Сочетания

Свойства сочетаний

Числа Ckn обладают целым рядом замечательных свойств. Эти свойства можно доказать по-разному. Можно доказывать алгебраически – прямо воспользоваться формулой (8)

Но можно эти же свойства доказывать и чисто комбинаторными соображениями.

Свойствo 1

(9).

Алгебраическое доказательство:

В формулу для Ckn верхним индексом подставим (n-k). Получим

Однако намного изящнее комбинаторное доказательство:

Что значит «выбрать n-k предметов из n»? Это все равно что «указать k предметов, которые не будут выбраны». Т.е. выбрать n-k предметов из n можно столькими же способами, что и k предметов.

Этим свойством удобно пользоваться, когда верхний индекс ненамного меньше нижнего. Сравните, к примеру, два способа вычисления C57:

напрямую используя формулу (8):

или применяя формулу (9):
Не правда ли, второй проще?

Свойство 2

(10).

Алгебраическое доказательство:

Запишем правую часть, используя формулу (8) для числа сочетаний:

Приведем к общему знаменателю, равному n!∙(n-k)!:

Однако и здесь комбинаторное доказательство намного красивее:

Все сочетания из n по k (их количество равно Ckn ) можно разбить на два класса: содержащие элемент под номером n и не содержащие его.

Выбрать из n элементов k штук, включая n-й – это все равно, что из оставшихся n-1 элементов выбрать k-1. Это можно сделать Ck-1n-1 способами.

Если же n-й элемент в сочетание не входит, то все k элементов нужно выбирать из оставшихся n-1 элементов. Это можно сделать Ckn-1 способами.

Так как каждое сочетание из n по k входит или в один, или в другой класс, но не в оба сразу, можно применить правило суммы, и получить доказываемое равенство:

(10).

Свойство 3

(11).

Доказательство (комбинаторное):

В левой части равенства стоит количество всех сочетаний из n элементов (независимо от числа элементов в самих сочетаниях).

О каждом элементе мы можем принять решение: брать его в сочетание или не брать. Т.е. для каждого элемента есть два варианта решения: «да» и «нет». Будем для обозначения того или иного сочетания класть на каждый элемент монетку, причем «да» будем обозначать орлом, а «нет» – решкой. Таким образом, каждому сочетанию из n элементов будет соответствовать ряд из n монет. В разделе «Основные законы комбинаторики» мы доказали, что для n монет возможны 2n вариантов распределения орлов и решек. Поэтому количество всех сочетаний из n элементов равно 2n, что и требовалось доказать.

Страницы: 1 2 3