|
| |
|
|
A005169
|
|
Number of fountains of n coins.
(Formerly M0708)
|
|
16
| |
|
|
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
(list; graph; refs; listen; history; 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.
a(n)=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 beacuse we have UDUUDD, UUDDUD and UDUDUDUD. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 22 2008
a(n)=number of ordered trees with path length n (follows from previous comment via a standard bijection). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 22 2008
Row sums of A047998. Column sums of A138158. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 22 2008
Probably first studied by Jim Propp (unpublished).
Number of compositions of n with a(1) = 1 and a(i+1) <= a(i) + 1. (Slide each row right 1/2 step relative to the row below, and count the columns.) [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Nov 24 2009]
|
|
|
REFERENCES
| Glasser, M. L.; Privman, V.; Svrakic, N. M.; Temperley's triangular lattice compact cluster model: exact solution in terms of the $q$ series. J. Phys. A 20 (1987), no. 18, L1275-L1280.
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
A. M. Odlyzko and H. S. Wilf, The editor's corner: n coins in a fountain, Amer. Math. Monthly, 95 (1988), 840-843.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..500
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
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(P[k],k=0..infinity), where P[0]=1, P[n]=t*sum(P[j]*P[n-j-1]*t^(n-j-1),j= 0..n-1) for n>=1. - Emeric Deutsch (deutsch(AT)duke.poly.edu), 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.: 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. [From Paul D. Hanna, Jul 08 2011]
|
|
|
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
|
|
|
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 (deutsch(AT)duke.poly.edu), Mar 22 2008
restart:
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; . - 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]
(* From Jean-François Alcover, Jun 21 2011, after E. Deutsch *)
|
|
|
PROG
| (PARI) /* Computation via g.f. from page L1278 of 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) /* show terms */ /* 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)} /* From 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)} /* From Paul D. Hanna */
|
|
|
CROSSREFS
| Cf. A047998, A138158.
First column of A168396. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Nov 24 2009]
Cf. A192728, A192729, A192730.
Sequence in context: A096816 A018157 A003065 * A129852 A065954 A067847
Adjacent sequences: A005166 A005167 A005168 * A005170 A005171 A005172
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from David W. Wilson (davidwwilson(AT)comcast.net), Apr 30 2001
|
| |
|
|
