Монеты в фонтане

Монеты в фонтане — задача комбинаторной математики , включающая производящую функцию . В этой задаче фонтан представляет собой расположение непересекающихся единичных кругов в горизонтальные ряды на плоскости так, чтобы последовательные круги в нижнем ряду касались друг друга и каждый круг в верхнем ряду касался двух монет из следующую строку под ним. Над нижним рядом последовательные монеты не обязаны соприкасаться. Задача состоит в том, сколько разных фонтанов $n$ монеты с $k$ монеты в нижнем ряду. ^[1]

Решение

**Первые несколько членов последовательности** ^[2]^[3]
0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	1	2	3	5	9	15	26	45	78	135	234	...

Приведенная выше последовательность показывает количество способов, которыми n можно сложить монет. Так, например, для 9 монет у нас есть 45 различных способов сложить их в фонтан.Число $f(n,k)$ которое является решением вышеуказанной проблемы, затем определяется коэффициентами полинома следующей производящей функции:

{\begin{aligned}f(n,k)={\dfrac {1}{1-{\dfrac {xy}{1-{\dfrac {x^{2}y}{1-{\dfrac {x^{3}y}{\cdots }}}}}}}}\end{aligned}}

( 1 )

Такая производящая функция широко изучается в ^[4]

В частности, количество таких фонтанов, которые можно создать с помощью n монет, определяется коэффициентами:

{\begin{aligned}f(n)&=&{\dfrac {1}{1-{\dfrac {x}{1-{\dfrac {x^{2}}{1-{\dfrac {x^{3}}{\cdots }}}}}}}}\,\end{aligned}}

( 2 )

В этом легко убедиться, заменив значение y равным 1. Это связано с тем, что, предположим, производящая функция для ( 1 ) имеет вид:

\sum _{n}\sum _{k}C_{n,k}x^{n}y^{k}

затем, если мы хотим получить общее количество фонтанов, нам нужно суммировать по k . Итак, количество фонтанов с n монетами можно определить по формуле:

\sum _{k}C_{n,k}x^{n}y^{k}

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

Доказательство производящей функции ( 1 ). Рассмотрим количество способов формирования фонтана из n монет с k монетами в основании, которое определяется выражением $f(n,k)$ . Теперь рассмотрим количество способов формирования того же самого, но с ограничением, что второй нижний слой (над базовым слоем) не содержит пробелов, т. е. содержит ровно k − 1 монет. Назовем это примитивным фонтаном и обозначим его через $g(n,k)$ . Эти две функции связаны следующим уравнением:

{\begin{aligned}g(n,k)&=f(n-k,k-1)\,\end{aligned}}

( 3 )

Это потому, что мы можем рассматривать примитивный фонтан как обычный фонтан из n - k' монет с k - 1 монетами в базовом слое, поставленными поверх одного слоя из k монет без каких-либо промежутков. Кроме того, рассмотрим обычный фонтан с предполагаемым зазором во предпоследнем слое (относительно базового слоя) в положении r . Итак, обычный фонтан можно рассматривать как совокупность двух фонтанов:

Примитивный фонтан с n монетами и базовым слоем с r монетами.
Обычный фонтан с n - n ' монетами и базовым слоем с k - r монетами.

Итак, мы получаем следующее соотношение:

{\begin{aligned}f(n,k)&=\sum _{r}g(n',r)\times f(n-n',k-r)\end{aligned}}

( 4 )

Теперь мы можем легко наблюдать соотношение производящей функции для ( 4 ):

F(x,y)=1+F(x,y).G(x,y)

( 5 )

и чтобы ( 3 ) было:

G(x,y)=xyF(x,xy)

( 6 )

Подставив ( 6 ) в ( 5 ) и переставив, получим соотношение:

{\begin{aligned}F(x,y)&={\dfrac {1}{1-xyF(x,xy)}}&={\dfrac {1}{1-{\dfrac {xy}{1-x^{2}yF(x,x^{2}y)}}}}&=\cdots &={\dfrac {1}{1-{\dfrac {xy}{1-{\dfrac {x^{2}y}{1-{\dfrac {x^{3}y}{\cdots }}}}}}}}\end{aligned}}

Ссылки

^ Одлыжко А.М. и Уилф Х.С. (1988) Уголок редактора: n монет в фонтане. амер. Математика. Ежемесячно 95 840–843. [1]
^ Слоан, NJA (2000) Интернет-энциклопедия целочисленных последовательностей. Опубликовано в электронном виде в «Энциклопедии последовательностей Слоана».
^ Филипп Дюшон, Филипп Флажоле, Гай Лушар и Жиль Шеффер (2003) «Семплеры Больцмана для случайной генерации комбинаторных структур»
^ Флажоле, П. (1980) Комбинаторные аспекты цепных дробей. Дискретная математика. 32 125–161.

[1] Одлыжко А.М. и Уилф Х.С. (1988) Уголок редактора: n монет в фонтане. амер. Математика. Ежемесячно 95 840–843. [1]

[2] Слоан, NJA (2000) Интернет-энциклопедия целочисленных последовательностей. Опубликовано в электронном виде в «Энциклопедии последовательностей Слоана».

[3] Филипп Дюшон, Филипп Флажоле, Гай Лушар и Жиль Шеффер (2003) «Семплеры Больцмана для случайной генерации комбинаторных структур»

[4] Флажоле, П. (1980) Комбинаторные аспекты цепных дробей. Дискретная математика. 32 125–161.

[1]

[2]

[3]

[4]