# Combinatorics. Falling factorial problem

Let $(n)_k = n(n-1)(n-2)...(n-k+1)$

(Evidently this is a falling factorial with $0 \le k \le n$).

Need to give a combinatorial proof of the following

$$(n)_k = \sum_{i=1}^{k} \binom ki (n-m)_i (m)_{k-i}$$

-
What is $m$?${}{}$ – Brian M. Scott Feb 18 '13 at 4:03
Have no idea. Maybe there is a mistake in the question, because it might ask to prove the combinatorial interpretation of the falling factorial which is $(x+y)_k = \sum_{i=0}^{k} \binom{k}{i} x_{i} y_{k-i}$. Only in our question $i=1$, not $0$... – John Lennon Feb 18 '13 at 4:22
It turns out not to matter, at least as long as $0\le m\le n$. And I’m pretty sure that that lower limit of $1$ is wrong: see the example in my answer. – Brian M. Scott Feb 18 '13 at 4:43

I prefer the notation $n^{\underline k}$ for the falling factorial; in that notation the desired identity becomes

$$n^{\underline k}=\sum_{i=1}^k\binom{k}i(n-m)^{\underline i}m^{\underline{k-i}}\;.\tag{1}$$

The lefthand side is clearly the number of ways to choose a sequence of $k$ distinct elements of $[n]=\{1,\dots,n\}$. If $a=\langle a_1,\dots,a_k\rangle$ is such a sequence, let $I(a)=\{j\in[k]:a_j\le n-m\}$, and let $i(a)=|I(a)|$.

Clearly $a$ is completely determined by the set $I(a)$ and the subsequences $a_L=\langle a_j:j\in I(a)\rangle$ and $a_H=\langle a_j:j\in[k]\setminus I(a)\rangle$. There are $(n-m)^{\underline{i(a)}}$ possible choices for $a_L$, $m^{\underline{k-i(a)}}$ possible choices for $a_H$, and $\binom{k}{i(a)}$ possible choices for $I(a)$. Now sum over the possible values of $i(a)$ to get the righthand side.

However, it appears that the lower limit of the summation should be $0$, not $1$, both from the argument given above and from the case $n=m=k=1$: the lefthand side of $(1)$ is $1$, but the righthand side as written is $\binom110^{\underline 1}1^{\underline 0}=0$. The correct identity is then

$$n^{\underline k}=\sum_{i=0}^k\binom{k}i(n-m)^{\underline i}m^{\underline{k-i}}\;.$$

-