Numbers and Sets | Part IA, 2005

Give a combinatorial definition of the binomial coefficient (nm)\left(\begin{array}{l}n \\ m\end{array}\right) for any non-negative integers n,mn, m.

Prove that (nm)=(nnm)\left(\begin{array}{c}n \\ m\end{array}\right)=\left(\begin{array}{c}n \\ n-m\end{array}\right) for 0mn0 \leq m \leq n.

Prove the identities

(nk)(kl)=(nl)(nlkl)\left(\begin{array}{l} n \\ k \end{array}\right)\left(\begin{array}{l} k \\ l \end{array}\right)=\left(\begin{array}{l} n \\ l \end{array}\right)\left(\begin{array}{l} n-l \\ k-l \end{array}\right)


i=0k(mi)(nki)=(n+mk)\sum_{i=0}^{k}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n \\ k-i \end{array}\right)=\left(\begin{array}{c} n+m \\ k \end{array}\right)

Typos? Please submit corrections to this page on GitHub.