sequences and series - 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}$$

Answer

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;