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

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

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.

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

## Related Questions

### How do I find the average rate of change of two points in a contour map?

1  Asked on December 15, 2020

### Winning money from random walks?

0  Asked on December 15, 2020 by maximilian-janisch

### Is every vector space isomorphic to a direct product of one-dimensional vector spaces?

0  Asked on December 14, 2020 by zhang

### There are operations that are not rotations?

0  Asked on December 14, 2020 by raxi-ral

### Prove that T is transitive if and only if the score of the $k^{th}$ vertex ($s_k$) = ‘$k-1$’ for $k =1,2,ldots. n$

1  Asked on December 14, 2020 by user146215

### Continuous $f$ has $≥2$ roots if $int_{-1}^{1} f(x)sqrt {1 – x^2} mathrm{d}x = int_{-1}^{1} xf(x) mathrm{d}x = 0$?

2  Asked on December 14, 2020

1  Asked on December 14, 2020 by quanticbolt

### Finding the probability of $Y>1/4$ when conditioned on $X=x$.

2  Asked on December 14, 2020 by rexwilliamson

### $arctan(z)$ and Riemann Surfaces

0  Asked on December 14, 2020 by elene

### How does $A$ relate to $B$ if $A – lfloor A/B rfloor – lceil A/B rceil leq lfloor A/B rfloor times (B+1)$?

2  Asked on December 14, 2020 by nicholas

### multiplicity of functions

0  Asked on December 14, 2020 by mathh

### If $x_n = (prod_{k=0}^n binom{n}{k})^frac{2}{n(n+1)}$ then $lim_{n to infty} x_n = e$

2  Asked on December 13, 2020 by perlik

### Find the angle that lets you make a bendy pipe

1  Asked on December 13, 2020 by john-porter

### How beneficial are Gröbner bases for solving systems of equations

1  Asked on December 13, 2020 by qwaster

### Evaluating $prod^{100}_{k=1}left[1+2cos frac{2pi cdot 3^k}{3^{100}+1}right]$

2  Asked on December 13, 2020 by jacky

### How many nonnegative integers $x_1, x_2, x_3, x_4$ satisfy $2x_1 + x_2 + x_3 + x_4 = n$?

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

### Set of open sets notation

1  Asked on December 12, 2020 by jpmarulandas

### Need help to understand a theorem about direct sums and regular morphism of R-modules

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

### Use cylindrical coordinates to find the volume of the solid using triple integrals

2  Asked on December 12, 2020 by eric-brown

1  Asked on December 12, 2020 by jasdeep-singh

Get help from others!