Сочетания

Сочетанием элементов множества X называется подмножество конечного множества AÍX. Если |A|=k, |X|=n, то подмножество X называется с очетанием из n по k. Например, сочетания трех цветов семицветной радуги будут описываться подмножествами, состоящими из трех элементов выбранных из множества, состоящего из 7 элементов.

Треугольник Паскаля и бином Ньютона. Для вычисления числа сочетаний построим таблицу, которая называется треугольником Паскаля. Она основана на следующей теореме:

Теорема 1. Число сочетаний удовлетворяет соотношениям:

; (при 0 < k < n).

Доказательство. Число пустых подмножеств равно 1. Стало быть, . Подмножества, состоящие из n элементов, совпадают со всем множеством, отсюда . Число сочетаний, не содержащих n -й элемент, равно , а содержащих – . Следовательно, при 0 < k < n,

Следующая таблица 2.1 строится на основе теоремы 1 и называется треугольником Паскаля.

Таблица 2.1

Треугольник Паскаля

Теорема 2. Число сочетаний из n по k равно .

Доказательство. По индукции по n. При n=0 и k=0 получаем . Пусть теорема верна для n. С помощью теоремы 1 получаем

.

Откуда формула верна для n +1 и всех k < n +1.

Другой способ доказательства заключается в сопоставлении каждой инъекции ее образ. В этом случае, учитывая, что число инъекций с одинаковым образом равно k!, получаем Þ .

Теорема 3. (Бином Ньютона).

Доказательство. По индукции по n. Пусть формула верна для n. Тогда

Можно предложить также другое доказательство: Рассмотрим произведение n сомножителей (1 +x) (1 +x) × × × (1 +x). Сомножители будем рассматривать как ящики. Произведение равно сумме степеней x^k, причем при каждом k слагаемые x^k получаются выбором из ящиков k элементов, равных x. Отсюда коэффициент при x^k будет равен количеству содержащих k элементов подмножеств множества, состоящего из n элементов.

Поиск по сайту: