флеров

Сочетания и биномиальные коэффициенты.

Простейшими комбинаторными объектами являются сочетания и биномиальные коэффициенты.

Пусть дано конечное множество X , содержащее n различных элементов. Нас интересует количество различных k- элементных подмножеств, которые можно образовать из элементов множества X. Два подмножества считаются различными, если они различаются хотя бы одним входящим в них элементом.

Такие подмножества называются сочетаниями из m элементов по k элементов и обозначаются , а их количество обозначается или . Обозначение читается как “число сочетаний из m по k “ или просто “из m по k”.

Утверждение 1.8. Число различных подмножеств из k элементов множества A, |A |= m есть

Первое доказательство.

Построим таблицу T всех строго возрастающих (монотонных, без повторений букв) слов длины k в алфавите A из m букв.

Пример.

Пусть множество A состоит из пяти различных элементов:

A= {a,b,c,d,c} .

Положим k=3.

Тогда таблица T всех строго возрастающих слов длины 3 в алфавите A имеет следующий вид:

abc acd adc

abd ace

abe

bcd bde

bce

cde 

Переставим буквы в каждом слове всеми возможными способами и обозначим получившуюся таблицу T^. T^ - множество слов без повторения букв длины k в алфавите A.

В таблице T^ нет пропусков: каждое слово длины k появится в таблице T^.

В таблице T^нет повторений: два слова из T^ либо получены из одного слова T и тогда отличаются порядком букв, либо из разных слов T и тогда различаются буквами.

По утверждению 1 .2:

| T^ | = [ m ]_k .

Поэтому

| T | = [ m ]_k/ k! .

Таким образом, окончательно получаем

Второе доказательство.

Определим множество (иногда обозначаемое как-нибудь иначе) как множество всех k-элементных подмножеств (или k-подмножеств) множества S и положим по определению (игнорируя прошлое использование символа ). Подсчитаем двумя способами число N(n, k) способов, которыми можно выбрать k-подможество T множества S, а затем линейно упорядочить его элементы. Множество T мы можем выбрать способами, а затем k способами выбрать первый по порядку элемент множества T, k-1 способом - второй элемент T и так далее. Таким образом

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

N(n, k) = n(n - 1) ... (n - k + 1).

Итак, мы дали комбинаторное доказательство того, что

и, следовательно,

. 

Прежде, чем двигаться дальше сделаем небольшое отступление, связанное с введением понятия производящих функций.

Содержание