Coins in a fountain

Last updated May 21, 2024

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.^[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 $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^[4]

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:

A primitive fountain with n' coins in it and base layer having r coins.
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}}

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

A finite difference is a mathematical expression of the form $f (x + b) - f (x + a)$ . If a finite difference is divided by $b - a$ , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the numerical solution of differential equations, especially boundary value problems.

In algebraic number theory, an algebraic integer is a complex number that is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial whose coefficients are integers. The set of all algebraic integers $A$ is closed under addition, subtraction and multiplication and therefore is a commutative subring of the complex numbers.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Catalan.

Flight dynamics is the science of air vehicle orientation and control in three dimensions. The three critical flight dynamics parameters are the angles of rotation in three dimensions about the vehicle's center of gravity (cg), known as pitch, roll and yaw. These are collectively known as aircraft attitude, often principally relative to the atmospheric frame in normal flight, but also relative to terrain during takeoff or landing, or when operating at low elevation. The concept of attitude is not specific to fixed-wing aircraft, but also extends to rotary aircraft such as helicopters, and dirigibles, where the flight dynamics involved in establishing and controlling attitude are entirely different.

In statistics, the Pearson correlation coefficient (PCC) is a correlation coefficient that measures linear correlation between two sets of data. It is the ratio between the covariance of two variables and the product of their standard deviations; thus, it is essentially a normalized measurement of the covariance, such that the result always has a value between −1 and 1. As with covariance itself, the measure can only reflect a linear correlation of variables, and ignores many other types of relationships or correlations. As a simple example, one would expect the age and height of a sample of teenagers from a high school to have a Pearson correlation coefficient significantly greater than 0, but less than 1.

In mathematics, Euler's pentagonal number theorem relates the product and series representations of the Euler function. It states that

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

<span class="mw-page-title-main">Boolean function</span> Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets S_i indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in S_n for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

In mathematics, a surface is a mathematical model of the common concept of a surface. It is a generalization of a plane, but, unlike a plane, it may be curved; this is analogous to a curve generalizing a straight line.

In mathematics, and more specifically in analysis, a holonomic function is a smooth function of several variables that is a solution of a system of linear homogeneous differential equations with polynomial coefficients and satisfies a suitable dimension condition in terms of D-modules theory. More precisely, a holonomic function is an element of a holonomic module of smooth functions. Holonomic functions can also be described as differentiably finite functions, also known as D-finite functions. When a power series in the variables is the Taylor expansion of a holonomic function, the sequence of its coefficients, in one or several indices, is also called holonomic. Holonomic sequences are also called P-recursive sequences: they are defined recursively by multivariate recurrences satisfied by the whole sequence and by suitable specializations of it. The situation simplifies in the univariate case: any univariate sequence that satisfies a linear homogeneous recurrence relation with polynomial coefficients, or equivalently a linear homogeneous difference equation with polynomial coefficients, is holonomic.

Zhegalkinpolynomials, also known as algebraic normal form, are a representation of functions in Boolean algebra. Introduced by the Russian mathematician Ivan Ivanovich Zhegalkin in 1927, they are the polynomial ring over the integers modulo 2. The resulting degeneracies of modular arithmetic result in Zhegalkin polynomials being simpler than ordinary polynomials, requiring neither coefficients nor exponents. Coefficients are redundant because 1 is the only nonzero coefficient. Exponents are redundant because in arithmetic mod 2, x² = x. Hence a polynomial such as 3x²y⁵z is congruent to, and can therefore be rewritten as, xyz.

In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It can be used to solve many simple counting problems, such as how many ways there are to put $n$ indistinguishable balls into $k$ distinguishable bins.

In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically just one. These algorithms are designed to operate with limited memory, generally logarithmic in the size of the stream and/or in the maximum value in the stream, and may also have limited processing time per item.

In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways $n$ people can be connected by person-to-person telephone calls. These numbers also describe the number of matchings of a complete graph on $n$ vertices, the number of permutations on $n$ elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values

A Boltzmann sampler is an algorithm intended for random sampling of combinatorial structures. If the object size is viewed as its energy, and the argument of the corresponding generating function is interpreted in terms of the temperature of the physical system, then a Boltzmann sampler returns an object from a classical Boltzmann distribution.

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Odlyzko, A. M. and Wilf, H. S. (1988) The editor’s corner: n coins in a fountain. Amer. Math. Monthly 95 840–843.

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

[1]

[2]

[3]

[4]