Рассматриваются перестановки, размещения, сочетания, деревья перестановок, кодирование сочетаний.

Основные определения и понятия

Перестановки (Permutations)

Определение: Упорядоченные arrangements из n различных элементов.

Формула:

Без повторений: Pₙ = n! = n×(n-1)×...×2×1
С повторениями: P(n₁,n₂,...,nₖ) = n!/(n₁!n₂!...nₖ!), где n₁+n₂+...+nₖ = n

Пример: Перестановки букв в слове "Миссисипи" (1 "м", 4 "и", 3 "с", 1 "п"):
P(4,3,1,1) = 9!/(4!3!1!1!) = 2520

Размещения (Arrangements)

Определение: Упорядоченные выборки из n элементов по m (m ≤ n). Учитывается и состав, и порядок элементов.

Формула:
Aₙᵐ = n!/(n-m)!

Сочетания (Combinations)

Определение: Неупорядоченные выборки из n элементов по m (m ≤ n). Учитывается только состав, порядок не важен.

Формула:
Cₙᵐ = n!/(m!(n-m)!)

Представление: Сочетаниям соответствуют двоичные последовательности длины n с m единицами.

Классификация комбинаторных задач на разбиение

Ключевые факторы различия:

Порядок элементов в группах (важен/не важен)
Порядок самих групп (важен/не важен)
Различимость элементов (различимы/неразличимы)
Различимость групп (различимы/неразличимы)
Допустимость пустых групп (да/нет)

Систематизация рассмотренных задач

Задача 1: Раскладка по ящикам

Элементы: различимы
Группы: различимы (ящики пронумерованы)
Порядок в группах: не важен
Размеры групп: фиксированы (n₁, n₂, ..., nₖ)

Формула: P(n₁,n₂,...,nₖ) = n!/(n₁!n₂!...nₖ!)

Задача 2: Перестановки с повторениями

Элементы: частично неразличимы (типы)
Порядок: важен

Эквивалентность: Задаче 1 через соответствие "места → типы элементов"

Задача 3: Флаги на мачтах

Элементы: различимы (флаги)
Группы: различимы (мачты)
Порядок в группах: важен
Пустые группы: допустимы

Формула: n! × Cₙ₊ₖ₋₁ᵏ⁻¹ = Aₙ₊ₖ₋₁ⁿ

Статистики в физике

Статистика	Различимость частиц	Ограничения	Формула
Максвелла-Больцмана	различимы	нет	kⁿ
Бозе-Эйнштейна	неразличимы	нет	Cₙ₊ₖ₋₁ᵏ⁻¹
Ферми-Дирака	неразличимы	≤1 частица в ячейке	Cₖⁿ

Задачи на разбиение чисел

Ключевое различие: Учет/неучет порядка слагаемых

Задача 4-5: Наклейка марок (порядок важен)

Рекуррентное соотношение:
f(N) = f(N-a₁) + f(N-a₂) + ... + f(N-aₖ)

Начальные условия:

f(0) = 1 (единственный способ - не клеить марки)
f(N) = 0 при N < 0

Частный случай: Разбиение на слагаемые 1,2,...,k

φ(k;N) = φ(k;N-1) + φ(k;N-2) + ... + φ(k;N-k)

Упрощенная формула: φ(N;N) = 2ᴺ⁻¹

Пример: Число 5 имеет 2⁴ = 16 разбиений на натуральные слагаемые с учетом порядка.

Комбинаторные структуры представления

Деревья перестановок

Корень → висячая вершина: одна перестановка
Число висячих вершин = n!
Ярусы соответствуют позициям в перестановке

Двоичное кодирование сочетаний

Длина последовательности: n
Число единиц: m
Единица на позиции i ⇔ элемент i включен в сочетание

Приложения в теории информации

Задача 6: Передача сообщений

Сигналы длительностей t₁, t₂, ..., tₖ
Время передачи: T
Учитываются только максимальные сообщения

Рекуррентное соотношение:
f(T) = f(T-t₁) + f(T-t₂) + ... + f(T-tₖ)