Звезды и полосы (комбинаторика)

В комбинаторике звезды и полосы (также называемые «палками и камнями», ^[1] «мячами и полосами», ^[2] и «точками и разделителями» ^[3] ) — это графическое пособие для вывода некоторых комбинаторных теорем. Его можно использовать для решения многих простых задач на подсчет , например, сколько существует способов поместить n неразличимых шаров в k различимых ячеек. ^[4]

Теоремы один и два представляют собой коэффициенты, используемые для двух различных диапазонов поддержки в отрицательном биномиальном распределении вероятностей .

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

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

Например, если n = 10 и k = 4 , теорема дает число решений уравнения x ₁ + x ₂ + x ₃ + x ₄ = 10 (при x ₁ , x ₂ , x ₃ , x ₄ > 0 ) в виде биномиального коэффициента

${\displaystyle {\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84.}$

Это соответствует композициям целого числа.

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

Например, если n = 10 и k = 4 , теорема дает число решений уравнения x ₁ + x ₂ + x ₃ + x ₄ = 10 (с x ₁ , x ₂ , x ₃ , x ₄ ${\displaystyle \geq 0}$ ) в виде:

${\displaystyle \left(\!\!{k \выберите n}\!\!\right)={k+n-1 \выберите n}={\binom {13}{10}}=286}$

${\displaystyle \left(\!\!{n+1 \выберите k-1}\!\!\right)={n+1+k-1-1 \выберите k-1}={\binom {13}{3}}=286}$

${\displaystyle {\binom {n+k-1}{k-1}}={\binom {10+4-1}{4-1}}={\binom {13}{3}}=286}$

Это соответствует слабым композициям целого числа.

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

Например, при n = 7 и k = 3 начните с размещения звезд в ряд:

Конфигурация будет определена, как только станет известно, какая звезда первой идет во вторую ячейку, а какая — в третью и т. д. Это обозначается размещением k − 1 полос между звездами. Поскольку ни одна ячейка не может быть пустой (все переменные положительны), между любой парой звезд может быть не более одной полосы.

Например:

Между звездами имеется n − 1 зазоров. Конфигурация получается путем выбора k − 1 из этих зазоров, содержащих полосу; поэтому возможны комбинации .${\displaystyle {\tbinom {n-1}{k-1}}}$

В этом случае ослабленное ограничение неотрицательности вместо положительности означает, что мы можем разместить несколько полос между звездами, перед первой звездой и после последней звезды.

Например, когда n = 7 и k = 5 , кортеж (4, 0, 1, 2, 0) может быть представлен следующей диаграммой:

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

Теорему 1 теперь можно переформулировать в терминах теоремы 2, поскольку требование, чтобы все переменные были положительными, эквивалентно предварительному присвоению каждой переменной значения a 1 и запросу количества решений, когда каждая переменная неотрицательна.

Например:

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}$

с${\displaystyle x_{1},x_{2},x_{3},x_{4}>0}$

эквивалентно:

${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=6}$

с${\displaystyle x_{1},x_{2},x_{3},x_{4}\geq 0}$

Оба случая очень похожи, мы рассмотрим случай, когда сначала. «Ведро» становится${\displaystyle x_{i}\geq 0}$

${\displaystyle {\frac {1}{1-x}}}$

Это также можно записать как

${\displaystyle 1+x+x^{2}+\точки }$

а показатель степени x показывает, сколько мячей помещено в ведро.

Каждое дополнительное ведро представлено другим , и поэтому окончательная генерирующая функция имеет вид${\displaystyle {\frac {1}{1-x}}}$

${\displaystyle {\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}={\frac {1}{(1-x)^{k}}}}$

Так как у нас есть только n шаров, нам нужен коэффициент (записанный ) из этого${\displaystyle x^{n}}$${\displaystyle [x^{n}]:}$

${\displaystyle [x^{n}]:{\frac {1}{(1-x)^{k}}}}$

Это хорошо известная производящая функция — она генерирует диагонали в треугольнике Паскаля , а коэффициент равен${\displaystyle x^{n}}$

