# How to solve this multiple summation?

How to solve this summation ?

$$\sum_{0\le x_1\le x_2...\le x_n \le n}^{}\binom{k+x_1-1}{x_1}\binom{k+x_2-1}{x_2}...\binom{k+x_n-1}{x_n}$$ where $k$ , $n$ are known.

Due to hockey-stick identity , $$\sum_{i=0}^n\binom{i+k-1}{i}=\binom{n+k}{k}$$

• It’s infinite without some further restriction on the values of the $x_i$. Commented Jun 5, 2015 at 17:16
• It is till $n$ and $n$ is known. Commented Jun 5, 2015 at 17:17
• @abcz: Do you mean that $x_n\le n$? Commented Jun 5, 2015 at 17:20
• Yes $0\le x_i \le n$ Commented Jun 5, 2015 at 17:21
• you are summing over the $x_i$ or over $k$? If it is over $k$ put the range please. Other thing, we must assume that $n, k\ge 0$ or $n, k\in\mathbb Z$?
– user173262
Commented Jun 6, 2015 at 9:10

Suppose we seek to evaluate $$\sum_{0\le x_1\le x_2\cdots \le x_n \le n} {k+x_1-1\choose x_1} {k+x_2-1\choose x_2} \cdots {k+x_n-1\choose x_n}.$$

Using the Polya Enumeration Theorem and the cycle index of the symmetric group this becomes $$Z(S_n) \left(Q_0+Q_1+Q_2+\cdots +Q_n\right)$$

evaluated at $$Q_m = {k-1+m\choose m}.$$

Now the OGF of the cycle index $Z(S_n)$ of the symmetric group is $$G(z) = \exp \left(a_1 \frac{z}{1} + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} + \cdots \right).$$

The substituted generating function becomes $$H(z) = \exp \left(\sum_{p\ge 1} \frac{z^p}{p} \sum_{m=0}^n {k-1+m\choose m}^p\right) = \exp \left(\sum_{m=0}^n \sum_{p\ge 1} \frac{z^p}{p} {k-1+m\choose m}^p\right) \\ = \exp \left(\sum_{m=0}^n \log\frac{1}{1-{k-1+m\choose m} z}\right) = \prod_{m=0}^n \frac{1}{1-{k-1+m\choose m} z}.$$

Some thought shows that this could have been obtained by inspection.

We use partial fractions by residues on this function which we re-write as follows: $$(-1)^{n+1} \prod_{m=0}^n {k-1+m\choose m}^{-1} \prod_{m=0}^n \frac{1}{z-1/{k-1+m\choose m}}.$$

Switching to residues we obtain $$(-1)^{n+1} \prod_{m=0}^n {k-1+m\choose m}^{-1} \sum_{m=0}^n \frac{1}{z-1/{k-1+m\choose m}} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1/{k-1+m\choose m}-1/{k-1+p\choose p}}.$$

Preparing to extract coefficients we get $$(-1)^{n} \prod_{m=0}^n {k-1+m\choose m}^{-1} \sum_{m=0}^n \frac{{k-1+m\choose m}}{1-z{k-1+m\choose m}} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1/{k-1+m\choose m}-1/{k-1+p\choose p}}.$$

Doing the coefficient extraction we obtain $$(-1)^{n} \prod_{m=0}^n {k-1+m\choose m}^{-1} \sum_{m=0}^n {k-1+m\choose m}^{n+1} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1/{k-1+m\choose m}-1/{k-1+p\choose p}} \\ = (-1)^{n} \prod_{m=0}^n {k-1+m\choose m}^{-1} \sum_{m=0}^n {k-1+m\choose m}^{2n+1} \\ \times \prod_{p=0, \; p\ne m}^n \frac{1}{1-{k-1+m\choose m}/{k-1+p\choose p}} \\ = (-1)^{n} \sum_{m=0}^n {k-1+m\choose m}^{2n} \prod_{p=0, \; p\ne m}^n \frac{1}{{k-1+p\choose p}-{k-1+m\choose m}}.$$

The complexity here is good since the formula has a quadratic number of terms in $n.$ The number of partitions that a total enumeration would have to consider is given by

$$Z(S_n) \left(Q_0+Q_1+Q_2+\cdots +Q_n\right)$$

evaluated at $Q_0 = Q_1 = Q_2 = \cdots = Q_n = 1$ which gives the substituted generating function

$$A(z) = \exp\left((n+1)\log\frac{1}{1-z}\right) = \frac{1}{(1-z)^{n+1}}.$$

This yields for the total number of partitions $${n+n\choose n} = {2n\choose n}$$ which by Stirling has asymptotic (consult OEIS A00984) $$\frac{4^n}{\sqrt{\pi n}} \quad\text{and}\quad n^2\in o\left(\frac{4^n}{\sqrt{\pi n}}\right).$$

For example when $n=24$ and $k=5$ we would have to consider ${48\choose 24} = 32.247.603.683.100$ partitions but the formula readily yields $$424283851839410438109261697709077430045882514844\\ 665327684062172306602549601581316037895634544256\\ 47212676100.$$

Additional exploration of these formulae may be undertaken using the following Maple code which contrasts total enumeration and the closed formula.

A :=
proc(n, k)
option remember;
local iter;

iter :=
proc(l)
if nops(l) = 0 then
elif nops(l) < n then
else
mul(binomial(k-1+l[q], l[q]), q=1..n);
fi;
end;

iter([]);
end;

EX :=
proc(n, k)
option remember;