Role of binomial coefficents in nested summations in layman terms

Question

I has this doubt from almost two years and not getting a simple solution in layman terms. In short, the doubt is the about relation between binomial coefficients and the nesting summation.

Recently I started reading this pre print in which authors claimed a formula and it shows relation between nesting and binomial coefficients used.

The formula given is as follows:

$$\sum\limits_{}^{(m)} n^k = \sum\limits_{i=0}^{k} \binom{n+m-1}{m+i} \mu[k,i]$$

Let's kept aside $\mu[k,i]$. The formula is showing relation between nesting ($m$) and the corresponding binomial coefficients used $\binom{n+m-i}{m+i}$.

In simple terms, if the binomial coefficient is $\binom{x}{y}$ for nesting $m$, then if we increase one more summation i.e., $(m+1)$, the binomial coefficients become $\binom{x+1}{y+1}$. The proving technique used is mathematical induction and hence can't able to get any clue from the pre print.

Is there any intuitive explanation to understand this?

Answer 1

This is a starter. We provide a combinatorial proof of the simplest case $k=0$. In order to do so we derive a more conventional representation of OP's stated formula and and give some additional information regarding the coefficients $\mu[k,i]$.

We start with a more conventional representation of the formula. Following the definition of $\sum^{(m)}$ given in the paper we have for non-negative integers $m,k$ and positive integers $n$ \begin{align*} \sum^{(m)}n^k= \begin{cases} \sum_{j=1}^n\sum^{(m-1)}j^k&m>0\tag{1}\\ n^k&m=0 \end{cases} \end{align*}

We obtain from (1)

\begin{align*} \sum^{(1)}n^k&=\sum_{j_1=1}^n\sum^{(0)}j_1^k=\sum_{j_1=1}^nj_1^k=\sum_{1\leq j_1\leq n}j_1^k\\ \sum^{(2)}n^k&=\sum_{j_2=1}^n\sum^{(1)}j_2^k=\sum_{j_2=1}^n\sum_{j_1=1}^{j_2}j_1^k=\sum_{1\leq j_1\leq j_2\leq n}j_1^k\\ \end{align*} and conclude for general $m>0$ \begin{align*} \color{blue}{\sum^{(m)}n^k=\sum_{1\leq j_1\leq \ldots\leq j_m\leq n}j_1^k}\tag{2}\\ \end{align*}

With (2) OP's formula can now be written as \begin{align*} &\sum_{j_m=1}^{n}\sum_{j_{m-1}=1}^{j_m}\cdots\sum_{j_1=1}^{j_2}j_1^k\\ &\qquad=\color{blue}{\sum_{1\leq j_1\leq \ldots \leq j_{m}\leq n}j_1^k=\sum_{j=0}^k\binom{n+m-1}{m+j}\mu[k,j]}\tag{3} \end{align*}

Now we look in some more detail at the numbers $\mu[k,j]$.

The numbers $\mu[k,j]$:

The authors of the paper introduce the numbers $\mu[k,j]$ as triangle numbers $$ \begin{array}{l|rrrrrrrrrrrrrrrrrr} k/j&0&1&2&3&4&\cdots\\ \hline 0&1\\ 1&1&1\\ 2&1&3&2\\ 3&1&7&12&6\\ 4&1&15&50&60&24\\ \,\vdots&&&\vdots\,&&&\\ \end{array} $$ and denote them as Saras numbers. In fact these numbers are already known as Worpitzky numbers (see here) and are stored as A028246 in OEIS.org. They can be represented via Stirling numbers of the second kind $k\brace j$ and OPs formula (3) becomes \begin{align*} \color{blue}{\sum_{1\leq j_1\leq \ldots\leq j_m\leq n}j_1^k=\sum_{j=0}^k\binom{n+m-1}{m+j}j!{{k+1}\brace{j+1}}}\tag{4} \end{align*}

The special case $k=0$:

Setting $k=0$ in (4) we have \begin{align*} \sum_{1\leq j_1\leq \ldots \leq j_m\leq n}1=\binom{n+m-1}{m}\tag{5} \end{align*}

The left-hand side of (5) can be interpreted as follows. We count the number of occurrences of $1\leq j_1\leq \ldots \leq j_m\leq n$ . There is a one-to-one correspondence between these and the $(m+1)$-tupel \begin{align*} (n-j_{m},j_m-j_{m-1},\ldots,j_1-1) \end{align*} whose entries sum up to $n-1$. This can be counted by arranging $n-1$ balls and $m$ dividers between bins in a row which can be done in $\binom{n+m-1}{m}$ ways. This is the right-hand side of (5).