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

Пример 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.

Пример 2. Число неубывающих сюръекций n ® 1 равно .

Число неубывающих сюръекций 3 ® 2 равно .

Сочетания с повторениями. Сочетанием с повторением из множества { e₁ , e₂ , ×××, e_n } называется линейная комбинация x₁e₁ + x₂e₂ + ××× +x_n e_n, состоящая из x₁ элементов e₁ , из x₂ элементов e₂ ,×××, из x_n элементов e_n, где x_i ≥ 0 – неотрицательные целые числа. Если x₁ + ××× +x_n = k, то оно называется сочетанием с повторениями из n по k.

Пусть, например, имеется 3 цвета: красный, зеленый, синий. Интенсивности этих цветов равны. Сколько смесей суммарной интенсивности 10 можно получить, смешивая x₁ красных, x₂ зеленых и x₃ синих цвета?

Лемма 1. Пусть - число сочетаний с повторениями из n по k. Тогда равно числу неубывающих функций {1,2, ×××, n-1} ® {0,1,2, ×××, n}

Доказательство.

Рис. 2.2. Решение уравнения x1 + ××× +xn = k

Каждому решению x₁ + ××× +x_n = k соответствует неубывающая последовательность y₁ ≤y₂ ≤ _{× × ×} ≤y_n-1, где y₁=x₁, y₂ = y₁+x₂, ×××, y_n-1 = y_n-2 + x_n-1.

Теорема 7. .

Доказательство. Рассмотрим график неубывающей функции

Рис. 2.3. График неубывающей функции

График задается последовательностью из 0 и 1

0 0 1 1 0 0 … 0 1 0 0 … 1 1 … 1

состоящей из n-1+k разрядов, имеющих k единиц.

Следствие 1. равно числу неубывающих функций

{1,2, ×××, k } ® {1,2, ×××, n }.

Доказательство. Первый способ: транспонировать графики. Если график, показанный на рис.2.3, отразить относительно прямой y = x, то получим график функции {1,2, ×××, k } ® {1,2, ×××, n }. Это доказывает утверждение следствия.

Второй способ: число неубывающих функций {1,2, ×××, k } ® {1,2, ×××, n } равно = = .

Получаем следующую таблицу 2.2, содержащую числа конфигураций

Таблица 2.2

Число конфигураций

 

	функций m®n	неубывающих функций m®n
Всех	n^m
Инъективных
Сюръективных	?
Биективных	n!, если m=n, иначе 0	1, если m=n, иначе 0

Здесь m = {0,1, ×××, m-1}. Например, число неубывающих сюръективных отображений {0,1, ×××, m -1} ® {0,1, ×××, n -1} равно .