Математика / Графы, логика

Число сюръекций: распределение без пустых ящиков

Сюръективное отображение отправляет n различимых объектов в k различимых ящиков так, чтобы каждый ящик был занят. Формула считает такие распределения через числа Стирлинга или включения и исключения.

Опубликовано: 17 октября 2026 г.Обновлено: 17 октября 2026 г.

Формула

N(n,k)=k!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n

Схема Три предмета в двух ящиках

Из восьми назначений исключены два с пустым ящиком.

Обозначения

$N(n,k)$: число распределений без пустых ящиков, безразмерная величина
$n$: число различимых объектов, безразмерная величина
$k$: число различимых ящиков, безразмерная величина
$S(n,k)$: число разбиений на k непустых групп, безразмерная величина
$j$: число запрещённых для размещения ящиков, безразмерная величина

Условия применения

Полагаем n≥1, k≥1; каждый объект отправляют ровно в один ящик. Ящики различаются номерами, ограничений на вместимость нет, пустые ящики запрещены. При k>n ответ нулевой. В крайнем слагаемом при j=k имеем 0^n=0, поскольку n положительно.

Ограничения

Для неразличимых предметов применяется другая модель: число положительных целочисленных решений равно C(n−1,k−1). Если ящики не имеют имён, нужно S(n,k), без множителя k!. Порядок предметов внутри ящика или ограниченная вместимость также меняют задачу.

Подробное объяснение

Сначала забудем названия ящиков и разделим n объектов на k непустых групп. Таких разбиений S(n,k). Затем назначим каждой группе свой номер ящика: биекций между k группами и k ящиками ровно k!. Каждый итоговый вариант получается единственным разбиением и единственной разметкой групп.

Второй путь начинается со всех k^n функций: каждый объект независимо выбирает один из k ящиков. Из них вычитают функции, не использующие выбранный ящик. Но функции с двумя пустыми ящиками при таком вычитании удаляются дважды, поэтому их возвращают.

Продолжение этой поправки даёт чередующуюся сумму. Для j запрещённых ящиков есть C(k,j) способов выбрать их и (k−j)^n функций в оставшиеся ящики. Знак чередуется, чтобы любой вариант с хотя бы одним пустым ящиком в сумме получил нулевой вес.

Если объектов меньше, чем ящиков, занять все ящики невозможно. Если их поровну, каждый ящик получает ровно один объект и ответ равен k!. При k=1 есть только одно распределение. Эти случаи удобно использовать как проверки программного подсчёта.

Формула отвечает только на вопрос о количестве допустимых назначений. Она не утверждает, что они равновероятны в реальном процессе распределения работы. Для вероятности при независимом равномерном выборе ящика результат можно разделить на k^n, явно указав эту модель.

Как пользоваться формулой

Определите, различимы ли предметы и ящики; слово «одинаковые» меняет используемую модель подсчёта.
Проверьте n≥k; при меньшем числе объектов сразу запишите ноль допустимых распределений.
Найдите S(n,k) и умножьте на k! либо составьте полную сумму включений и исключений по j.
Сравните ответ с k^n: запрет пустых ящиков не может увеличить количество всех назначений.

Историческая справка

Подсчёт сюръекций связывает два стандартных языка комбинаторики: разбиения множества и включения–исключения. В университетских лекциях по комбинаторике формулу получают как пример того, что одно множество объектов можно пересчитать разными способами. В справочной литературе XX–XXI веков выражение через S(n,k) стало обычным средством перехода от неназванных блоков к именованным категориям. Исторические имена чисел Стирлинга относятся к самой числовой системе, а не к конкретной современной истории про исполнителей и задания. Полезная сторона этой связи — взаимная проверка: рекуррентная таблица и чередующаяся сумма должны давать одинаковое целое число. Единственного автора элементарного условия «каждый ящик занят» здесь не устанавливаем.

Историческая линия формулы

Количество сюръекций k!S(n,k) — стандартная интерпретация чисел Стирлинга второго рода. Альтернативная сумма является прямым применением принципа включений и исключений. Именование ящиков объясняет множитель k!, поэтому историческое название не заменяет проверку условий задачи.

Пример

Четыре разных задания нужно раздать трём названным исполнителям, причём каждый должен получить хотя бы одно. Всех назначений 3⁴ = 81. Вычитаем назначения с выбранным пустым исполнителем: 3·2⁴ = 48. Случаи с двумя пустыми исполнителями были вычтены дважды, поэтому возвращаем 3·1⁴ = 3. Получаем N(4,3) = 81 − 48 + 3 = 36. Проверка: размеры групп обязательно 2,1,1; выбираем пару заданий шестью способами, затем назначаем три группы исполнителям 3! = 6 способами. Произведение 6·6 = 36 совпало. Это число распределений; доля допустимых среди равномерных назначений была бы 36/81 = 4/9.

Частая ошибка

Не используйте сочетания с повторениями для различных заданий. Не забывайте множитель k!, если исполнители имеют имена. Не останавливайте включения и исключения после первого вычитания: пересечения пустых ящиков тоже нужны. Не считайте порядок вручения заданий внутри одного ящика новым распределением.

Практика

Задачи с решением

Два ящика

Условие. Распределите три разных предмета по двум названным ящикам без пустых.

Решение. Всего 2³ = 8; два назначения кладут всё в один ящик. 8 − 2 = 6.

Ответ. 6 распределений

Пять заданий

Условие. Найдите N(5,3).

Решение. N = 3⁵ − 3·2⁵ + 3·1⁵ = 243 − 96 + 3 = 150.

Ответ. 150 распределений

Дополнительные источники

https://math.mit.edu/~fox/MAT307-lecture04.pdf
https://dlmf.nist.gov/26.8

Связанные формулы

Математика

Числа Стирлинга второго рода: разбиение на группы

$S(n,k)=kS(n-1,k)+S(n-1,k-1)$

Число Стирлинга второго рода S(n,k) показывает, сколькими способами можно разбить n различных элементов на k непустых неименованных групп. Рекурсия отделяет добавление элемента в старую группу от создания новой.

Математика

Формула включений и исключений для трех множеств

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Формула включений и исключений для трех множеств считает элементы, попавшие хотя бы в одно из A, B или C. Она складывает три мощности, вычитает попарные пересечения и возвращает тройное пересечение, чтобы каждый объект был учтен ровно один раз.

Математика

Сочетания с повторениями: метод звёзд и перегородок

$\overline C_n^k=\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!(n-1)!}$

Формула считает наборы из k элементов n видов, когда один вид разрешено выбирать несколько раз, а порядок выбора не важен. Эквивалентная задача — распределить k одинаковых предметов по n различимым ящикам.