MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Consider the multi-index $\gamma=(\gamma_1,\ldots, \gamma_n)$. Is there a closed form for the sum $\sum_{|\gamma|=k} \gamma!$ in terms of $n$ and $k$? Asymptotics, or good upper bounds are also very helpful.

Here is what I have tried. Let $f(x)=\sum_{i=0} i! x^{i+2}$. This generating function satisfies the ODE $x^2f'(x)=f(x)-x$. Then the sum $\sum_{|\gamma|=k} \gamma!$ is the coefficient of $x^{k+2n}$ in $f(x)^n$. However I don't have any means to find this coefficient.

share|cite|improve this question
the generating function of your sum regarded as a sequence in k seems to satisfy the relatively simple nonlinear DE $n x^2 g(x) g''(x) -(n-1)g'(x)^2 + n(3x-1)g'(x)+n^2g(x)^2=0$. Not sure whether this may be helpful, and I have no time to check right now. It may well be a triviality, in which case I beg your pardon. – Martin Rubey Mar 14 '11 at 15:35
is there any particular relation of $k$ and $n$ that interests you? – Konstantinos Panagiotou Mar 14 '11 at 20:55
A closed form is unlikely. For fixed $n$ (or $n$ small compared with $k$) the main contribution will come from the terms where for some $j$, $\gamma_j =k$ and $\gamma_i=0$ for $i\ne j$, so the sum will be asymptotic to $n\cdot k!$. More generally, asymptotic expansion can be obtained in this case by taking the terms where all but one $\gamma_i$ is a fixed integer. – Ira Gessel Mar 14 '11 at 23:55

Dividing by $(\gamma_1+\cdots+\gamma_n)!$ you are trying to estimate $$\sum_{\gamma \vdash k}\binom{k}{\gamma_1,\dots,\gamma_n}^{-1}$$ One way to start would be to write it as an integral over the probability simplex (sum of generalized beta functions) or to try to find some information from the generating function. For $n=2$, for instance the integral representation is $$\sum_{i=0}^k \binom{k}{i}^{-1}=(k+1)\int_{0}^1 \frac{(1-t)^{k+1}-t^{k+1}}{1-2t}dt$$ and the generating function is $$\sum_{k=0}^{\infty} \left(\sum_{i=0}^k \binom{k}{i}^{-1}\right)x^k=\frac{2x}{1-x}-\frac{2x}{2-x}-\frac{2x \log(1-x)}{(2-x)^2}$$ from which it is not very hard to see that $$\sum_{i=0}^k \binom{k}{i}^{-1} \sim 2+\frac{2}{k-1}$$ so $$\sum_{i=0}^k i!(k-i)!\sim k!\left(2+\frac{2}{k-1}\right)$$

share|cite|improve this answer

Let's try $n=2$. Maple says: $$ \sum_{j = 0}^{k} j!(k - j)! = -\Biggl(\mathrm{LerchPhi} (2,1,k) k^{2} + \mathrm{LerchPhi} (2,1,k) k + \frac{i \pi k^{2}}{2^{k}} + \frac{i \pi k}{2^{k}} - 3 k - 1\Biggr) \frac{\Gamma (k)}{2} $$ but doesn't know asymptotics for $\mathrm{LerchPhi}(2,1,k)$.

share|cite|improve this answer
This is – Gerry Myerson Mar 14 '11 at 23:49

Your Answer


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