I am having problems with a combinatorial argument and I need some help. I do not do combinatorics so I am not sure what is the best notation for this problem (any suggestion is very welcome). Consider $ninmathbb{N}$ with $ngeq 2$. I would like to compute the following quantity: First consider the list of numbers $$

L_n:={tfrac{1}{2},tfrac{3}{2},…,tfrac{2n-1}{2}}.

$$

Now let’s call $P_{3}$ the set of all possible selection of $3$ elements of $L_n$ where it is possible to repeat an element at most two times where we don’t allow permutations. The sense of "allowing to repeat two times an element" has to be understood as having "objects" with repeated labels, and hence having two times each "object" (number). So, for example, if $n=2$, we have $$

P_3={{tfrac{1}{2},tfrac{1}{2},tfrac{3}{2}},{tfrac{1}{2},tfrac{1}{2},tfrac{3}{2}},{tfrac{1}{2},tfrac{3}{2},tfrac{3}{2}}{tfrac{1}{2},tfrac{3}{2},tfrac{3}{2}}},

$$

where ${tfrac{1}{2},tfrac{1}{2},tfrac{3}{2}}$ appears two times in $P_3$ because we can pick both repetitions of $tfrac{1}{2}$ and then we can choose any of the two differents objects with the label $tfrac{3}{2}$. On the other hand, if we consider for instance, $P_2$ (the same definition of $P_3$ but with all possible selections of $2$ elements instead of three, and repeating at most two times each element (exactly as before)), then the pair $$

{tfrac{1}{2},tfrac{3}{2}}

$$

appears **four** times in $P_2$ (see the "PS2" below for more details). In this sense, the pair ${tfrac{1}{2},tfrac{1}{2}}$ also belongs to $P_2$ and appears only one time. I would like to compute the quantity $$

mathcal{Q}_3=sum_{Pin P_{3}}prod_{kin P}k^2.

$$

The previous quantity must to be understood in the following way: in the case $n=3$, if $P$ is for example ${tfrac{1}{2},tfrac{1}{2},tfrac{5}{2}}$, then $$

prod_{kin P}k^2=(tfrac{1}{2})^2(tfrac{1}{2})^2(tfrac{5}{2})^2.

$$

More generally I would like to understand the growth of the previous quantity once we fix $n$ and we increase the number of elements we can choose. In other words, consider $min{1,…,n}$ and denote by $P_{m}$ the set of all possible selections of $m$-elements (from our fixed list $L_n$) where we are allowed to repeat an element at most two times (exactly as before). Would it be possible to prove something like (for example) $$

mathcal{Q}_{2m-2}leq 4mathcal{Q}_{2m-1}?

$$

Here, by convention lets say that $mathcal{Q}_0:=1$.

PS: Just as an example, if $n=2$ and $m=2$, then $$

sum_{Pin P_3}prod_{kin P}k^2=tfrac{45}{16} quad hbox{and}quad sum_{Pin P_2}prod_{kin P}k^2=tfrac{59}{8},

$$

and hence $tfrac{59}{8}=mathcal{Q}_2<4mathcal{Q}_3=tfrac{90}{8}$. Moreover, if $m=1$ in the previous example, then $mathcal{Q}_1=5$ and $mathcal{Q}_0=1$, so $mathcal{Q}_0<4mathcal{Q}_1$.

**PS2:** To fix ideas (I am emphasising just because I am worried that the problem might not be sufficiently clear), if $n=2$ then $P_1$ would be $ P_1={tfrac{1}{2},tfrac{1}{2},tfrac{3}{2},tfrac{3}{2}}$, and $$

P_2={{tfrac{1}{2},tfrac{1}{2}},{tfrac{1}{2},tfrac{3}{2}},{tfrac{1}{2},tfrac{3}{2}},{tfrac{1}{2},tfrac{3}{2}},{tfrac{1}{2},tfrac{3}{2}},{tfrac{3}{2},tfrac{3}{2}}},

$$

