Меню Главная Случайная статья Настройки Метод шаров и перегородок Материал из https://ru.wikipedia.org Метод шаров и перегородок (англ. stars and bars — букв. «звёздочки и чёрточки») — это графический метод для вывода некоторых комбинаторных теорем. Метод популяризировал Уильям Феллер в его классической книге по теории вероятностей. Метод может быть использован для решения многих простых задач подсчёта, таких как «сколькими способами можно разложить n неразличимых шаров по k различимым ящикам»[1][2]. Содержание 1 Утверждения теорем 1.1 Теорема 1 1.2 Теорема 2 2 Доказательства с помощью шаров и перегородок 2.1 Теорема 1 2.2 Теорема 2 3 Примеры 4 См. также 5 Примечания 6 Литература 7 Ссылки Утверждения теорем Метод шаров и перегородок часто представляется доказательством следующих двух теорем элементарной комбинаторики. Теорема 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 шаров как фиксированные объекты определяют Теорема 2 В этом случае представление кортежей как последовательности шаров и перегородок остаётся неизменным. Накладываемое более слабое условие неотрицательности (вместо положительности) означает, что можно расположить несколько перегородок между двумя шарами, а также можно располагать перегородки перед первым шаром и после последнего. Таким образом, например, при n = 7 и k = 5 кортеж (4, 0, 1, 2, 0) может быть представлен следующим рисунком. | | | | Это устанавливает соответствие один-к-одному между кортежами такого вида и выборками с возвращением Чтобы видеть, что те же объекты подсчитываются биномиальным коэффициентом ${\displaystyle {\tbinom {n+k-1}{n}}}$, заметим, что желаемое расположение состоит из Примеры Если 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}$ способов распределения монет. См. также Двенадцатиричный путь Примечания Feller, 1950. Ю. В. Курышова. Начала комбинаторики . СУНЦ МГУ. Дата обращения: 11 апреля 2018. Архивировано 11 апреля 2018 года. Литература Feller W. An Introduction to Probability Theory and Its Applications. — 2nd ed.. — Wiley, 1950. — Т. 1. Ссылки Weisstein, Eric W. Multichoose . Mathworld -- A Wolfram Web Resource. Дата обращения: 18 ноября 2012.