login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005169 Number of fountains of n coins.
(Formerly M0708)
66
1, 1, 1, 2, 3, 5, 9, 15, 26, 45, 78, 135, 234, 406, 704, 1222, 2120, 3679, 6385, 11081, 19232, 33379, 57933, 100550, 174519, 302903, 525734, 912493, 1583775, 2748893, 4771144, 8281088, 14373165, 24946955, 43299485, 75153286, 130440740, 226401112, 392955956, 682038999, 1183789679, 2054659669, 3566196321, 6189714276 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

A fountain is formed by starting with a row of coins, then stacking additional coins on top so that each new coin touches two in the previous row.

Also the number of Dyck paths for which the sum of the heights of the vertices that terminate an upstep (i.e., peaks and doublerises) is n. Example: a(4)=3 because we have UDUUDD, UUDDUD and UDUDUDUD. - Emeric Deutsch, Mar 22 2008

Also the number of ordered trees with path length n (follows from previous comment via a standard bijection). - Emeric Deutsch, Mar 22 2008

Probably first studied by Jim Propp (unpublished).

Number of compositions of n with c(1) = 1 and c(i+1) <= c(i) + 1. (Slide each row right 1/2 step relative to the row below, and count the columns.) - Franklin T. Adams-Watters, Nov 24 2009

With the additional requirement for weak unimodality one obtains A001524. - Joerg Arndt, Dec 09 2012

REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 381.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..4178 (first 501 terms from T. D. Noe)

P. Bala, Some simple continued fraction expansions

P. Flajolet, Combinatorial aspects of continued fractions, Discrete Mathematics 32 (1980), pp. 125-161.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 331.

M. L. Glasser, V. Privman, N. M. Svrakic, Temperley's triangular lattice compact cluster model: exact solution in terms of the q series. J. Phys. A 20 (1987), no. 18, L1275-L1280.

H. W. Gould, R. K. Guy, and N. J. A. Sloane, Correspondence, 1987.

R. K. Guy, Letter to N. J. A. Sloane, Sep 25 1986.

R. K. Guy, Letter to N. J. A. Sloane, 1987

R. K. Guy, The strong law of small numbers, Amer. Math. Monthly 95 (1988), no. 8, 697-712.

R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]

R. K. Guy and N. J. A. Sloane, Correspondence, 1988.

Kival Ngaokrajang, Illustration for initial terms

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

A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Example 10.7 (pdf, ps)

Eric Weisstein's World of Mathematics, Rogers-Ramanujan Continued Fraction.

FORMULA

A005169(n) = f(n, 1), where f(n, p) = 0 if p > n, 1 if p = n, Sum(1 <= q <= p+1; f(n-p, q)) if p < n.

G.f.: F(t) = Sum_{k>=0} P[k], where P[0]=1, P[n] = t*Sum_{j= 0..n-1} P[j]*P[n-j-1]*t^(n-j-1) for n >= 1. - Emeric Deutsch, Mar 22 2008

G.f.: 1/(1-x/(1-x^2/(1-x^3/(1-x^4/(1-x^5/(...)))))) [given on the first page of the Odlyzko/Wilf reference]. - Joerg Arndt, Mar 08 2011

G.f.: 1/G(0), where G(k)= 1 - x^(k+1)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Jun 29 2013

G.f.: A(x) = P(x)/Q(x) where

  P(x) = Sum_{n>=0} (-1)^n* x^(n*(n+1)) / Product(k=1..n} (1-x^k),

  Q(x) = Sum_{n>=0} (-1)^n* x^(n^2) / Product(k=1..n} (1-x^k),

due to the Rogers-Ramanujan continued fraction identity. - Paul D. Hanna, Jul 08 2011

From Peter Bala, Dec 26 2012: (Start)

Let F(x) denote the o.g.f. of this sequence. For positive integer n >= 3, the real number F(1/n) has the simple continued fraction expansion 1 + 1/(n-2 + 1/(1 + 1/(n-2 + 1/(1 + 1/(n^2-2 + 1/(1 + 1/(n^2-2 + 1/(1 + ...)))))))), while for n >= 2, F(-1/n) has the simple continued fraction expansion 1/(1 + 1/(n-1 + 1/(1 + 1/(n-1 + 1/(n^2-1 + 1/(1 + 1/(n^2-1 + 1/(n^3-1 + 1/(1 + ...))))))))). Examples are given below. Cf. A111317 and A143951.

(End)

a(n) = c * x^(-n) + O((5/3)^n), where c = 0.312363324596741... and x = 0.576148769142756... (Odlyzko & Wilf 1988). - Vaclav Kotesovec, Jul 18 2013

