Облако знаний. Число сочетаний. Математика. 10 класс

Число сочетаний

Сочетанием из n элементов по k $(k < n)$ называется любое множество, составленное из k элементов, выбранных из данных n элементов (не имеет значения, в каком порядке указаны элементы).
Количество сочетаний всех неупорядоченных k-элементных подмножеств n‑элементного множества равно:
$C_{n}^{k} = \frac{A_{n}^{k}}{P_{k}} = \frac{n!}{(n - k)! k!},$
где $A_{n}^{k}$ – число размещений из n элементов по k, $P_{k}$ – значение перестановок.
Пример. Из 8 фотографий нужно отобрать 3 на стенд. Сколькими способами это можно сделать?
$C_{8}^{3} = \frac{8!}{(8 - 3)! 3!} = \frac{6 \cdot 7 \cdot 8}{1 \cdot 2 \cdot 3} = 56$ – количество способов отбора.
Свойства чисел сочетаний:
- $C_{N}^{0} = C_{N}^{N} = 1$ . Это свойство следует из общей формулы.
- $C_{N}^{1} = C_{N}^{N - 1} = N$ . Чтобы выбрать (N – 1) элементов из N, нужно указать один элемент, который не выбран, что можно сделать тоже N способами.
- $C_{N}^{k} = C_{N}^{N - k}$ , для любого $0 \leq k \leq N$ . Выбрать (N – 1) элементов из N можно таким же количеством способов, каким указать k элементов, которые не выберем.
- $C_{N}^{0} + C_{N}^{1} + C_{N}^{2} + \dots + C_{N}^{N - 1} + C_{N}^{N} = 2^{N}$ – сумма ряда.
- $C_{N}^{k} = C_{N - 1}^{k - 1} + C_{N - 1}^{k}$ . Рекуррентный способ вычисления, т. е. получение новых чисел с большими значениями N через предыдущие числа с меньшими значениями N.

Было полезно?