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

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

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

Теорема 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. (неопр.) . Mathworld -- A Wolfram Web Resource . Дата обращения: 18 ноября 2012.