Метод шаров и перегородок

Метод шаров и перегородок (англ. stars and bars — букв. «звёздочки и чёрточки») — это графический метод для вывода некоторых комбинаторных теорем. Метод популяризировал Уильям Феллер в его классической книге по теории вероятностей. Метод может быть использован для решения многих простых задач подсчёта, таких как «сколькими способами можно разложить n неразличимых шаров по k различимым ящикам»^[1][2].

Утверждения теорем

Метод шаров и перегородок часто представляется доказательством следующих двух теорем элементарной комбинаторики.

Теорема 1

Для любой пары натуральных чисел n и k число k-кортежей натуральных чисел, сумма которых равна n, равно числу ${\displaystyle (k-1)}$-элементных подмножеств множества из ${\displaystyle n-1}$ элементов.

Оба эти числа задаются биномиальным коэффициентом ${\displaystyle \textstyle {n-1 \choose k-1}}$. Например, при n = 3 и k = 2 кортежи, подсчитанные теоремой, это (2, 1) и (1, 2), и существует ${\displaystyle {\tbinom {3-1}{2-1}}=2}$ таких кортежей.

Теорема 2

Для любой пары натуральных чисел n и k число k-кортежей неотрицательных целых чисел, сумма которых равна n, равно числу мультимножеств мощности k — 1, взятых из множества размера n + 1.

Оба числа равны числу мультимножеств ${\displaystyle \left(\!{\tbinom {n+1}{k-1}}\!\right)}$, или, эквивалентно, биномиальному коэффициенту ${\displaystyle {\tbinom {n+k-1}{k-1}}={\tbinom {n+k-1}{n}}}$ или числу мультимножеств ${\displaystyle {\big (}\!{\tbinom {k}{n}}\!{\big )}}$. Например, при n = 3 и k = 2 кортежи, подсчитываемые теоремой, — это (3, 0), (2, 1), (1, 2) и (0, 3), и имеется ${\displaystyle \left(\!{\tbinom {3+1}{2-1}}\!\right)=4}$ таких кортежей.

Если k-кортеж неотрицательных целых чисел является разложением числа n на набор неотрицательных слагаемых, то k-кортеж из тех же чисел, увеличенных на 1, является разложением числа n+k на набор положительных слагаемых. Таким образом устанавливается взаимно однозначное соответствие между такими разложениями. Поэтому, согласно Теореме 1, количество k-кортежей неотрицательных чисел, сумма которых равна n, будет равно ${\displaystyle \textstyle {n+k-1 \choose k-1}}$

Доказательства с помощью шаров и перегородок

Теорема 1

Предположим, что имеется n объектов (которые представляются шарами, В примере ниже n = 7) нужно разместить в k ящиках (в примере k = 3) таким образом, что все ящики должны содержать по меньшей мере один объект. Ящики различаются (скажем, они пронумерованы числами от 1 до k), но шары неразличимы (так что конфигурации различимы по числу шаров, находящихся в каждом ящике, фактически, конфигурация представляет k-кортеж положительных чисел, как в утверждении теоремы). Вместо размещения шаров в ящиках шары располагаются в линию:

где шары для первого ящика берутся слева, затем идут шары второго ящика и так далее. Таким образом, конфигурация определяется тем, какой начальный шар принадлежит первому ящику, какой первый (самый левый) шар принадлежит второму ящику и так далее. Можно отмечать это положение, помещая k − 1 разделяющих перегородок в некоторых местах между двумя шарами; а поскольку никакой ящик не может оказаться пустым, между двумя соседними шарами может быть не более одной перегородки:

Тогда n шаров как фиксированные объекты определяют n − 1 промежутков между шарами, в каждый из которых можно поместить (или не поместить) одну перегородку. Нужно выбрать k − 1 мест, в которых разместить перегородки, поэтому имеется ${\displaystyle {\tbinom {n-1}{k-1}}}$ возможных конфигураций (см. Сочетание).

Теорема 2

В этом случае представление кортежей как последовательности шаров и перегородок остаётся неизменным. Накладываемое более слабое условие неотрицательности (вместо положительности) означает, что можно расположить несколько перегородок между двумя шарами, а также можно располагать перегородки перед первым шаром и после последнего. Таким образом, например, при n = 7 и k = 5 кортеж (4, 0, 1, 2, 0) может быть представлен следующим рисунком.

Это устанавливает соответствие один-к-одному между кортежами такого вида и выборками с возвращением k − 1 промежутков среди n + 1 возможных промежутков, или, эквивалентно, (k − 1)-элементных мультимножеств, взятых из множества размера n + 1. По определению, такие объекты подсчитываются числом мультивыбора ${\displaystyle \left(\!{\tbinom {n+1}{k-1}}\!\right)}$.

Чтобы видеть, что те же объекты подсчитываются биномиальным коэффициентом ${\displaystyle {\tbinom {n+k-1}{n}}}$, заметим, что желаемое расположение состоит из n + k − 1 объектов (n шаров и k − 1 перегородок). Выбор позиций для шаров оставляет ровно k − 1 мест для k − 1 перегородок. То есть выбор позиций для шаров определяет всю конфигурацию, так что число конфигураций равно ${\displaystyle {\tbinom {n+k-1}{n}}}$. Заметим, что ${\displaystyle {\tbinom {n+k-1}{n}}={\tbinom {n+k-1}{k-1}}}$, что отражает факт, что конфигурация определяется выбором позиций для k − 1 перегородок.

Примеры

Если 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, что даёт ${\displaystyle \textstyle {7-1 \choose 3-1}=15}$ способов распределения монет.

См. также

• Двенадцатиричный путь

Примечания

Литература

Ссылки

• Weisstein, Eric W. Multichoose  (неопр.). Mathworld -- A Wolfram Web Resource. Дата обращения: 18 ноября 2012.

Эта страница в последний раз была отредактирована 3 февраля 2024 в 10:45.