Комбинаторика: подсчёт пространства возможностей

Beam search в GPT-4 при k=5: на каждом шаге из 50257 токенов. За 1000 токенов - (50257)^1000 возможных путей. Это больше чем атомов во Вселенной в степени 70. Комбинаторный взрыв - реальная проблема, которую каждый LLM решает эвристикой. А 8-символьный пароль из букв и цифр - это 62^8 ~ 2×10^14. PIN из 20 цифр - 10^20, в 457 раз больше. Комбинаторика не терпит интуиции.

• **Безопасность паролей:** энтропия - log2(число вариантов), которое считается через правило произведения. 62^8 vs 10^20 - цифры решают
• **Birthday attack на хэши:** из C(n,2) пар хэшей вероятность коллизии резко растёт при n ~ 2^(m/2). Именно поэтому MD5 (2^64) сломан, а SHA-256 (2^128) нет
• **Hyperparameter search:** 10 параметров × 10 значений = 10^10 комбинаций. RandomSearch семплирует из C(n,k) подпространств - и обгоняет GridSearch

Предварительные знания

• Методы доказательств

Правила произведения и суммы: фундамент подсчёта

Beam search в GPT-4 при ширине k=5 рассматривает на каждом шаге 5 лучших токенов из 50257. За последовательность из 1000 токенов - это (50257)^1000 теоретических путей. Число настолько огромное, что не влезает в нотацию. И всё же модель отвечает за секунды. Почему? Потому что правило произведения работает в обе стороны: оно объясняет как комбинаторный взрыв, так и то, как его обойти.

**Правило произведения (AND):** последовательные независимые выборы - перемножить. |A × B| = |A| · |B| **Правило суммы (OR):** взаимоисключающие альтернативы - сложить. |A ∪ B| = |A| + |B|, если A ∩ B = ∅

Длина пароля важнее сложности алфавита - это прямое следствие правила произведения. Добавление одного символа умножает количество вариантов на весь размер алфавита. Расширение алфавита с 62 до 72 символов при длине 8 даёт только (72/62)^8 - примерно 3.3 раза. Добавление одного символа при том же алфавите - умножает на 62.

**Практическое правило:** логарифм числа вариантов - это «биты энтропии». 2^64 - примерно 1.8 × 10^19 - нижняя граница для устойчивости к брутфорсу при современных скоростях. Пароль из 12 случайных символов (62-алфавит) даёт около 71 бита - достаточно для большинства задач.

Перестановки: n! способов упорядочить

1654 год. Паскаль и Ферма переписываются о задаче азартной игры: сколько способов выпасть определённой последовательности? Первый систематический подсчёт порядков. Через 370 лет те же формулы считают пространство поиска нейросетей, маршруты TSP-решателей и перестановочные инварианты в attention-механизмах.

**Перестановка n элементов:** P(n) = n! = n · (n-1) · (n-2) · ... · 2 · 1 **Размещение k из n** (k объектов из n, порядок важен): P(n, k) = n! / (n-k)! = n · (n-1) · ... · (n-k+1) Мнемоника: **порядок важен** - перестановки/размещения.

**n! растёт катастрофически быстро.** При n=20 - около 2.4 × 10^18 операций. При 10^9 операций в секунду - это 3.8 миллиарда лет. Именно поэтому TSP, задачи оптимального планирования и перебор гиперпараметров не решаются полным перебором - используют эвристики, эволюционные алгоритмы и random search.

Сочетания C(n,k): когда порядок не важен

Hyperparameter search - типичная задача в ML. Модель с 10 гиперпараметрами, каждый с 10 значениями - GridSearch перебирает 10^10 комбинаций. RandomSearch случайно семплирует из этого пространства без возврата. Оказывается, случайный поиск в среднем находит хорошее решение быстрее - это математический факт, следующий из геометрии пространства C(n,k).

**Число сочетаний:** C(n, k) = n! / (k! · (n-k)!) Читается «n выбрать k» или «биномиальный коэффициент». Связь с размещениями: C(n, k) = P(n, k) / k! Делим на k! потому что k! перестановок одной и той же группы дают одно и то же сочетание.

**Треугольник Паскаля:** C(n,k) = C(n-1,k-1) + C(n-1,k). Каждый элемент либо включён в подмножество (C(n-1,k-1)), либо нет (C(n-1,k)). Это рекуррентность - основа динамического программирования для задач подсчёта. GPT-2 paper использует похожую структуру для подсчёта контекстных комбинаций в attention head анализе.

Применения: энтропия, beam search, birthday attack

8-символьный пароль из букв и цифр даёт 62^8 - примерно 2.18 × 10^14 вариантов. 20-символьный PIN из цифр - 10^20. Второй в 457 раз больше. Интуиция говорит: 20 символов надёжнее 8. Комбинаторика говорит: смотри на основание степени, а не на показатель. Именно здесь ломается большинство паролей корпоративных политик.

Data augmentation в computer vision - ещё одно комбинаторное пространство. Для изображения 224×224: случайные обрезки C(n,k) вариантов, горизонтальные флипы (2 состояния), ротации (360 степеней), изменения яркости (непрерывный параметр). Количество уникальных аугментаций практически бесконечно - именно поэтому модели не переобучаются на аугментированных данных даже при сотнях эпох.

Ключевые идеи

• **Правило произведения:** последовательные независимые выборы перемножаются. Правило суммы - для взаимоисключающих альтернатив. Это объясняет beam search и entropy паролей
• **Перестановки и размещения:** когда порядок важен. P(n,k) = n!/(n-k)! - k элементов из n. n! растёт быстрее любой экспоненты - TSP невозможен брутфорсом при n>15
• **Сочетания C(n,k):** когда порядок не важен. C(n,k) = P(n,k)/k! - делим на k! перестановок одной группы. Birthday attack: 50% коллизия при n ~ sqrt(2N)
• **Stars and bars C(n+k-1,k):** сочетания с повторениями - распределить k одинаковых по n ящикам. Размер таблицы DP в задачах распределения ресурсов
• **RandomSearch > GridSearch** для многих гиперпараметров - математический факт из геометрии комбинаторного пространства, не эвристика

Связанные темы

Комбинаторика - фундамент для вероятностей, криптографии и анализа алгоритмов:

• Методы доказательств — Биномиальная теорема и формулы для C(n,k) доказываются индукцией
• Производящие функции — OGF кодируют последовательности комбинаторных чисел как коэффициенты многочленов
• Принцип включений-исключений — PIE считает |A∪B∪...| через знакочередующиеся суммы биномиальных коэффициентов

Вопросы для размышления

• Проектируется система генерации API-токенов. Какой алфавит и длину выбрать, чтобы за 10 лет не исчерпать токены при 10^6 генераций в день и 128 битах безопасности?
• В чём разница между «выбрать 3 фичи из 10 для спринта» (сочетание) и «назначить приоритеты 1, 2, 3 трём фичам из 10» (размещение)?
• Почему RandomSearch обходит GridSearch при большом числе гиперпараметров - можно ли это объяснить через C(n,k)?

Связанные уроки

• prob-02-combinatorics — Вероятностная комбинаторика: birthday problem, случайные графы, вероятностный метод
• prob-04-bayes — Байесовский апдейт требует подсчёта числа событий - прямое применение C(n,k)
• dm-06 — Производящие функции кодируют комбинаторные последовательности как коэффициенты
• dm-07 — Принцип включений-исключений строится на биномиальных коэффициентах
• calc-01-sequences — Факториал и биномиальный коэффициент - предельное поведение через последовательности
• alg-01-big-o