загрузка...
 
Теория множеств и комбинаторика *
Повернутись до змісту

Теория множеств и комбинаторика *

Подсчитаем, сколько подмножеств имеет конечное множество (в число подмножеств мы включаем и пустое множество, и само множество). Множество, состоящее из одного элемента а, имеет два подмножества: 0 и {а}. Множество, состоящее из двух элементов а и Ь, имеет уже четыре подмножества: те же подмножества 0 и {а} и еще {Ь} и {а, Ь}. Если прибавить к множеству третий элемент с, то кроме уже найденных четырех подмножеств 0, {а}, {Ь} и {а, Ь} появятся еще четыре подмножества: {с}, {а, с}, {Ь, с} и {а, Ь, с}, получаемые добавлением элемента с к каждому из имевшихся ранее подмножеств. Ясно, что каждый раз добавление нового элемента удваивает число подмножеств. Поэтому множество, содержащее п элементов, имеет 2” подмножеств.

Подмножества конечного множества можно расклассифицировать по числу входящих в них элементов. Если множество содержит п элементов, то его подмножества, состоящие из к элементов, называются сочетаниями из п по к. Их число обозначается С”. Так как общее число подмножеств равно 2”, то справедливо равенство

С0 + С1 + ... + Ск + ... + С” = 2”.

Для чисел С^ существует немало любопытных соотношений, многие из которых удается вывести, рассматривая некоторые подмножества с определенными свойствами. Докажем, например, соотношение

Ск = Ск-1 + Ск_!   (1)

в предположении 1 ^ к < п. С этой целью среди всех сочетаний из п элементов ах, ..., а„ по к выберем сочетания, содержащие


элемент а„. Остальные к — 1 мест в сочетании могут занимать любые из п — 1 элементов ах, ..., а„_1. Поэтому число выбранных сочетаний равно С”-1. Теперь подсчитаем, сколько сочетаний из элементов а!, ..., а„ по к не содержат элемента а„. Эти сочетания составлены из элементов ах, ..., а„_1. Так как в сочетание входят к элементов, то число таких сочетаний равно С^_]_. Поскольку в каждое из С^ сочетаний либо входит, либо не входит элемент а„, то должно выполняться равенство (1).

Отметим еще, что С0 = 1 при любом п ^ 0, так как каждое множество имеет лишь одно пустое подмножество. Точно так же очевидно, что С” = 1.

Пользуясь сделанными замечаниями, можно последовательно подсчитывать числа С^ сначала при п = 0, потом при п = 1, потом при п = 2 и т. д. Таблица чисел С^ записывается обычно в виде

С0 С0 с!

а>0

с2   С2 С2

/">0 /">1 /">2 /">3

С3 С3 С3 С3

(так называемый треугольник Паскаля).

Так как С0 =  = 1, то на сторонах треугольника Паскаля стоят

единицы. А остальные числа последовательно вычисляем, учитывая, что в силу соотношения (1) каждое число равно сумме чисел, стоящих в предыдущей строке слева и справа от него. В результате получаем следующую таблицу:

1

11 121 1331 1 4    6    4    1

5    10 10     5    1

Существует формула для непосредственного вычисления чисел Ск. Она имеет вид

п!

=

к!(п — к)!’’

где к! = 1 • 2 • ... • к и 0! = 1. Предоставляем читателю проверить, что определяемые этой формулой числа действительно удовлетворяют соотношению (1) и равенствам С0 = С” = 1.



загрузка...