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

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

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

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

1

Такие производящие функции подробно изучены в ^[4].

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

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

2

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

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

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

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

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

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

${\displaystyle {\begin{align}g(n,k)&=f(nk,k-1)\,\end{align}}}$

3

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

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

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

${\displaystyle {\begin{align}f(n,k)&=\sum _{r}g(n',r)\times f(nn',kr)\end{align}}}$

4

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

${\displaystyle F(x,y)=1+F(x,y).G(x,y)}$

5

и для ( 3 ) должно быть:

${\displaystyle G(x,y)=xyF(x,xy)}$

6

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

${\displaystyle {\begin{align}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{align}}}$