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

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

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

Формулировки теорем

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

Теорема первая

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

Например, если $n = 10$ и $k = 4$ , теорема дает число решений $x 1 + x 2 + x 3 + x 4 = 10$ (при $x 1, x 2, x 3, x 4 > 0$ ) как биномиальный коэффициент

{\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 1 + x 2 + x 3 + x 4 = 10$ (при $\geq 0$ ) как:

\left(\!\!{k \choose n}\!\!\right)={k+n-1 \choose n}={\binom {13}{10}}=286

\left(\!\!{n+1 \choose k-1}\!\!\right)={n+1+k-1-1 \choose k-1}={\binom {13}{3}}=286

{\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$ начните с размещения звезд в линию:

★ ★ ★ ★ ★ ★ ★

Рис. 1: Семь объектов, представленных звездами.

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

Например:

★ ★ ★ ★ | ★ | ★ ★

Рис. 2. Эти две полоски образуют три ячейки, содержащие 4, 1 и 2 объекта.

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

Доказательство второй теоремы

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

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

★ ★ ★ ★ | | ★ | ★ ★ |

Рис. 3. Эти четыре столбца образуют пять ячеек, содержащих 4, 0, 1, 2 и 0 объектов.

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

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

Например:

x_{1}+x_{2}+x_{3}+x_{4}=10

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

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

x_{1}+x_{2}+x_{3}+x_{4}=6

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

Доказательства производящими функциями

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

{\frac {1}{1-x}}

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

1+x+x^{2}+\dots

а показатель степени $x$ говорит нам, сколько шаров помещено в ведро.

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

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

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

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

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

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

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

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

и коэффициент $x^{n}$ является

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

Примеры

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

Пример 1

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

Пример 2

Если $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$ бара, чтобы получить ${\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56$ .

Пример 3

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

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

Пример 4

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

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

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

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

Пример 5

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

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

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

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

См. также

Ссылки

^ Баттерсон, Дж. Соревнования по математике в средней школе . Искусство решения проблем.
^ Флажоле, Филипп; Седжвик, Роберт (26 июня 2009 г.). Аналитическая комбинаторика . Издательство Кембриджского университета. ISBN 978-0-521-89806-5 .
^ «Искусство решения проблем» . artofproblemsolve.com . Проверено 26 октября 2021 г.
^ Феллер, Уильям (1968). Введение в теорию вероятностей и ее приложения . Том. 1 (3-е изд.). Уайли. п. 38.
^ Эренфест, Пол; Камерлинг-Оннес, Хайке (1914). «Упрощенный вывод формулы из теории комбинаций, которую Планк положил в основу своей теории излучения» . Труды КНАВ . 17 : 870–873 . Проверено 16 мая 2024 г.
^ Эренфест, Пол; Камерлинг-Оннес, Хайке (1915). «Упрощенный вывод формулы из теории комбинаций, которую Планк положил в основу своей теории излучения» . Лондонский, Эдинбургский и Дублинский философский журнал и научный журнал . Серия 6. 29 (170): 297–301. дои : 10.1080/14786440208635308 . Проверено 5 декабря 2020 г.
^ Планк, Макс (1901). «О законе распределения энергии в нормальном спектре» . Анналы физики . 309 (3): 553–563. Стартовый код : 1901АнП...309..553П . дои : 10.1002/andp.19013090310 .
^ Геархарт, К. (2002). «Планк, квант и историки» (PDF) . Физ. Перспектива . 4 (2): 170–215. Бибкод : 2002PhP.....4..170G . дои : 10.1007/s00016-002-8363-7 . Проверено 16 мая 2024 г.

Дальнейшее чтение

Питман, Джим (1993). Вероятность . Берлин: Springer-Verlag. ISBN 0-387-97974-3 .
Вайсштейн, Эрик В. «Множественный выбор» . Mathworld — веб-ресурс Wolfram . Проверено 18 ноября 2012 г.

[1] Баттерсон, Дж. Соревнования по математике в средней школе . Искусство решения проблем.

[2] Флажоле, Филипп; Седжвик, Роберт (26 июня 2009 г.). Аналитическая комбинаторика . Издательство Кембриджского университета. ISBN 978-0-521-89806-5 .

[:0-3] «Искусство решения проблем» . artofproblemsolve.com . Проверено 26 октября 2021 г.

[4] Феллер, Уильям (1968). Введение в теорию вероятностей и ее приложения . Том. 1 (3-е изд.). Уайли. п. 38.

[5] Эренфест, Пол; Камерлинг-Оннес, Хайке (1914). «Упрощенный вывод формулы из теории комбинаций, которую Планк положил в основу своей теории излучения» . Труды КНАВ . 17 : 870–873 . Проверено 16 мая 2024 г.

[6] Эренфест, Пол; Камерлинг-Оннес, Хайке (1915). «Упрощенный вывод формулы из теории комбинаций, которую Планк положил в основу своей теории излучения» . Лондонский, Эдинбургский и Дублинский философский журнал и научный журнал . Серия 6. 29 (170): 297–301. дои : 10.1080/14786440208635308 . Проверено 5 декабря 2020 г.

[7] Планк, Макс (1901). «О законе распределения энергии в нормальном спектре» . Анналы физики . 309 (3): 553–563. Стартовый код : 1901АнП...309..553П . дои : 10.1002/andp.19013090310 .

[8] Геархарт, К. (2002). «Планк, квант и историки» (PDF) . Физ. Перспектива . 4 (2): 170–215. Бибкод : 2002PhP.....4..170G . дои : 10.1007/s00016-002-8363-7 . Проверено 16 мая 2024 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]