Метод шаров и перегородок
Метод шаров и перегородок (Шаблон:Lang-en — букв. «звёздочки и чёрточки») — это графический метод для вывода некоторых комбинаторных теорем. Метод популяризировал Уильям Феллер в его классической книге по теории вероятностей. Метод может быть использован для решения многих простых задач подсчёта, таких как «сколькими способами можно разложить n неразличимых шаров по k различимым ящикам»Шаблон:Sfn[1].
Утверждения теорем
Метод шаров и перегородок часто представляется доказательством следующих двух теорем элементарной комбинаторики.
Теорема 1
Для любой пары натуральных чисел n и k число k-кортежей натуральных чисел, сумма которых равна n, равно числу -элементных подмножеств множества из элементов.
Оба эти числа задаются биномиальным коэффициентом . Например, при n = 3 и k = 2 кортежи, подсчитанные теоремой, это (2, 1) и (1, 2), и существует таких кортежей.
Теорема 2
Для любой пары натуральных чисел n и k число k-кортежей неотрицательных целых чисел, сумма которых равна n, равно числу мультимножеств мощности k — 1, взятых из множества размера n + 1.
Оба числа равны числу мультимножеств , или, эквивалентно, биномиальному коэффициенту или числу мультимножеств . Например, при n = 3 и k = 2 кортежи, подсчитываемые теоремой, — это (3, 0), (2, 1), (1, 2) и (0, 3), и имеется таких кортежей.
Если k-кортеж неотрицательных целых чисел является разложением числа n на набор неотрицательных слагаемых, то k-кортеж из тех же чисел, увеличенных на 1, является разложением числа n+k на набор положительных слагаемых. Таким образом устанавливается взаимно однозначное соответствие между такими разложениями. Поэтому, согласно Теореме 1, количество k-кортежей неотрицательных чисел, сумма которых равна n, будет равно
Доказательства с помощью шаров и перегородок
Теорема 1
Предположим, что имеется n объектов (которые представляются шарами, В примере ниже n = 7) нужно разместить в k ящиках (в примере k = 3) таким образом, что все ящики должны содержать по меньшей мере один объект. Ящики различаются (скажем, они пронумерованы числами от 1 до k), но шары неразличимы (так что конфигурации различимы по числу шаров, находящихся в каждом ящике, фактически, конфигурация представляет k-кортеж положительных чисел, как в утверждении теоремы). Вместо размещения шаров в ящиках шары располагаются в линию:
где шары для первого ящика берутся слева, затем идут шары второго ящика и так далее. Таким образом, конфигурация определяется тем, какой начальный шар принадлежит первому ящику, какой первый (самый левый) шар принадлежит второму ящику и так далее. Можно отмечать это положение, помещая Шаблон:Math разделяющих перегородок в некоторых местах между двумя шарами; а поскольку никакой ящик не может оказаться пустым, между двумя соседними шарами может быть не более одной перегородки:
Тогда n шаров как фиксированные объекты определяют Шаблон:Math промежутков между шарами, в каждый из которых можно поместить (или не поместить) одну перегородку. Нужно выбрать Шаблон:Math мест, в которых разместить перегородки, поэтому имеется возможных конфигураций (см. Сочетание).
Теорема 2
В этом случае представление кортежей как последовательности шаров и перегородок остаётся неизменным. Накладываемое более слабое условие неотрицательности (вместо положительности) означает, что можно расположить несколько перегородок между двумя шарами, а также можно располагать перегородки перед первым шаром и после последнего. Таким образом, например, при n = 7 и k = 5 кортеж (4, 0, 1, 2, 0) может быть представлен следующим рисунком. Шаблон:Image frame
Это устанавливает соответствие один-к-одному между кортежами такого вида и выборками с возвращением Шаблон:Math промежутков среди Шаблон:Math возможных промежутков, или, эквивалентно, (Шаблон:Math)-элементных мультимножеств, взятых из множества размера Шаблон:Math. По определению, такие объекты подсчитываются числом мультивыбора .
Чтобы видеть, что те же объекты подсчитываются биномиальным коэффициентом , заметим, что желаемое расположение состоит из Шаблон:Math объектов (n шаров и Шаблон:Math перегородок). Выбор позиций для шаров оставляет ровно Шаблон:Math мест для Шаблон:Math перегородок. То есть выбор позиций для шаров определяет всю конфигурацию, так что число конфигураций равно . Заметим, что , что отражает факт, что конфигурация определяется выбором позиций для Шаблон:Math перегородок.
Примеры
Если n = 5, k = 4 и множество размера k — {a, b, c, d}, то ●|●●●||● представляет мультимножество {a, b, b, b, d} или 4-кортеж (1, 3, 0, 1). Представление любого мультимножества для этого примера будет использовать n = 5 шаров и k − 1 = 3 перегородок.
Многие элементарные задачи в комбинаторике решаются вышеприведёнными теоремами. Например, если нужно подсчитать число способов распределить семь неразличимых десятирублёвых монет между Анной, Борисом и Виталием так, что каждый из них получит по меньшей одну монету, можно заметить, что распределение эквивалентно кортежу из трёх натуральных чисел, сумма которых равна 7. (Здесь первая позиция в кортеже определяет число монет, отдаваемых Анне, и так далее.) Таким образом, метод шаров и перегородок применим с n = 7 и k = 3, что даёт способов распределения монет.