Литература по курсу "Комбинаторика"
Ключевые тезисы
- Основной задачник — «Комбинаторика» Виленкина.
- «Зелёная книжка» (методическое пособие) — ключевой указатель по материалу курса.
- Дополнительные источники: задачник Фуфаева и Устинова, книга Харари «Теория графов».
- Комбинаторика изучает способы комбинирования объектов, подсчёта их количества и поиска комбинаций с оптимальными свойствами.
Основное содержание
Базовые понятия и обозначения
- Множество — совокупность объектов, обозначается как
A = {a₁, a₂, ..., aₙ}. - Мощность множества (
|A|) — количество элементов в нём.
Основные правила комбинаторики
Правило сложения
Если есть два непересекающихся множества A (мощности n) и B (мощности m), то число способов выбрать один объект либо из A, либо из B равно n + m.
Правило умножения
Если есть два множества A (мощности n) и B (мощности m), то число способов последовательно выбрать сначала объект из A, а затем объект из B равно n * m.
- Пример: Подсчёт количества автомобильных номеров при фиксированном регионе.
Принцип Дирихле (принцип ящиков)
Если n + 1 кролика рассадить в n ящиков, то найдётся ящик, в котором не менее двух кроликов.
- Пример применения: В квадрате со стороной 2 произвольно выбраны 5 точек. Всегда найдутся две точки, расстояние между которыми не превышает
√2. (Точки — «кролики», 4 равных квадрата со стороной 1 — «ящики»).
Сочетания, размещения, перестановки
Рассматриваются способы выбора k объектов из множества мощности n.
| Тип выбора | Порядок важен? | Повторения разрешены? | Название | Обозначение |
|---|---|---|---|---|
| Последовательно, без возврата | Да | Нет | Размещения без повторений | Aₙᵏ |
| Последовательно, с возвратом | Да | Да | Размещения с повторениями | Āₙᵏ |
| Без порядка (пригоршней), без возврата | Нет | Нет | Сочетания без повторений | Cₙᵏ |
| Без порядка (пригоршней), с возвратом | Нет | Да | Сочетания с повторениями | C̄ₙᵏ |
Определения
- Размещение — выбор, при котором важен порядок элементов (распределение по «должностям»).
- Сочетание — выбор без учёта порядка («пригоршня» объектов).
- Перестановка — частный случай размещения, когда
k = n(все объекты используются и порядок важен). Число перестановокnобъектов —n!(эн-факториал).
Формулы для подсчёта
Теорема 1: Число размещений с повторениями: Āₙᵏ = nᵏ (следует из правила умножения).
Теорема 2: Число размещений без повторений: Aₙᵏ = n * (n-1) * ... * (n-k+1). Альтернативная запись: Aₙᵏ = n! / (n-k)!.
Теорема 3: Число сочетаний без повторений: Cₙᵏ = Aₙᵏ / k!. Альтернативная симметричная запись: Cₙᵏ = n! / (k! * (n-k)!).
- Доказательство: Каждому сочетанию (неупорядоченной «кучке» из
kобъектов) соответствуетk!различных размещений (упорядочиваний). Поэтому общее число размещенийAₙᵏвk!раз больше числа сочетанийCₙᵏ.
Важное замечание: По определению 0! = 1. Это обеспечивает корректность формул в граничных случаях (например, Cₙ⁰ = 1 — способ ничего не выбрать).