How to solve this multiple summation?

Question

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

Answer 1

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
            add(iter([q]), q=0..n)
        elif nops(l) < n then
            add(iter([op(l), q]), q=op(-1, l)..n)
        else
            mul(binomial(k-1+l[q], l[q]), q=1..n);
        fi;
    end;

    iter([]);
end;

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

    (-1)^n*add(binomial(k-1+m,m)^(2*n)*
               mul(1/(binomial(k-1+p,p)-binomial(k-1+m,m)), p=0..m-1)*
               mul(1/(binomial(k-1+p,p)-binomial(k-1+m,m)), p=m+1..n),
               m=0..n);
end;