Треугольник Паскаля и бином Ньютона.

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

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

Доказательство. Число сочетаний, не содержащих n-й элемент, равно , а содержащих – .

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

n k

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

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

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

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