Coins in a fountain

Coins in a fountain is a problem in combinatorial mathematics that involves a 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.[1]

Solution:

First few terms of the sequence[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 | ...

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 [math]\displaystyle{ f(n,k) }[/math] which is the solution for the above stated problem is then given by the coefficients of the polynomial of the following generating function:

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

|
|

Such generating function are extensively studied in[4]

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

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

|
|

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:

[math]\displaystyle{ \sum_{n}\sum_{k} C_{n,k} x^n y^k }[/math]

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:

[math]\displaystyle{ \sum_{k}C_{n,k}x^ny^k }[/math]

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

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 [math]\displaystyle{ f(n,k) }[/math]. 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 [math]\displaystyle{ g(n,k) }[/math]. The two functions are related by the following equation:

[math]\displaystyle{ \begin{align} g(n,k) &= f(n-k, k-1) \, \end{align} }[/math]

|
|

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:

[math]\displaystyle{ \begin{align} f(n,k) &= \sum_{r}g(n',r)\times f(n-n', k-r) \end{align} }[/math]

|
|

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

[math]\displaystyle{ F(x,y) = 1 + F(x,y).G(x,y) }[/math]

|
|

and for (3) to be:

[math]\displaystyle{ G(x,y) = xyF(x,xy) }[/math]

|
|

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

[math]\displaystyle{ \begin{align} F(x,y) &= \dfrac{1}{1-xyF(x,xy)} &= \dfrac{1}{1-\dfrac{xy}{1-x^2yF(x,x^2y)}} &= \cdots &= \dfrac{1}{1-\dfrac{xy}{1-\dfrac{x^2y}{1-\dfrac{x^3y}{\cdots}}}} \end{align} }[/math]

## References

1. ↑ Odlyzko, A. M. and Wilf, H. S. (1988) The editor’s corner: n coins in a fountain. Amer. Math. Monthly 95 840–843.[1]
2. ↑ Sloane, N. J. A. (2000) The On-Line Encyclopedia of Integer Sequences. Published electronically at "Sloane's encyclopedia of sequences"
3. ↑ Phillipe Duchon, Phillipe Flajolet, Guy Louchard and Gilles Schaeffer (2003)"Boltzmann Samplers for the Random Generation of Combinatorial Structures"
4. ↑ Flajolet, P. (1980) Combinatorial aspects of continued fractions. Discrete Math. 32 125–161.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Coins in a fountain. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Coins_in_a_fountain&oldid=17694"