Coins in a fountain

Coins in a fountain is a problem in combinatorial mathematics that involves a generating function. In this problem, a fountain is an arrangement of non-overlapping unit circles into horizontal rows in the plane so that consecutive circles in the bottom row are tangent to each other, and such that each circle in a higher row is tangent to two coins from the next row below it. Above the bottom row, consecutive coins are not required to touch. The problem asks for the number of different fountains of $n$ coins with $k$ coins in the bottom row.

Solution

First few terms of the sequence

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	...

The above sequence show the number of ways in which n coins can be stacked. So, for example for 9 coins we have 45 different ways of stacking them in a fountain. The number $f(n,k)$ which is the solution for the above stated problem is then given by the coefficients of the polynomial of the following generating function:

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

Such generating function are extensively studied in

Specifically, the number of such fountains that can be created using n coins is given by the coefficients of:

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

This is easily seen by substituting the value of y to be 1. This is because, suppose the generating function for (1) is of the form:

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

then, if we want to get the total number of fountains we need to do summation over k. So, the number of fountains with n total coins can be given by:

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

which can be obtained by substituting the value of y to be 1 and observing the coefficient of xⁿ.

Proof of generating function (1). Consider the number of ways of forming a fountain of n coins with k coins at base to be given by $f(n,k)$. Now, consider the number of ways of forming the same but with the restriction that the second most bottom layer (above the base layer) contains no gaps, i.e. it contains exactly k − 1 coins. Let this be called primitive fountain and denote it by $g(n,k)$. The two functions are related by the following equation:

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

This is because, we can view the primitive fountain as a normal fountain of n − k' coins with k − 1 coins in the base layer staked on top of a single layer of k coins without any gaps. Also, consider a normal fountain with a supposed gap in the second last layer (w.r.t. the base layer) in the r position. So, the normal fountain can be viewed as a set of two fountains:

1. A primitive fountain with n' coins in it and base layer having r coins.
2. A normal fountain with n − n' coins in it and the base layer having k − r coins.

So, we get the following relation:

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

Now, we can easily observe the generating function relation for (4) to be:

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

and for (3) to be:

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

Substituting (6) in (5) and re-arranging, we get the relation:

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