Properties of Combinations

Five standard identities let a combination be simplified or compared without full expansion.

Property 1. (i) $^nC_0=1$, (ii) $^nC_n=1$, (iii) $^nC_r=\dfrac{n(n-1)(n-2)\cdots(n-r+1)}{r!}$.

Proof. $^nC_0=\dfrac{n!}{0!\,n!}=1$; $^nC_n=\dfrac{n!}{n!\,0!}=1$; and cancelling the common $(n-r)!$ in $\dfrac{n!}{r!(n-r)!}$ leaves exactly the first $r$ descending factors of $n!$ over $r!$.

Property 2 (symmetry). $^nC_r={}^nC_{n-r}$.

Proof. $^nC_{n-r}=\dfrac{n!}{(n-r)!(n-(n-r))!}=\dfrac{n!}{(n-r)!\,r!}={}^nC_r$.

Property 3. If $^nC_x={}^nC_y$ then either $x=y$ or $x+y=n$.

Proof. By Property 2, $^nC_y={}^nC_{n-y}$; combined with $^nC_x={}^nC_y$ this gives $^nC_x={}^nC_{n-y}$, which forces $x=y$ or $x=n-y$ (i.e. $x+y=n$).

Property 4 (Pascal's rule). $^nC_r+{}^nC_{r-1}={}^{n+1}C_r$.

Proof. Writing both terms with a common factor of $\dfrac{n!}{(r-1)!(n-r)!}$ and combining $\dfrac1r+\dfrac1{n-r+1}=\dfrac{n+1}{r(n-r+1)}$ collapses the sum to $\dfrac{(n+1)!}{r!(n+1-r)!}={}^{n+1}C_r$.

Property 5. $^nC_r = \dfrac nr\times{}^{n-1}C_{r-1}$.

Proof. $\dfrac nr\times{}^{n-1}C_{r-1}=\dfrac nr\times\dfrac{(n-1)!}{(r-1)!(n-r)!}=\dfrac{n(n-1)!}{r(r-1)!(n-r)!}=\dfrac{n!}{r!(n-r)!}={}^nC_r$.

A telescoping consequence. Repeated use of Property 4 collapses sums like $^aC_r+{}^{a+1}C_r+{}^{a+2}C_r+\cdots+{}^bC_r$ down to a single term $^{b+1}C_{r+1}-{}^aC_{r+1}$ — the standard trick behind identities such as $^{15}C_3+2\!\times\!{}^{15}C_4+{}^{15}C_5={}^{17}C_5$ (group the middle term with each neighbour and apply Pascal's rule twice). …