Question: Using a combinatorial proof show the following identity.

$$x^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k,$$

where $x^{(n)}$ denotes the rising factorial and $(x)_k$ denotes the falling factorial.

I am also intersted in why it suffices to show such formulas only for $x \in \mathbb{N}$ and then expect them to hold for real or even complex $x$.

Context: We know that, $L(n,k)$ are Lah numbers satisfiying this recurrence relation: $$L(n,k) = L(n-1, k-1) + (n - 1 + k)L(n - 1,k),$$ and this explicit formula $L(n,k) = \frac{n!}{k!}\binom{n-1}{n-k}$. I have seen a few pages where Lah numbers were defined as the connecting coefficients between the rising and falling factorials, which is what I am trying to show, but I have yet to find a proof of my desired statement.


Noticing that $\binom{a}{b}=\frac{(a)_b}{b!}, $ you can write your expression as $$\binom{x+n-1}{n}=\sum _{k=1}^n\binom{n-1}{n-k}\binom{x}{k}$$ which is Vandermonde, so the standard combinatorial proof of Vandermonde suffices.

Notice that the explicit formula comes from shuffling the elements of $[n]$ in a line, using stars and bars to see that $\binom{n-1}{n-k}$ is the number of ways to partition the $n$ into positive $k$ parts $a_1+a_2+\cdots +a_k=n$ where order matters, and so you partition your line using first $a_1$ numbers, then $a_2$ until you get the $n$ numbers, and taking out the order of the $k$ parts. For example: Given $a_1=4,a_2=2,a_3=1,a_4=4$ then $$\underbrace{1\,9\,10\,2}_{a_1}\,\underbrace{5\,6}_{a_2}\,\underbrace{4}_{a_3}\,\underbrace{7\,3\,8}_{a_4}\text{ gives the ordered partition.}$$

It suffices to show it just for $x$ an integer because this are polynomials on $x$ and if you have two polynomials $P_1(x)=P_2(x)$ for $x\in \mathbb{N}$ then $$P_1(x)-P_2(x)=0$$ implies that the polynomial on the LHS has infinite roots, that is just possible if the polynomial on the left is strictly $0.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.