$$\large{\displaylines{\Large \color{#ff7800}C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k} \\ \\ {\color{#ff7800}a_1: \ } \underbrace{a_{1},(n-1)}_{n} \quad \underbrace{a_{1},(k-1)}_{k} \\ \\ \xcancel{\color{#ff7800}a_1:} \underbrace{a_{1},(n-1)}_{n} \quad k}}$$
Рекуррентное свойство биномиальных коэффициентов
Разбиение множества на блоки
- Дано множество $\{a_1, \ldots, a_n \}$
- Разобьем множество всех сочетаний из $n$ по $k$ на два блока: в первом блоке будут все сочетания с элементом $a_1$, во втором блоке – все сочетания без элемента $a_1$
- Число сочетаний в первом блоке равно числу сочетаний из $(n-1)$ по $(k-1)$
- Число сочетаний во втором блоке равно числу сочетаний из $(n-1)$ по $k$