Arrangements and Combinations · Combinations

Lesson 9

Nikolai Chukhin · Alexander S. Kulikov

Fix one person—for example, Alice. Then all possible teams of \(k\) people are divided into two types:

  1. Teams that include Alice. There are \(\binom{n-1}{k-1}\) of them.
  2. Teams that do not include Alice. There are \(\binom{n-1}{k}\) of them.
Therefore, \[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\] We have obtained a combinatorial proof of this equality. It is called combinatorial because we proved it not through algebraic manipulations but by giving a combinatorial meaning to both parts. The method used here is known as the distinguished element method.

Now consider Pascal's triangle: on the \(n\)-th row, from left to right, the values of \(\binom{n}{k}\) for all \(k\) from 0 to \(n\) are arranged.