Комбинаторика
Комбинаторика исследует конечные конфигурации и способы их построения или подсчёта. Если порядок элементов важен, задача может считать последовательности; если важен только состав выбранного набора — подмножества.
Более сложные методы используют биекции, рекуррентные соотношения и производящие функции: один и тот же объект можно посчитать двумя способами и получить тождество. Комбинаторика также изучает структуру объектов, например графов, а не только формулы для перестановок и сочетаний.
Комбинаторика
Перестановки
Упорядоченные расположения n элементов. Pₙ = n! (факториал). Перестановки с повторениями: n!/(k₁!k₂!...kₘ!).
Размещения
Упорядоченные выборки k элементов из n. Aₙᵏ = n!/(n-k)!. С повторениями: nᵏ.
Сочетания
Неупорядоченные выборки k из n. Cₙᵏ = n!/(k!(n-k)!). Бином Ньютона: (a+b)ⁿ = ΣCₙᵏaⁿ⁻ᵏbᵏ.
Принцип включения-исключения
Формула для мощности объединения: |A∪B| = |A| + |B| - |A∩B|. Обобщение на n множеств, решето Эратосфена.
Перестановки и сочетания
Перестановки P(n,k) = n!/(n-k)! — упорядоченные выборки. Сочетания C(n,k) = n!/(k!(n-k)!) — неупорядоченные. Формулы подсчёта вариантов в вероятности, криптографии.
Производящие функции
Формальные степенные ряды для кодирования последовательностей. Сложение → умножение рядов. Решение рекуррентных соотношений, подсчёт комбинаторных объектов.