Sum of product of squared binomial coefficients

Question

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} + \cdots + 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}$:

\begin{align} n^{2m} & = \sum_{y_{1} + \cdots + y_{n}\ =\ 2m} \,\,\binom{2m}{y_{1},\ldots,y_{n}} \\[5mm] & = \sum_{y_{1} + \cdots + y_{n}\ =\ 2m} \,\,\,\, \prod_{i = 1}^{w} \binom{\sum_{j = 1}^{i}y_{j}}{y_{i}} \end{align}

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

Answer 1

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}}$.