where ${tfrac{1}{2},tfrac{3}{2}}$ appears four times because we can choose the first appearance of $tfrac{1}{2}$ with both, the first and the second appearance of $tfrac{3}{2}$; and then we can do the same with the second appearance of $tfrac{1}{2}$. (There probably is a much better way to write this with proper combinatorial notation). So for example I think that the fact that this pair ${tfrac{1}{2},tfrac{3}{2}}$ appears four times in the set has to be related to considering the permutations of ${tfrac{1}{2},tfrac{3}{2}}$ (which are two), with an extra factor of $2$ due to the fact we are allowing to consider two times each element (but I am not sure how to write that, mainly because the pair ${tfrac{1}{2},tfrac{1}{2}}$ appears only **one** time in the set). I hope the problem is clear enough.

Mathematics Asked by Sharik on November 21, 2021

2 AnswersElaborating on Michael's answer, it's easy to get a closed-form expression for $mathcal{Q}_3$ (and $mathcal{Q}_m$) for general $n$. In terms of elementary symmetric polynomials, we have $$mathcal{Q}_m = e_m(left(frac{1}{2}right)^2,left(frac{1}{2}right)^2,left(frac{3}{2}right)^2,dots,left(frac{2n-1}{2}right)^2,left(frac{2n-1}{2}right)^2).$$ While it may be tricky to compute $e_3$ from scratch, we can easily get initial values of power sum symmetric polynomials: $$p_k(left(frac{1}{2}right)^2,left(frac{1}{2}right)^2,left(frac{3}{2}right)^2,dots,left(frac{2n-1}{2}right)^2,left(frac{2n-1}{2}right)^2)=frac{1}{2^{2k-1}}cdot p_{2k}(1,3,dots,2n-1).$$ For $k=1,2,3$, they are $$frac{n(2n-1)(2n+1)}{6}, frac{n(2n-1)(2n+1)(12n^2-7)}{120}, frac{n(2n-1)(2n+1)(48n^4-72n^2+31)}{672}.$$ Using Newton's identities, we get $$mathcal{Q}_1 = frac{n(2n-1)(2n+1)}{6},$$ $$mathcal{Q}_2 = frac{n(2n-1)(2n+1)(40n^3-36n^2-10n+21)}{720},$$ $$mathcal{Q}_3 = {frac {n left( 2,n-1 right) left( 2,n+1 right) left( n-1 right) left( 2,n-3 right) left( 560,{n}^{4}-112,{n}^{3}-320,{n}^{2}+628,n+465 right) }{90720}}.$$

For a fixed $m$, $mathcal{Q}_m$ is expressed as a polynomial in $n$ as follows: $$mathcal{Q}_m = frac{(-1)^m}{m!} mathcal{B}_m(t_1, t_2, ldots, t_m ),$$ where $mathcal{B}_m$ is the complete exponential Bell polynomial and $$t_k := -frac{(k-1)!}{2^{2k-1}}p_{2k}(1,3,dots,2n-1).$$ The latter is expressed as a polynomial in $n$ with Faulhaber's formula: $$p_{2k}(1,3,dots,2n-1) = p_{2k}(1,2,dots,2n-1) - 2^{2k}p_{2k}(1,2,dots,n-1)$$ $$ = frac{1}{2k+1}sum_{j=0}^{2k}(-1)^jbinom{2k+1}j B_j ((2n-1)^{2k+1-j} - 2^{2k}(n-1)^{2k+1-j}),$$ where $B_j$ are Bernoulli numbers.

Answered by Max Alekseyev on November 21, 2021

The number of subsets can be found by pretending that there are two “copies” of each element in $P_1$, and then using standard combinatorics arguments. For example, if you are choosing subsets of $m$ elements from $L_n$, allowing the selection to be repeated no more than twice, there are ${2n choose m}$ possible subsets.