G.f.: G(0), where G(k)= 1 - x^(k+1)/(x^(k+1) - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 06 2013

G.f.: 1 - 1/x + 1/(x*W(0)), where W(k)= 1 - x^(2*k+2)/(1 - x^(2*k+1)/W(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013

EXAMPLE

An example of a fountain with 19 coins:

... O . O O

.. O O O O O O . O

. O O O O O O O O O

From Peter Bala, Dec 26 2012: (Start)

F(1/10) = Sum_{n >= 0} a(n)/10^n has the simple continued fraction expansion 1 + 1/(8 + 1/(1 + 1/(8 + 1/(1 + 1/(98 + 1/(1 + 1/(98 + 1/(1 + 1/(998 + 1/(1 + 1/(998 + 1/(1 + ...)))))))))))).

F(-1/10) = Sum_{n >= 0} (-1)^n*a(n)/10^n has the simple continued fraction expansion 1/(1 + 1/(9 + 1/(1 + 1/(9 + 1/(99 + 1/(1 + 1/(99 + 1/(999 + 1/(1 + 1/(999 + 1/(9999 + 1/(1 + ...)))))))))))).

(End)

MAPLE

P[0]:=1: for n to 40 do P[n]:=sort(expand(t*(sum(P[j]*P[n-j-1]*t^(n-j-1), j= 0..n-1)))) end do: F:=sort(sum(P[k], k=0..40)): seq(coeff(F, t, j), j=0..36); # Emeric Deutsch, Mar 22 2008

# second Maple program:

A005169_G:= proc(x, NK); Digits:=250; Q2:=1;

        for k from NK by -1 to 0 do  Q1:=1-x^k/Q2; Q2:=Q1; od;

        Q3:=Q2; S:=1-Q3;

end:

series(A005169_G(x, 20), x, 21); # Sergei N. Gladkovskii, Dec 18 2011

MATHEMATICA

m = 36; p[0] = 1; p[n_] := p[n] = Expand[t*Sum[p[j]*p[n-j-1]*t^(n-j-1), {j, 0, n-1}]]; f[t_] = Sum[p[k], {k, 0, m}]; CoefficientList[Series[f[t], {t, 0, m}], t] (* Jean-François Alcover, Jun 21 2011, after Emeric Deutsch *)

max = 43; Series[1-Fold[Function[1-x^#2/#1], 1, Range[max, 0, -1]], {x, 0, max}] // CoefficientList[#, x]& (* Jean-François Alcover, Sep 16 2014 *)

PROG

(PARI) /* using the g.f. from p. L1278 of the Glasser, Privman, Svrakic paper */

N=30;  x='x+O('x^N);

P(k)=sum(n=0, N, (-1)^n*x^(n*(n+1+k))/prod(j=1, n, 1-x^j));

G=1+x*P(1)/( (1-x)*P(1)-x^2*P(2) );

Vec(G) /* Joerg Arndt, Feb 10 2011 */

(PARI) /* As a continued fraction: */

{a(n)=local(A=1+x, CF); CF=1+x; for(k=0, n, CF=1/(1-x^(n-k+1)*CF+x*O(x^n)); A=CF); polcoeff(A, n)} /* Paul D. Hanna */

(PARI) /* By the Rogers-Ramanujan continued fraction identity: */

{a(n)=local(A=1+x, P, Q);

P=sum(m=0, sqrtint(n), (-1)^m*x^(m*(m+1))/prod(k=1, m, 1-x^k));

Q=sum(m=0, sqrtint(n), (-1)^m*x^(m^2)/prod(k=1, m, 1-x^k));

A=P/(Q+x*O(x^n)); polcoeff(A, n)}  /* Paul D. Hanna */

(Haskell)

a005169 0 = 1

a005169 n = a168396 n 1  -- Reinhard Zumkeller, Sep 13 2013; corrected by R. J. Mathar, Sep 16 2013

CROSSREFS

Cf. A001524, A192728, A192729, A192730, A111317, A143951, A285903.

First column of A168396. - Franklin T. Adams-Watters, Nov 24 2009

Diagonal of A185646.

Row sums of A047998. Column sums of A138158. - Emeric Deutsch, Mar 22 2008

Sequence in context: A185648 A228645 A185649 * A129852 A065954 A067847

Adjacent sequences:  A005166 A005167 A005168 * A005170 A005171 A005172

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson, Apr 30 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 20 11:59 EDT 2017. Contains 293601 sequences.