Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
    
This is oeis.org/A003149 –  Gerry Myerson Mar 14 '11 at 23:49
add comment

Your Answer

 
discard

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.