To calculate the $mathcal{Q}_n$ quantities, we can use generating functions. It's easiest to proceed by looking at the example $m = 2$. Consider the polynomial $$ f_2(x) = left[ 1 + left(frac{1}{2}right)^2 x right] left[ 1 + left(frac{1}{2}right)^2 x right] left[ 1 + left(frac{3}{2}right)^2 x right] left[ 1 + left(frac{3}{2}right)^2 x right]. $$ This will be some polynomial in $x$, with terms up to $x^4$. If we were to multiply this out, what would the coefficient of $x^3$ be? It would result from all of the terms where we "pick" three of the $x$ terms from three of the monomials, and "pick" 1 from the remaining monomial. In other words, the coefficient of $x^3$ would be $$ left(frac{1}{2}right)^2 left(frac{1}{2}right)^2 left(frac{3}{2}right)^2 + left(frac{1}{2}right)^2 left(frac{1}{2}right)^2 left(frac{3}{2}right)^2 + left(frac{1}{2}right)^2 left(frac{3}{2}right)^2 left(frac{3}{2}right)^2 + left(frac{1}{2}right)^2 left(frac{3}{2}right)^2 left(frac{3}{2}right)^2 = mathcal{Q}_3. $$ In fact, it is not hard to see that by similar logic, $$ f_2(x) = mathcal{Q}_0 + mathcal{Q}_1 x + mathcal{Q}_2 x^2 + mathcal{Q}_3 x^3 + mathcal{Q}_4 x^4. $$

While this technique doesn't yield a closed-form expression^{*} for $mathcal{Q}_m$, it does allow for relatively easy exact calculation via computer algebra systems (Mathematica or equivalent.) In addition, it may be possible to use the generating function to make exact statements about the relative values of coefficients in the polynomial $f_n(x)$, and thus relating $mathcal{Q}_{2m-2}$ to $mathcal{Q}_{2m-1}$ as you hope to do.

My Mathematica code is below, if you are interested. It returns a list of the values of $mathcal{Q}_m$ for a given value of $n$.

```
n = 2;
poly[x_, a_] = (1 + a^2 x)^2;
f[n_, x_] := Expand[Product[poly[x, (2 i - 1)/2], {i, 1, n}]]
CoefficientList[f[n, x], x]
```

^{*} Mathematica does actually return an exact result for general $n$ in terms of Pochhammer symbols involving $1/sqrt{-x}$ and $x/(-x)^{3/2}$. But that's hardly useful.

Answered by Michael Seifert on November 21, 2021

1 Asked on December 15, 2020

0 Asked on December 15, 2020 by maximilian-janisch

0 Asked on December 14, 2020 by zhang

1 Asked on December 14, 2020 by user146215

2 Asked on December 14, 2020

1 Asked on December 14, 2020 by quanticbolt

2 Asked on December 14, 2020 by rexwilliamson

conditional probability density function probability probability distributions

0 Asked on December 14, 2020 by elene

branch cuts branch points complex analysis riemann surfaces trigonometry

2 Asked on December 14, 2020 by nicholas

2 Asked on December 13, 2020 by perlik

1 Asked on December 13, 2020 by john-porter

1 Asked on December 13, 2020 by qwaster

2 Asked on December 13, 2020 by jacky

3 Asked on December 13, 2020 by ivar-the-boneless

1 Asked on December 12, 2020 by luiz-guilherme-de-carvalho-lop

2 Asked on December 12, 2020 by eric-brown

Get help from others!

Recent Answers

- zkutch on A is greater than B by 25% then by what percentage B is less than A?
- Dominique on A is greater than B by 25% then by what percentage B is less than A?
- Ethan Bolker on A is greater than B by 25% then by what percentage B is less than A?
- Harish Chandra Rajpoot on A is greater than B by 25% then by what percentage B is less than A?
- NeitherNor on How to segment a group of symmetric points

Recent Questions

- Write condition if rectangle is inside another rectangle
- How to segment a group of symmetric points
- Prove $D(A):= {win H^{2}(0, 2pi): w(0) = w(2pi), w^{‘}(0) = w^{‘}(2pi) }$ is dense in $L^{2}(0,2pi).$
- A is greater than B by 25% then by what percentage B is less than A?
- Show continuity of partial derivatives of piece-wise function

© 2021 InsideDarkWeb.com. All rights reserved.