Формулы комбинаторики и их применение¶

Формулы комбинаторики — это математические выражения, позволяющие вычислять число способов выбора, упорядочивания или распределения элементов конечного множества. Комбинаторика как раздел дискретной математики опирается на несколько базовых формул: правило суммы и произведения, формулы для перестановок, размещений и сочетаний, а также производные от них выражения с повторениями. Эти формулы лежат в основе теории вероятностей, статистики, криптографии, информатики и многих прикладных дисциплин.

¶Основные правила

Два исходных принципа, из которых выводятся почти все комбинаторные формулы, — правило суммы и правило произведения.

Правило суммы. Если объект A можно выбрать m способами, а объект B — n способами, причём выборы взаимно исключают друг друга (нельзя выбрать оба одновременно), то выбор «A или B» осуществляется m + n способами.

Правило произведения. Если объект A выбирается m способами и после каждого такого выбора объект B — n способами, то выбор пары (A, B) возможен m × n способами. Именно это правило даёт формулу для числа размещений и перестановок.

¶Факториал

Ключевой элемент большинства формул — факториал натурального числа n, обозначаемый n! и равный произведению всех натуральных чисел от 1 до n:

n! = 1 × 2 × 3 × … × n.

По определению 0! = 1. Факториал растёт чрезвычайно быстро: 5! = 120, 10! = 3 628 800, а 20! превышает 2,4 × 10¹⁸. Это отражает комбинаторный взрыв — стремительный рост числа вариантов при увеличении размера множества.

¶Перестановки

Перестановка — упорядоченный набор всех n элементов множества без повторений. Число перестановок обозначается Pₙ и вычисляется по формуле:

Pₙ = n!

Например, число способов расставить 4 книги на полке равно 4! = 24. Если среди элементов есть одинаковые (перестановки с повторениями), формула принимает вид:

P(n₁, n₂, …, nₖ) = n! / (n₁! × n₂! × … × nₖ!),

где n₁ + n₂ + … + nₖ = n. Так, число различных слов из букв слова «МАМА» равно 4! / (2! × 2!) = 6.

¶Размещения

Размещение — упорядоченная выборка k элементов из n, где порядок важен и элементы не повторяются. Число размещений:

Aⁿₖ = n! / (n − k)!

Эту величину также обозначают A(n, k) или через убывающий факториал. Пример: число способов распределить три призовых места среди 10 участников равно A¹⁰₃ = 10! / 7! = 10 × 9 × 8 = 720.

Размещения с повторениями допускают возврат элемента. Тогда число вариантов равно:

Āⁿₖ = nᵏ.

Например, число трёхзначных кодов из цифр 0–9 (с возможными повторами) составляет 10³ = 1000.

¶Сочетания

Сочетание — неупорядоченная выборка k элементов из n, где порядок не важен. Число сочетаний обозначается Cⁿₖ (или «n choose k») и вычисляется так:

Cⁿₖ = n! / (k! × (n − k)!)

Эту же величину записывают как биномиальный коэффициент. Пример: число способов выбрать 3 делегата из 10 человек равно C¹⁰₃ = 120. Сочетания связаны с размещениями соотношением Aⁿₖ = Cⁿₖ × k!, поскольку каждую неупорядоченную выборку можно упорядочить k! способами.

Сочетания с повторениями (выбор с возвратом, порядок не важен) считаются по формуле:

C̄ⁿₖ = C(n + k − 1, k) = (n + k − 1)! / (k! × (n − 1)!)

Так, число способов купить 5 пирожных из 3 сортов равно C(7, 5) = 21.

¶Сводная таблица

¶Бином Ньютона и треугольник Паскаля

Биномиальные коэффициенты возникают в разложении степени суммы:

(a + b)ⁿ = Σ Cⁿₖ × aⁿ⁻ᵏ × bᵏ.

Коэффициенты этого разложения удобно находить через треугольник Паскаля, где каждое число равно сумме двух стоящих над ним. Свойства коэффициентов включают симметрию Cⁿₖ = Cⁿₙ₋ₖ и рекуррентное соотношение Cⁿₖ = C(n−1, k−1) + C(n−1, k).

¶Применение

Формулы комбинаторики используются при подсчёте вероятностей по классическому определению (отношение числа благоприятных исходов к общему числу), в задачах теории графов, при анализе алгоритмов, в генетике (комбинации аллелей), в криптографии (оценка стойкости ключей) и в статистике. В школьном курсе математики комбинаторика входит в раздел теории вероятностей и статистики.

Отдельно выделяют принцип Дирихле и включений-исключений, дополняющие базовые формулы. Формула включений-исключений позволяет считать мощность объединения множеств:

|A₁ ∪ … ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + … + (−1)ⁿ⁻¹|A₁ ∩ … ∩ Aₙ|.

¶Историческая справка

Отдельные комбинаторные задачи решались ещё в Древнем Китае и Индии. Как самостоятельная дисциплина комбинаторика оформилась в XVII веке в работах Блеза Паскаля и Пьера Ферма, связанных с теорией азартных игр. Термин «комбинаторика» закрепился в XVIII веке, а систематическое изложение формул дал Леонард Эйлер. В России значительный вклад в комбинаторный анализ внесли математики XIX–XX веков, развивавшие теорию перечислений и её приложения.

Источники: учебники по дискретной математике, теория вероятностей, комбинаторный анализ.