Coins in a fountain


Coins in a fountain is a problem in combinatorial mathematics that involves a generating function. The problem is described below:
Solution:
012345678910111213
111235915264578135234...

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 which is the solution for the above stated problem is then given by the coefficients of the polynomial of the following generating function:
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:
This is easily seen by substituting the value of y to be 1.
This is because, suppose the generating function for is of the form:
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:
which can be obtained by substituting the value of y to be 1 and observing the coefficient of xn.
Proof of generating function.
Consider the number of ways of forming a fountain of n coins with k coins at base to be given by. Now, consider the number of ways of forming the same but with the restriction that the second most bottom layer contains no gaps, i.e. it contains exactly k − 1 coins. Let this be called primitive fountain and denote it by. The two functions are related by the following equation:
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 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:
Now, we can easily observe the generating function relation for to be:
and for to be:
Now, simply substituting in we get the relation: