prove $\sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n$

Question

A descent in the permutation $\sigma = a_1 \cdots a_n \in S_n$ is an index $i\in[n-1$] for which $a_i > a_{i+1}$. Let A(n, k) be the number of permutations of $[n]$ with $k-1$ descents where $n \geq 1$. Let $A(0,0) = 1$ and $A(0,k) = 0$ for $k \geq 1$ and let: $A(n+1,k)=kA(n,k)+(n-k+2)A(n,k-1)$

For $n \geq 1$ prove that: \begin{equation} \sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n \end{equation}

Proof by Induction:

For n = 1 : $\sum \limits_{k=1}^1 A(1,k){x+k-1 \choose 1}= A(1,1)\binom{x}{1}=(A(0,1)+A(0,0))x = x=x^1$

Suppose: $\sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n$

$\sum \limits_{k=1}^{n+1} A(n+1,k){x+k-1 \choose n+1}$

$=\sum \limits_{k=1}^{n} A(n+1,k){x+k-1 \choose n+1}+ A(n+1,n+1){x+n \choose n+1}$

$=\sum \limits_{k=1}^{n} \big( kA(n,k)+(n-k+2)A(n,k-1)\big){x+k-1 \choose n+1}+ A(n+1,n+1){x+n \choose n+1}$

$=\sum \limits_{k=1}^{n} kA(n,k){x+k-1 \choose n+1} + \sum \limits_{k=1}^{n}(n-k+2)A(n,k-1){x+k-1 \choose n+1} + A(n+1,n+1){x+n \choose n+1}$

$=k\sum \limits_{k=1}^{n} A(n,k){x+k-1 \choose n+1} + (n-k+2)\sum \limits_{k=1}^{n}A(n,k-1){x+k-1 \choose n+1} + A(n+1,n+1){x+n \choose n+1} \\ = ???????????$

how to complete the proof?

Answer 1

Let's give a combinatorial proof of this identity. This answer will be a simplified version of $[1]$.

Let $\sigma$ be a permutation on $n$ letters. We will call an index $1 \le i \le n$ an index of descent if $\sigma(i) > \sigma(i+1)$ or if $i=n$, i.e. a permutation will always end in a descent by our convention. Then our numbers $A(n,k)$ counts the total number of permutations on $n$ letters with precisely $k$ indices of descent (these are Eulerian numbers with slightly shifted indices).

Now we define the notion of a barred permutation. A barred permutation on $n$ letters with $k$ bars is a permutation with precisely $k$ bars inserted into the permutation with the restriction that there must be at least one bar inserted between each descent. Note that this means there must always be a bar ending the permutation.

For example, the barred permutations on $3$ letters with $2$ bars are: $$\{123||,\ 12|3|,\ 1|23|,\ |123|,\ 13|2|,\ 2|13|,\ 23|1|,\ 3|12|\}.$$

Let $B(n,k)$ denote the number of barred permutations on $n$ letters with $k$ bars. Let us count $B(n,k)$ in two ways.

First, note that a barred permutation on $n$ letters with $k$ bars can be obtained from a regular permutation on $n$ letters with $k-i$ descents by placing a bar at each of the $k-i$ indices of descent, and then arbitrarily placing the remaining $i$ bars. The way of placing $i$ bars to separate $n$ objects is $\binom{n+i}{i}$ via stars and bars. Therefore we must have $$B(n,k) = \sum_{i=0}^{k-1}\binom{n+i}{i}A(n,k-i).$$ Reindexing the above sum with $j=k-i$, we get $$B(n,k) = \sum_{j=1}^k\binom{n+k-j}{n}A(n,j).$$

On the other hand, we can count $B(n,k)$ directly. Notice that the segment of the permutation between any two bars (if non-empty) is strictly increasing. Therefore the number of barred permutations on $n$ letters with $k$ bars is precisely the number of partitions of the set $\{1,2,\cdots,n\}$ into at most $k$ ordered parts (or equivalently, the number of functions from $\{1,2,\cdots,n\}$ to $\{1,2,\cdots,k\}$). For each element in $\{1,2,\cdots,n\}$, we must choose one of the $k$ partitions it goes into. There are $k$ choices for each of the $n$ elements for a total of $k^n$ such ordered partitions. Therefore we must have $$B(n,k) = k^n.$$ This establishes the fact that $$B(n,k) = k^n = \sum_{j=1}^k\binom{n+k-j}{n}A(n,j).$$ This is almost the identity as you have it. The rest is just a bit of book keeping. First, note that the numbers $A(n,j)$ have the symmetry $A(n,j) = A(n,n-j+1)$ (prove this by reversing a permutation). Therefore let us re-index the sum again with $\ell = n-j+1$. Then we get $$k^n = \sum_{\ell=n-k+1}^{n}\binom{\ell+k-1}{n}A(n,\ell).$$ Finally, note that if $\ell < n-k+1$ then $\ell + k - 1 < n$, so that the binomial coefficient is $0$ in that case. Therefore we may lower our index of summation to $1$ without harm. This is precisely the identity you wanted.

$[1]$ A. S. Dzhumadil’daev, Worpitzky identity for multipermutations. Mathematical Notes. September 2011, Volume 90, Issue 3-4, pp 448-450

Answer 2

This is Worpitzky's identity. It is mentioned in Concrete Mathematics, equation (6.37) there. It mentions that this is easy to prove by induction (presumably on $n$) and leaves doing this as an exercise. Although the book gives an "answer" to this question, this is just an equation that is neither easy to see nor obviously gives the identity, so I would like to provide a detailed answer here, just for the record. (I don't think this is actually the best approach though.) For this reason I'll use the Concrete Mathematics notation, which is a bit different from that in the question.

The Eulerian number $\def\euler{\genfrac<>{0pt}{}}\euler nk$ is defined for $n>0$ and $\def\N{\Bbb N}k\in\N$ as the number of permutations of $n$ with $k$ ascents. (Actually, the book defines this for $n=0$ as well, but I think this is somewhat pointless as one cannot make the fundamental relation that the numbers of ascents and descents add up to $n-1$ hold for $n=0$.) So the relation with the notation of the question of the question is given by $$\euler nk=A(n,n-k)$$ (this is also $A(n,k+1)$, since the reversal of a permutation with $n-k-1$ descents gives a permutation with $k~$descents). The fundamental recurrence relation for Eulerian numbers is $$ \euler nk=(k+1)\euler{n-1}k+(n-k)\euler{n-1}{k-1} \qquad\text{for all $n>1$ and $k>0$} $$ which can be checked to give the relation $A(n+1,k)=kA(n,k)+(n-k+2)A(n,k-1)$ of the question. Worpitzky's identity becomes $$ \sum_{k=0}^{n-1}\euler nk\binom{x+k}n=x^n \qquad\text{for all $n>1$.} $$

The answer that Concrete Mathematics provides to the exercise (6.14) asking for a proof of this identity (presumably by induction as the main text mentions) reads "We have $$x\binom{x+k}n=(k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}$$ because $(n+1)x=(k+1)(x+k-n)+(n-k)(x+k+1)$. (It suffices to verify the latter identity when $k=0$, $k=-1$, and $k=n$.)"

Starting at the end, I don't really see the point of the final parenthesised remark, though I can easily justify the equation. Maybe it is saying that both sides of the equation are at most quadratic in $k$, so equality at three distinct values of $k$ suffices for equality everywhere; I would prefer saying both sides are linear expressions in $x$, with leading coefficients $n+1$ respectively $(k+1)+(n-k)$, and constant terms $0$ respectively $(k+1)(k-n)+(n-k)(k+1)$, with obvious equality in both cases.

The reason why the final equation implies the one displayed before it in the answer, is that it is what remains from the displayed equation after expanding all binomial coefficients using $\binom xm=\frac{x(x-1)\ldots(x-m+1)}{m!}$, simplifying by the factors $(x+k)(x+k-1)\ldots(x+k-n+1)$ that appear for all three binomial coefficients, and multiplying by $(n+1)!$ to chase denominators.

Finally, having justified the equation given by way of answer, why does it prove Worpitzky's identity? It would provide help for the induction step (the base case $n=1$ is obvious); here is what I think is intended. Assuming that $x^n=\sum_{k=0}^{n-1}\euler nk\binom{x+k}n$, multiply both sides by $x$, and try to transform the right hand side into $\sum_{l=0}^n\euler{n+1}l\binom{x+l}{n+1}$, which is what $x^{n+1}$ should be equal to. Bringing $x$ into the summation and combining it with $\binom{x+k}n$ using the equation that was proved, one gets $$ x^{n+1}= \sum_{k=0}^{n-1}\euler nk\left((k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}\right). $$ We now group together identical binomial coefficients $\binom{x+l}{n+1}$, and compare the factor they come with to the desired factor $\euler{n+1}l$. For $l=0$ the factor is just $\euler n0\times1=1$ obtained for $k=0$, as it should. Otherwise ($l>0$) one gets for the factor of $\binom{x+l}{n+1}$ a contribution $\euler nl(l+1)$ from $k=l$, and a contribution $\euler n{l-1}(n+1-l)$ from $k=l-1$, and these add up to the desired $\euler{n+1}l$ by the basic recurrence relation of Eulerian numbers. QED