MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?


share|cite|improve this question
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. 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
up vote 7 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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