Сочетания

Сочетания объема k из n-множества X – это неупорядоченные выборки вида {a1, a2,…, ak}, где ai, i = 1, 2,…, k, – попарно различные элементы множества X.

В соответствии с определением сочетания объема k – это

k-подмножества множества X. Число сочетаний объема k из

n

или через 

 и называют

числом сочетаний из n по k.

k 

0  1,

C1  n ,

n  1. Чтобы получить

формулу для числа сочетаний в общем случае, докажем

сначала, что при k ≤ n справедливо следующее соотношение:

⋅Pk .

В самом деле, пусть X – n-множество. Каждому размещению

(a1, a2,…, ak)

поставим в соответствие сочетание

{a1, a2,…, ak}.

Одно и то же сочетание {a1, a2,…, ak} соответствует всем размещениям, полученным перестановкой элементов a1, a2,…, ak. Число таких перестановок равно Pn. Таким образом, вся совокупность размещений по k элементов разбивается

на C k

классов, каждый из которых содержит P

размещений.

n n

Отсюда и следует доказываемая формула.

Используя (6), (7) получаем выражение для числа сочетаний

«в факториалах»:

n k!(n − k )!

Часто используется и следующее соотношение:

n k!

Пример.Найдем число сочетаний из 52 по 26.

В соответствии с (9) имеем:

52 (26!)2 .

Используя формулу Стирлинга можно получить

приблизительную оценку:

– (ln 2 + ln 26) – 52(ln 26 –1)

= 53ln 2 – 0,5ln(52⋅2) ≈ 33,84.

Значит,

26 33,84 14

C52 ≈ e

≈ 4,98⋅10

Пример.Найдем число монотонно возрастающих отображений из множества

X = {1 ,2 ,…, k}

в множество

Y = {1 ,2 ,…, n}.

Любое такое отображение f задает набор чисел

f(1) < f(2) < … <f(k).

Обратно, любое k-подмножество Y′ = {y1, y2,…, yk} множества Y однозначно определяет монотонно возрастающее отображение из X в Y, для которого f(X) = Y′ . В самом деле, упорядочим элементы множества Y′ по возрастанию так, что Y′ = {y1, y2,…, yk}, причем y1 < y2 <…< yk. Полагая f(i) = yi, получаем соответствующее отображение. Таким образом, число

монотонно возрастающих отображений из X в Y равно числу

из n по k.

– числу сочетаний

Рассмотрим теперь вопрос о числе сочетаний с повторениями. Сочетания с повторениями объема k из n-множества X – это неупорядоченные выборки вида a1 a2… ak, где ai, i = 1, 2,…, k, – произвольные элементы множества X,

среди которых могут быть и совпадающие. Примерами сочетаний с повторениями из элементов a, b, c, d по три могут служить выборки aaa; aab; dab.

Предположим для определенности, что X = {1, 2,…, n}. Сочетание с повторениями из элементов множества X однозначно определяется упорядоченным набором неотрицательных целых чисел (x1, x2,…, xn), где xi, i = 1, 2,…, n, равно числу вхождений в выборку элемента i. Например, выборка 1, 3, 2, 1, 3, 3 из множества X = {1, 2, 3, 4} задается набором (2, 1, 3, 0), поскольку 1 встречается в ней два раза, 2 – один раз, 3 – три раза, и 4 – ни разу. Сумма x1 + x2 +…+ xn – это объем выборки. Таким образом, число сочетаний с повторениями из n элементов по k равно числу решений

уравнения

x1 + x2 +…+ xn = k (11)

в целых неотрицательных числах. Сделаем замену неизвестных. Пусть yi =xi + 1. Относительно новых неизвестных уравнение (11) запишется в следующем виде:

y1 + y2 +…+ yn = n + k. (12)

Нас интересует число решений этого уравнения в целых положительных числах. Если взять строчку из n + k точек и в промежутках между ними поставить n – 1 разделительную черточку, то можно считать y1 числом точек в первой группе, y2 – числом точек во второй группе и т. д.:

....|.....|L|.... .

y1 y2 yn

Таким образом, число решений уравнения (12) равно числу способов расставить n – 1 черточек в n + k – 1 промежутках между точками. Число способов выбрать n – 1 промежутков (в

которые ставятся черточки) из n + k – 1 промежутков равно

C n −1 −1 .

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

монет по трем карманам. Каждый расклад монет представляет собой сочетание с повторениями из трех элементов по 10. Каждый «карман» входит в выборку столько раз, сколько монет в него положено. Таким образом, искомое число способов

расклада равно

2  12⋅11  66 .