${\displaystyle {\binom {n+k-1}{k-1}}}$

В случае, когда , нам нужно добавить x в числитель, чтобы указать, что в ведре находится хотя бы один мяч.${\displaystyle x_{i}>0}$

${\displaystyle {\frac {x}{1-x}}{\frac {x}{1-x}}\dots {\frac {x}{1-x}}={\frac {x^{k}}{(1-x)^{k}}}}$

и коэффициент равен${\displaystyle x^{n}}$

${\displaystyle {\binom {n-1}{k-1}}}$

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

Если кто-то захочет подсчитать количество способов распределить семь неразличимых однодолларовых монет между Эмбер, Беном и Кертисом так, чтобы каждый из них получил хотя бы один доллар, можно заметить, что распределения по сути эквивалентны кортежам из трех положительных целых чисел, сумма которых равна 7. (Здесь первая запись в кортеже — это количество монет, отданных Эмбер, и т. д.) Таким образом, применима теорема 1 о звездах и полосах с n = 7 и k = 3 , и существуют способы распределить монеты.${\displaystyle {\tbinom {7-1}{3-1}}=15}$

Если n = 5 , k = 4 , а набор размера k равен {a, b, c, d}, то ★|★★★||★ может представлять либо мультимножество {a, b, b, b, d} , либо 4- кортеж (1, 3, 0, 1). Представление любого мультимножества для этого примера должно использовать SAB2 с n = 5 , k – 1 = 3 столбца, чтобы получить .${\displaystyle {\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56}$

В SAB2 допускается больше полос, чем звезд, что не допускается в SAB1.

Так, например, 10 шаров в 7 ящиков — это , в то время как 7 шаров в 10 ящиков — это , а 6 шаров в 11 ящиков — это${\displaystyle {\tbinom {16}{6}}}$${\displaystyle {\tbinom {16}{9}}}$${\displaystyle {\tbinom {16}{10}}={\tbinom {16}{6}}.}$

Если у нас есть бесконечный степенной ряд

${\displaystyle \left[\sum _{k=1}^{\infty }x^{k}\right],}$

мы можем использовать этот метод для вычисления произведения Коши m копий ряда. Для n -го члена разложения мы выбираем n степеней x из m отдельных мест. Следовательно, есть способы сформировать нашу n -ю степень:${\displaystyle {\tbinom {n-1}{m-1}}}$

${\displaystyle \left[\sum _{k=1}^{\infty }x^{k}\right]^{m}=\sum _{n=m}^{\infty }{{n-1} \choose {m-1}}x^{n}}$

Графический метод был использован Паулем Эренфестом и Хайке Камерлинг-Оннесом — с символом ε (квантовый элемент энергии) вместо звездочки и символом 0 вместо черточки — как простой вывод выражения Макса Планка для числа «комплексионов» для системы «резонаторов» одной частоты. ^{[5] [6]}

Под комплексионами ( микросостояниями ) Планк подразумевал распределения P энергетических элементов ε по N резонаторам. ^{[7] [8]} Число R комплексионов равно

${\displaystyle R={\frac {(N+P-1)!}{P!(N-1)!}}.\ }$

Графическое представление каждого возможного распределения будет содержать P копий символа ε и N – 1 копий символа 0. В своей демонстрации Эренфест и Камерлинг-Оннес взяли N = 4 и P = 7 ( т.е. R = 120 комбинаций). Они выбрали 4-кортеж ( 4, 2, 0, 1) в качестве иллюстративного примера для этого символического представления: εεεε0εε00ε .

• Гауссовский биномиальный коэффициент
• Разбиение (теория чисел)
• Двенадцатикратный путь
• Дирихле-мультиномиальное распределение

• Питман, Джим (1993). Вероятность . Берлин: Springer-Verlag. ISBN 0-387-97974-3.
• Weisstein, Eric W. "Multichoose". Mathworld -- A Wolfram Web Resource . Получено 18 ноября 2012 г.