2.2. Сочетания

Сочетанием элементов множества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

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

n k	0	1	2	3	4	5
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6

Теорема 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элементов.

Применение сочетаний. Сочетание можно интерпретировать как размещение без повторений неразличимых предметов в ящиках.

Пример 1. Найдем вероятность угадать 7 номеров из 49 (игра спортлото). Количество вариантов равно числу сочетаний из 49 элементов по 7. Существует единственный благоприятный вариант. Отсюда вероятность равна .

Теорема 4. Число возрастающих функций f: {1, 2, , k}  {1,2,  , n} равно .

Доказательство. Каждой возрастающей функции сопоставим ее образ {f(1),f(2),, f(k)}{1,2, …,n}. Получим биекцию между возрастающими функциями и подмножествами множества {1, …,n}, состоящими изkэлементов. Согласно определению сочетания, число таких подмножеств равно числу сочетаний .

Замечание. Возрастающая функция задается возрастающей последовательностьюkчисел. Отсюда число возрастающих последовательностейx₁ < …<x_kчисел, принадлежащих множеству {1, 2, …,n}, будет равно .

Теорема 5. Число последовательностей натуральных чисел (x₁ , x₂ ,  , x_k), x_i1, удовлетворяющих уравнению

x₁ + x₂ +  + x_k=n,

равно .

Доказательство. Каждой последовательности (x₁ , x₂ ,  , x_k), удовлетворяющей данному уравнению сопоставим возрастающую последовательностьy₁ =x₁ , y₂=x₁+ x₂ ,  , y_k-1 = x₁+ x₂ +…+x_k-1. Наоборот, каждой возрастающей последовательностиy₁< …<y_k-1<nможно сопоставить решение данного уравнение, состоящее из чиселx₁=y₁,x₂=y₂-y₁, …,x_k-1=y_k-1-y_k-2,x_k=n-y_k-1. Получаем биекцию между решениями данного уравнения и возрастающими последовательностями, состоящими изk-1 чисел принимающих значения 1, 2, …,n-1. По теореме 4 число таких возрастающих последовательностей равно .

Теорема 6. Число неубывающих сюръекций{0,1,  , n –1}  {0, 1,  , k–1 }равно.

Доказательство.Каждая сюръекция задает разбиение множества {0, 1,  , k–1 } на подмножестваf ^─1(0) , f ^─1(1),  , f ^─1(n –1). Пустьm₀– наибольший вf ^─1(0),m₁– наибольший вf ^─1(1) ,, m_n-2– наибольший вf^─1(n –2). Тогдаm_n-1 = k – 1. Следовательно,

0 ≤ m₀ < m₁ <  < m_n-2 ≤ k-2.

Число таких последовательностей равно – количеству возрастающих функцийn–1  k–1.