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;