|
|
A005169
|
|
Number of fountains of n coins.
(Formerly M0708)
|
|
79
|
|
|
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
|
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)
|
|
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. f=A168396.
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.: 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
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 = A347901 = 0.576148769142756... is the lowest root of the equation Q(x) = 0, Q(x) see above (Odlyzko & Wilf 1988). - Vaclav Kotesovec, Jul 18 2013, updated Sep 24 2020
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
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:
|
|
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 *)
b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j], {j, 1, Min[i+1, n]}]];
c[n_] := b[n, 0] - b[n-1, 0];
|
|
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) );
(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));
(Haskell)
a005169 0 = 1
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|