Используя сочетания можно получить новое обоснование формулы для числа перестановок с повторениям (8). В самом деле, пусть рассматриваются перестановки с повторениями типа (n1, n2,…, nk) из элементов множества X = {x1, x2,…, xk}. Для определенности будем считать, что k = 3. Чтобы составить перестановку с повторениями, нужно указать места, на которых расположены элементы x1; места, на которых расположены элементы x2, места, на которых расположены элементы x3. Для расстановки элементов x1 можно выбрать любые n1

из n1 + n2 +…+ nk мест. Это можно сделать

C n1

n1 n2 Knk

способами. Элементы x2 можно расставлять на незанятые места,

которых остается n2 +…+ nk. Значит, места для элементов x2

можно выбрать

C n2

n2 Knk

способами. Продолжая подобным

образом, приходим к тому, что элементы xk–1 должны быть расставлены на nk–1 + nk мест, а элементы xk – на оставшиеся nk

мест. По правилу произведения получаем:

n1 n2 Knk

⋅C n2

⋅ ⋅C nk .

nk

Если теперь записать числа сочетаний в факториалах, то

после сокращений получится (8).

 P(k , n − k ) .

Непосредственно из формулы (8) легко усмотреть, что при любых n и k, 0 ≤ k ≤ n, верно равенство

Если 0 ≤ k < n, то

k  C n − k

C k 1 . (14)

С использованием (9) доказательство может быть получено

непосредственной проверкой:

n! 

k!(n − k )!

n!

(k 1)!(n − k − 1)!

 n!(k 1)  n!(n − k ) 

(k 1)!(n − k )!

 n!(n 1) 

(n 1)!

k 1.

Сумма

(k  1)!(n − k )!

 Cn1

(k 1)!(n − k )!

0 1 2 n

Cn  Cn  Cn

... Cn

(15)

плюс число одноэлементных подмножеств C1

и т. д.). Как было установлено ранее, n-множество имеет 2n

подмножеств. Следовательно,

0 1 2 n n

Cn  Cn  Cn

... Cn  2

. (16)

Впрочем, с использованием (14) формула (16) может быть получена по индукции. При малых значениях n справедливость (16) легко проверяется непосредственно.

Индуктивный шаг сводится к следующей несложной выкладке:

n 1

 n 1

 n 1

 ... 

n 1

 C 0

 (C 0  C1 )  (C1  C 2 )  ...  (C n −1  C n )  C n 1 

n n n 1

 C1 ... C n ) 

n n n

n 1

n 1 n n

 2(C 0  C1  C 2 ... C n ).

n n n n

В последнем переходе использовалось то, что

и C 0 1 1 C 0 .

C n 1  1  C n n 1 n

n  n

Формула (14) позволяет последовательно заполнять строки таблицы, называемой треугольником Паскаля. Рассмотрим

первые пять строк этой таблицы:

0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

В строке с номером n (указанном слева от вертикальной

черты) расположены числа

C 0 ,

C1 , …, C n . В соответствии

n n n

с (14), складывая два соседних числа в строке n, мы получим число в строке n + 1, стоящее под правым слагаемым.

Рассмотрим бином (x + y)n. Для любого целого

неотрицательного числа n имеет место следующее тождество:

(x  y)n 

∑C k xn−k y k , (17)

или в развернутом виде:

k 0

(x  y)n

 C 0 xn y0  C1 xn −1 y1 ... C n x0 y n ,

n n n

называемое формулой Ньютона.

Доказательство этого факта несложно провести по индукции, используя (14). Формула Ньютона, очевидно, верна при n = 0. Чтобы выполнить индуктивный шаг, в равенстве

(x + y)n+1 = (x + y)n(x + y)

заменим (x + y)n суммой из правой части (17). После раскрытия скобок и приведения подобных получаем:

(x  y)n1 

 0 n

0  ∑

k n −k k 

k −1

n−k 1

k −1

n 0 n 

xCn x y

n

xCn x y

yCn x y

yCn x y

 xn1 

∑C k

 C k −1xn−k 1y k

 y n 1

В соответствии с (14),

k 

так что

Cn Cn

Cn 1

xn 1 y0  C1

x n y1  ...  C n 1x0 y n 1

и, следовательно, формула Ньютона верна и при показателе степени равном n + 1.

Подставка в формулу Ньютона конкретных числовых значений переменных позволяет получать различные

тождества. Вот некоторые из них:

n

k n

∑ Cn  2 ;

k  0

n

 0 ;

k 0

n

 3n .

k 0

В первом случае (полученное тождество совпадает с (16)) мы подставили в (17) x = 1, y = 1; во втором – x = 1, y = –1; в третьем – x = 1, y = 2.