Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Please help.

share|improve this question
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
add comment

1 Answer

up vote 3 down vote accepted

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}}\;.$$

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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