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

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