# Estimate on sum of squares of multinomial coefficients

I am interested in approximating the sum of the squares of the multinomial coefficients, i.e.

$a_\ell^p := \sum_{k_0+\ldots+k_p = \ell} (\frac{\ell!}{k_0! \ldots k_p!})^2$

or more general,

$a_\ell^{\alpha_0,\ldots, \alpha_p} := \sum_{k_0+\ldots+k_p = \ell} (\prod_{i=0}^p \alpha_i^{k_i})^2(\frac{\ell!}{k_0! \ldots k_p!})^2$

Here $p$ is prime, and $\ell$ is an integer smaller then $p$, $k_i$ are non-negative integers. I would like to obtain some simple expression in terms of $\ell$ and $p$, a good approximation for large $p$, an upper bound will be good.

I saw some results on recursive formula for such expressions, but not estimates. Should I just go with a Stirling formula in all the terms or is there something better done in this direction?

Does someone knows what would be the Mathematica/Maple code for calculating such sums as functions from $p$ and $l$?

Thanks!

• That $p$ is prime doesn't affect anything. It probably helps to view this as a question about random walks, rescaling so $\sum \alpha_i = 1$. – Douglas Zare Apr 21 '13 at 16:45
• Even for $p=2$ (the next case after the standard binomial identity), it seems like the sum doesn't have a closed form. oeis.org/A002893 If you were interested in a fixed $p$ as $\ell\to \infty$ then you should be able to get asymptotics from the Central Limit Theorem or local variations, or Laplace's method, maybe something like $(p+1)^{2\ell}(c \ell)^{-p/2}$. However, you specify $\ell \lt p$. – Douglas Zare Apr 21 '13 at 20:26

Douglas already commented that the asymptotics for fixed $p$ and $l\to \infty$ shoudl follow from standard methods. One gets $$a_{\ell}^p\approx (p+1)^{2\ell+\frac{p+1}{2}}(4\pi \ell)^{-\frac{p}{2}}.$$ See theorem 4 in "Counting Abelian squares", by Richmond and Shallit. Notice that these numbers appear also in combinatorics when considering abelian squares, or more generally abelian powers, on a fixed alphabet.
For the asymptotics that you're interested in, at least in the unweighted case, one can say $$a _{\ell} ^p=\sum _{j=0} ^{\ell} \binom{p}{j}\sum _{a _1+ \cdots +a _j = \ell \atop a _i \geq 1} \binom{\ell}{a _1,a _2,\dots,a _j}^2$$ which makes it clear that $a _{\ell}^p$ is a polynomial in $p$ of fixed degree $\ell$. The coefficient of $\binom{p}{\ell}$ is $(\ell!)^2$, and the coefficient of $\binom{p}{\ell -1}$ is $\frac{\ell-1}{4}(\ell!)^2$, so you have $$a _{\ell}^p =\ell!p^{\ell}-\ell!\frac{\ell(\ell-1)}{4}p^{\ell-1}+O(p^{\ell-2}).$$
• Thank you for the answer and the link, it is very useful. Indeed, in my case I can only send $p$ to $\infty$, but $l$ is always smaller then $p$ and therefore your second comment is the type of result I was looking for. If you have time, can you please explain more in details - I understood the recursive formula for $f_k(n)$ in the paper but what you wrote is different, and I didn't quite get it.. – Liss Apr 25 '13 at 10:31
• I figured out how you got the coefficients in front of the powers of $p$, but I am only confused with the minus of the second term? Sorry if am asking dumb questions – Liss Apr 25 '13 at 10:41