Комбинаторика для программистов: перестановки, сочетания, размещения

Коротко

Половина ошибок в комбинаторике — от путаницы в первых двух столбцах. Всегда начинайте с вопроса: важен ли порядок?

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

Сколькими способами расставить n различных объектов в ряд?

Первое место — n вариантов, второе — n−1 (один уже занят), третье — n−2, и так далее.

P(n) = n · (n−1) · (n−2) · … · 1 = n!

import math

print(math.factorial(5))   # 120 — способов расставить 5 книг на полке

Факториал растёт чудовищно быстро: 20! уже больше 2·10¹⁸. Это объясняет, почему перебор всех перестановок применим только при n ≤ 10–11.

Перестановки с повторяющимися элементами

Если среди объектов есть одинаковые, часть перестановок совпадает. Формула делится на факториалы кратностей:

n! / (k₁! · k₂! · … · kₘ!)

from collections import Counter
import math


def permutations_with_repeats(items: list) -> int:
    result = math.factorial(len(items))
    for count in Counter(items).values():
        result //= math.factorial(count)
    return result


print(permutations_with_repeats(list('МАМА')))   # 6

Слово «МАМА» даёт 6 различных перестановок, а не 24: две М и две А неразличимы.

Размещения

Выбираем k объектов из n и расставляем по порядку.

A(n, k) = n! / (n − k)!

Житейский пример: сколькими способами распределить золото, серебро и бронзу между 10 участниками? Порядок важен — первое место не то же самое, что третье.

def arrangements(n: int, k: int) -> int:
    return math.perm(n, k)      # Python 3.8+


print(arrangements(10, 3))   # 720

Сочетания

Выбираем k объектов из n, порядок не важен.

C(n, k) = n! / (k! · (n − k)!)

Пример: сколькими способами выбрать 3 человек из 10 в команду? Здесь неважно, кого выбрали первым.

print(math.comb(10, 3))   # 120

Сравните с размещениями: 720 против 120, разница ровно в 3! = 6 — столько способов упорядочить каждую выбранную тройку.

Это и есть связь между формулами:

C(n, k) = A(n, k) / k!

Полезные свойства

C(n, k) = C(n, n−k)              симметрия
C(n, k) = C(n−1, k−1) + C(n−1, k)   правило Паскаля
Σ C(n, k) = 2ⁿ                    сумма по всем k

Симметрия имеет прозрачный смысл: выбрать 3 из 10 — то же самое, что решить, каких 7 не брать. На практике это даёт оптимизацию: считать C(n, min(k, n-k)).

Правило Паскаля — основа рекуррентного вычисления: либо берём первый элемент (и выбираем k−1 из оставшихся), либо не берём (выбираем k из оставшихся).

Треугольник Паскаля

Прямая реализация правила Паскаля — способ посчитать все сочетания без факториалов и деления.

def pascal_triangle(n: int) -> list[list[int]]:
    triangle = [[1]]

    for i in range(1, n + 1):
        row = [1]
        for j in range(1, i):
            row.append(triangle[i - 1][j - 1] + triangle[i - 1][j])
        row.append(1)
        triangle.append(row)

    return triangle


for row in pascal_triangle(5):
    print(row)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]
# [1, 5, 10, 10, 5, 1]

Способ удобен, когда нужны все значения C(n, k) для небольших n — например, в динамическом программировании. Сложность O(n²), но нет деления, что важно при работе по модулю.

Сочетания по модулю

В задачах ответ обычно просят по модулю 10⁹+7. Деление напрямую невозможно — нужен обратный элемент.

MOD = 10 ** 9 + 7
MAX = 10 ** 6

fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD

