4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Martin Rubey
    Commented Mar 14, 2011 at 15:35
  • $\begingroup$ is there any particular relation of $k$ and $n$ that interests you? $\endgroup$
    – Konstantinos Panagiotou
    Commented Mar 14, 2011 at 20:55
  • $\begingroup$ 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. $\endgroup$
    – Ira Gessel
    Commented Mar 14, 2011 at 23:55

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1

You must log in to answer this question.