WikiSort.ru - Не сортированное

Биективное доказательство

Заметим, что две величины, для которых мы доказываем равенство, подсчитывают число подможеств размера k и n − k соответственно любого n-элементного множества S. Существует простая биекция между двумя семействами F_k и F_n − k подмножеств S — она связывает каждое k-элементное подмножество с его дополнением, которое содержит в точности оставшиеся n − k элементов множества S. Поскольку F_k и F_n − k имеют одинаковое число элементов, соответствующие биномиальные коэффициенты должны быть равны.

Биективное доказательство

Доказательство. Мы считаем число способов выбрать k элементов из n-элементного множества. Снова, по определению, левая часть равенства равна числу способов выбора k элементов из n. Поскольку 1 ≤ k ≤ n − 1, мы можем фиксировать элемент e из n-элементного множества, так что оставшееся подмножество не пусто. Для каждого k-элементного множества, если e выбрано, существует

${\displaystyle {n-1 \choose k-1}}$

способов выбора оставшихся k − 1 элементов среди оставшихся n − 1 возможностей. В противном случае имеется

${\displaystyle {n-1 \choose k}}$

способов выбора оставшихся k элементов среди оставшихся n − 1 возможностей. Тогда есть

${\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}$

способов выбора k элементов.${\displaystyle \Box }$