A058300 Number of ways of piling up n wine bottles above a row of n+1 bottles at ground level.

1, 1, 1, 3, 7, 16, 43, 115, 303, 813, 2203, 5991, 16371, 44917, 123598, 340988, 942930, 2612735, 7252407, 20163046, 56136326, 156488946, 436739752, 1220157514, 3412116339, 9550192161, 26751643663, 74991516850, 210364915858, 590490257667, 1658484275955

Offset: 0

Author

Roland Bacher, Dec 08 2000

Keywords

• easy
• nonn
• nice

Comments

Related to the Catalan numbers (which count the ways of storing an arbitrary number of bottles above n bottles at ground level).

Related to fountains of n coins (A005169). [Joerg Arndt, Mar 18 2011]

Examples

			a(4) = 7: the seven possibilities are:
..............0.............0.........0...............0.........0............0
.0.0.0.0.....0.0.0.......0.0.0.......0.0...0.....0...0.0.......0.0.0......0.0.0
0.0.0.0.0.,.0.0.0.0.0.,.0.0.0.0.0.,.0.0.0.0.0.,.0.0.0.0.0.,.0.0.0.0.0,.0.0.0.0.0
		

References

• R. P. Stanley, Enumerative Combinatorics (Volume 2); see Exercise 6.19(hhh).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..600
• Andrew M. Odlyzko and Herbert S. Wilf, The editor's corner: n coins in a fountain, Amer. Math. Monthly, 95 (1988), 840-843.

Crossrefs

Cf. A047998.

Programs

Mathematica

terms = 31; initialMax = 5; Clear[g]; g[max_] := g[max] = (Print["max = ", max]; f = 1/Fold[1 - y*x^#2/#1&, 1, Range[max] // Reverse]; b[n_, k_] := SeriesCoefficient[f, {x, 0, n}, {y, 0, k}]; b[0, 0] = 1; Clear[a]; a[n_] := a[n] = b[2n+1, n+1]; Array[a, terms, 0]); g[max = initialMax]; g[max = max+1]; While[g[max] != g[max-1], max = max+1]; A058300 = g[max] (* Jean-François Alcover, Oct 05 2017, after Alois P. Heinz's formula *)

Formula

Coefficient of w^(2*n+1)*z^(n+1) in the formal power series G(w, z) defined by G(w, z)=1+w*z*G(w, w*z).

a(n) = A047998(2n+1,n+1). - Alois P. Heinz, Jun 24 2015

a(n) ~ c * d^n / sqrt(n), where d = 2.8566122635122125634030051... and c = 0.19212135026441477122126... - Vaclav Kotesovec, Jul 17 2019

Extensions

More terms from Alois P. Heinz, Jun 24 2015