Coins in a fountain

In combinatorial mathematics, coins in a fountain is an interesting problem with an even more interesting generating function. The problem is described below:

In how many different number of ways can you arrange n coins with k coins at the base such that all the coins above the base layer touch exactly two coins of the lower layer.

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)

Now, simply substituting (6) in (5) 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}}$