Sum involving the set of all possible combinations with at most two repetitions

Question

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.

Max Alekseyev · Answer

Elaborating 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.

Michael Seifert · Answer

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.

Sum involving the set of all possible combinations with at most two repetitions

2 Answers

Add your own answers!

Ask a Question