2
$\begingroup$

Similar to the sum of product of binomial coefficients—what happens when I square the binomial coefficients? Is there a nice closed formula for that?

More precisely, I'm interested in the special case where the $k_i$ are all equal to the sum of all $x_i$ (to use the notation of the question linked above), which I'll call $m$ (not necessarily equal to $n$ here).

So what I'm looking for is making the following sum tractable:

$$S_{n,m}=\sum_{x_1+\ldots+x_n=m}\prod_{i=1}^{n}{\binom{m}{x_i}^2}$$

My goal is to show that $S_{n,m}\cdot n^{-2m}$ decreases as the number of summands, $n$, grows. I've tried expanding $n^{2m}$:

$$n^{2m} = \sum_{y_1+\ldots+y_n=2m}{\binom{2m}{y_1,\ldots,y_n}} = \sum_{y_1+\ldots+y_n=2m} {\prod_{i=1}^{w} {\binom{\sum_{j=1}^{i}{y_j}}{y_i}}}$$

but I didn't get anywhere with that. I'd be grateful for any pointers on how to approach this.

$\endgroup$
2
$\begingroup$

We consider the generating function \begin{align*} S_m(x)=\sum_{j=0}^m\binom{m}{j}^2x^j\qquad\qquad m\geq 0 \end{align*} Note $S_{n,m}$ is the coefficient of $x^m$ of $\left(S_m(x)\right)^n$. \begin{align*} S_{n,m}=\sum_{{x_1+\ldots+x_n=m}\atop{x_j\geq 0}}\prod_{i=1}^{n}{\binom{m}{x_i}^2} =[x^m]\left(S_m(x)\right)^n \end{align*}

We can represent $S_m(x)$ in terms of Legendre polynomials $P_m(x)$. From the representation \begin{align*} P_m(x)=\frac{1}{2^m}\sum_{j=0}^m\binom{m}{j}^2(x-1)^{m-j}(x+1)^j \end{align*} we obtain

\begin{align*} P_m\left(\frac{x+1}{x-1}\right) &=\frac{1}{2^m}\sum_{j=0}^m\binom{m}{j}^2\left(\frac{x+1}{x-1}-1\right)^{m-j}\left(\frac{x+1}{x-1}+1\right)^j\\ &=\frac{1}{2^m}\sum_{j=0}^m\binom{m}{j}^2\frac{2^{m-j}}{(x-1)^{m-j}}\cdot \frac{(2x)^j}{(x-1)^j}\\ &=\frac{1}{(x-1)^m}\sum_{j=0}^m\binom{m}{j}^2x^j\tag{1} \end{align*}

Multiplication of (1) with $(x-1)^m$ gives \begin{align*} S_m(x)=(x-1)^mP_m\left(\frac{x+1}{x-1}\right)\qquad\qquad m\geq 0 \end{align*} and we finally conclude \begin{align*} S_{n,m}&=[x^m]\left(S_m(x)\right)^n\\ &=[x^m](x-1)^{mn}P_m\left(\frac{x+1}{x-1}\right)^n\qquad\qquad n\geq 1,m\geq 0 \end{align*}

Example: $S_{3,1}$ to $S_{3,3}$

At first wie calculate $S_{3,1}$ to $S_{3,3}$ according to the OPs definition of $S_{n,m}$. The we look at the coefficients of the corresponding transformed Legendre polynomials.

\begin{align*} S_{3,1}&=\sum_{{x_1+x_2+x_3=1}\atop{x_j\geq 0}}\prod_{i=1}^3\binom{1}{x_i}^2 =\frac{3!}{2!1!}\binom{1}{0}^2\binom{1}{0}^2\binom{1}{1}^2\\ &=\color{blue}{3}\\ S_{3,2}&=\sum_{{x_1+x_2+x_3=2}\atop{x_j\geq 0}}\prod_{i=1}^3\binom{2}{x_i}^2\\ &=\frac{3!}{2!1!}\binom{2}{0}^2\binom{2}{0}^2\binom{2}{2}^2 +\frac{3!}{1!2!}\binom{2}{0}^2\binom{2}{1}^2\binom{2}{1}^2\\ &=3+48\\ &=\color{blue}{51}\\ S_{3,3}&=\sum_{{x_1+x_2+x_3=3}\atop{x_j\geq 0}}\prod_{i=1}^3\binom{3}{x_i}^2\\ &=\frac{3!}{2!1!}\binom{3}{0}^2\binom{3}{0}^2\binom{3}{3}^2 +\frac{3!}{1!1!1!}\binom{3}{0}^2\binom{3}{1}^2\binom{3}{2}^2\\ &\qquad+\frac{3!}{3!}\binom{3}{1}^2\binom{3}{1}^2\binom{3}{1}^2\\ &=3+486+729\\ &=\color{blue}{1218} \end{align*}

On the other hand we obtain with some help of Wolfram Alpha \begin{align*} S_1(x)&=(x-1)P_1\left(\frac{x+1}{x-1}\right)\\ &=1+x\\ S_1^2(x)&=1+2x+x^2\\ S_1^3(x)&=1+\color{blue}{3}x+3x^2+x^3\\ \\ S_2(x)&=(x-1)^2P_2\left(\frac{x+1}{x-1}\right)\\ &=1+4x+x^2\\ S_2^2(x)&=1+8x+18x^2+8x^3+x^4\\ S_2^3(x)&=1+12x+\color{blue}{51}x^2+88x^3+51x^4+12x^5+x^6\\ \\ S_3(x)&=(x-1)^3P_3\left(\frac{x+1}{x-1}\right)\\ &=1+9x+9x^2+x^3\\ S_3^2(x)&=1+18x+99x^2+164x^3+99x^4+18x^5+x^6\\ S_3^3(x)&=1+27x+270x^2+\color{blue}{1218}x^3+2484x^4+2484x^5+1218x^6+270x^7+27x^8+x^9 \end{align*} with corresponding coefficients marked in $\color{blue}{\text{blue}}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.