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

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.

## 1 Answer

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.$$