inv_fact = [1] * (MAX + 1)
inv_fact[MAX] = pow(fact[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD


def comb_mod(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD


print(comb_mod(10, 3))            # 120
print(comb_mod(1000000, 500000))  # считается мгновенно

Обратные факториалы вычисляются одним вызовом pow и обратным проходом — приём, который стоит запомнить.

Сочетания с повторениями

Задача «звёзды и палочки»: сколькими способами разложить k одинаковых конфет по n детям?

C(n + k − 1, k)

Идея наглядная: представим конфеты звёздочками, а границы между детьми — палочками. Нужно расставить k звёзд и n−1 палочку в ряд.

** | * | ***     →  2 конфеты первому, 1 второму, 3 третьему

def combinations_with_repeats(n: int, k: int) -> int:
    return math.comb(n + k - 1, k)


print(combinations_with_repeats(3, 6))   # 28

Тот же приём решает задачи вида «сколько неотрицательных целых решений у уравнения x₁ + x₂ + … + xₙ = k».

Формула включений-исключений

Считаем размер объединения множеств, когда они пересекаются:

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Знаки чередуются: одиночные плюс, пары минус, тройки плюс.

Пример: сколько чисел от 1 до 100 делятся на 2 или на 3?

n = 100
by_2 = n // 2                # 50
by_3 = n // 3                # 33
by_6 = n // 6                # 16 — делятся и на 2, и на 3

print(by_2 + by_3 - by_6)    # 67

Обобщение на много множеств удобно реализовать через битовые маски:

def count_divisible_by_any(n: int, divisors: list[int]) -> int:
    from math import lcm

    total = 0
    k = len(divisors)

    for mask in range(1, 1 << k):
        chosen = [divisors[i] for i in range(k) if mask & (1 << i)]
        multiple = lcm(*chosen)
        sign = 1 if len(chosen) % 2 == 1 else -1
        total += sign * (n // multiple)

    return total


print(count_divisible_by_any(100, [2, 3, 5]))   # 74

Генерация в Python

Для маленьких n модуль itertools избавляет от ручной реализации:

from itertools import permutations, combinations, product, combinations_with_replacement

list(permutations([1, 2, 3]))               # все 6 перестановок
list(permutations([1, 2, 3], 2))            # размещения по 2
list(combinations([1, 2, 3], 2))            # [(1,2), (1,3), (2,3)]
list(product([0, 1], repeat=3))             # все двоичные строки длины 3
list(combinations_with_replacement('ab', 2))  # [('a','a'), ('a','b'), ('b','b')]

Все функции возвращают итераторы и не хранят результат в памяти целиком — важно, потому что перестановок может быть очень много.

Как выбрать формулу

Алгоритм на три вопроса:

1. Порядок важен? Да → перестановки или размещения. Нет → сочетания.
2. Берём все объекты или часть? Все → перестановки. Часть → размещения или сочетания.
3. Элементы могут повторяться? Да → добавляем повторы в формулу.

Полезный приём самопроверки: посчитать ответ для крошечного случая (n=2, k=1) руками и сравнить с формулой. Это ловит большинство ошибок.

Частые ошибки

Путаница размещений и сочетаний. Самая частая. «Выбрать команду» — сочетания, «распределить призовые места» — размещения.

Двойной счёт. Если объекты неразличимы, а формула считает их разными, ответ завышается ровно в k! раз.

Факториал больших чисел без модуля. 10000! — это число с 35 тысячами цифр; в Python посчитается, но медленно.

Деление при работе по модулю. Нужен обратный элемент, иначе ответ неверен.

Неучтённые ограничения задачи. «Никакие двое не сидят рядом», «первый элемент фиксирован» — такие условия меняют формулу, и слепое применение шаблона даст неверный ответ.

Что запомнить

• Первый вопрос всегда: важен ли порядок. От него зависит выбор формулы.
• Сочетания = размещения, делённые на k!.
• C(n, k) = C(n, n−k) — используйте для оптимизации.
• Правило Паскаля даёт треугольник и рекуррентное вычисление без деления.
• По модулю считайте через факториалы и обратные факториалы.
• Формула включений-исключений чередует знаки по размеру пересечения.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→