cp's OEIS Frontend

A005169 Number of fountains of n coins.

%I A005169 M0708 #175 Feb 16 2025 08:32:28
%S A005169 1,1,1,2,3,5,9,15,26,45,78,135,234,406,704,1222,2120,3679,6385,11081,
%T A005169 19232,33379,57933,100550,174519,302903,525734,912493,1583775,2748893,
%U A005169 4771144,8281088,14373165,24946955,43299485,75153286,130440740,226401112,392955956,682038999,1183789679,2054659669,3566196321,6189714276
%N A005169 Number of fountains of n coins.
%C A005169 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.
%C A005169 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
%C A005169 Also the number of ordered trees with path length n (follows from previous comment via a standard bijection). - _Emeric Deutsch_, Mar 22 2008
%C A005169 Probably first studied by Jim Propp (unpublished).
%C A005169 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
%C A005169 With the additional requirement for weak unimodality one obtains A001524. - _Joerg Arndt_, Dec 09 2012
%D A005169 S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 381.
%D A005169 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005169 Alois P. Heinz, <a href="/A005169/b005169.txt">Table of n, a(n) for n = 0..4178</a> (first 501 terms from T. D. Noe)
%H A005169 Peter Bala, <a href="/A005169/a005169_3.pdf">Some simple continued fraction expansions</a>
%H A005169 P. Flajolet, <a href="http://dx.doi.org/10.1016/0012-365X(80)90050-3">Combinatorial aspects of continued fractions</a>, Discrete Mathematics 32 (1980), pp. 125-161.
%H A005169 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 331.
%H A005169 Atli Fannar Franklín, <a href="https://arxiv.org/abs/2410.07467">Pattern avoidance enumerated by inversions</a>, arXiv:2410.07467 [math.CO], 2024. See pp. 2, 4.
%H A005169 Atli Fannar Franklín, Anders Claesson, Christian Bean, Henning Úlfarsson, and Jay Pantone, <a href="https://arxiv.org/abs/2406.16403">Restricted Permutations Enumerated by Inversions</a>, arXiv:2406.16403 [cs.DM], 2024. See p. 2.
%H A005169 M. L. Glasser, V. Privman, N. M. Svrakic, <a href="http://dx.doi.org/10.1088/0305-4470/20/18/010">Temperley's triangular lattice compact cluster model: exact solution in terms of the q series</a>. J. Phys. A 20 (1987), no. 18, L1275-L1280.
%H A005169 H. W. Gould, R. K. Guy, and N. J. A. Sloane, <a href="/A005169/a005169_5.pdf">Correspondence</a>, 1987.
%H A005169 R. K. Guy, <a href="/A005169/a005169_6.pdf">Letter to N. J. A. Sloane</a>, Sep 25 1986.
%H A005169 R. K. Guy, <a href="/A005728/a005728.pdf">Letter to N. J. A. Sloane, 1987</a>
%H A005169 R. K. Guy, <a href="http://www.jstor.org/stable/2322249">The strong law of small numbers</a>, Amer. Math. Monthly 95 (1988), no. 8, 697-712.
%H A005169 R. K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
%H A005169 R. K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.
%H A005169 Kival Ngaokrajang, <a href="/A005169/a005169_4.pdf">Illustration for initial terms</a>
%H A005169 A. M. Odlyzko and H. S. Wilf, <a href="http://www.jstor.org/stable/2322898">The editor's corner: n coins in a fountain</a>, Amer. Math. Monthly, 95 (1988), 840-843.
%H A005169 A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Example 10.7 (<a href="http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf">pdf</a>, <a href="http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.ps">ps</a>)
%H A005169 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rogers-RamanujanContinuedFraction.html">Rogers-Ramanujan Continued Fraction</a>.
%F A005169 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.
%F A005169 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
%F A005169 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
%F A005169 G.f.: 1/G(0), where G(k)= 1 - x^(k+1)/G(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Jun 29 2013
%F A005169 G.f.: A(x) = P(x)/Q(x) where
%F A005169   P(x) = Sum_{n>=0} (-1)^n* x^(n*(n+1)) / Product_{k=1..n} (1-x^k),
%F A005169   Q(x) = Sum_{n>=0} (-1)^n* x^(n^2) / Product_{k=1..n} (1-x^k),
%F A005169 due to the Rogers-Ramanujan continued fraction identity. - _Paul D. Hanna_, Jul 08 2011
%F A005169 From _Peter Bala_, Dec 26 2012: (Start)
%F A005169 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.
%F A005169 (End)
%F A005169 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
%F A005169 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
%F A005169 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
%e A005169 An example of a fountain with 19 coins:
%e A005169 ... O . O O
%e A005169 .. O O O O O O . O
%e A005169 . O O O O O O O O O
%e A005169 From _Peter Bala_, Dec 26 2012: (Start)
%e A005169 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 + ...)))))))))))).
%e A005169 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 + ...)))))))))))).
%e A005169 (End)
%p A005169 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
%p A005169 # second Maple program:
%p A005169 A005169_G:= proc(x,NK); Digits:=250; Q2:=1;
%p A005169         for k from NK by -1 to 0 do  Q1:=1-x^k/Q2; Q2:=Q1; od;
%p A005169         Q3:=Q2; S:=1-Q3;
%p A005169 end:
%p A005169 series(A005169_G(x, 20), x, 21); # _Sergei N. Gladkovskii_, Dec 18 2011
%t A005169 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_ *)
%t A005169 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 *)
%t A005169 b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j], {j, 1, Min[i+1, n]}]];
%t A005169 c[n_] :=  b[n, 0] - b[n-1, 0];
%t A005169 c /@ Range[0, 50] // Accumulate  (* _Jean-François Alcover_, Nov 14 2020, after _Alois P. Heinz_ in A289080 *)
%o A005169 (PARI) /* using the g.f. from p. L1278 of the Glasser, Privman, Svrakic paper */
%o A005169 N=30;  x='x+O('x^N);
%o A005169 P(k)=sum(n=0,N, (-1)^n*x^(n*(n+1+k))/prod(j=1,n,1-x^j));
%o A005169 G=1+x*P(1)/( (1-x)*P(1)-x^2*P(2) );
%o A005169 Vec(G) /* _Joerg Arndt_, Feb 10 2011 */
%o A005169 (PARI) /* As a continued fraction: */
%o A005169 {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_ */
%o A005169 (PARI) /* By the Rogers-Ramanujan continued fraction identity: */
%o A005169 {a(n)=local(A=1+x,P,Q);
%o A005169 P=sum(m=0,sqrtint(n),(-1)^m*x^(m*(m+1))/prod(k=1,m,1-x^k));
%o A005169 Q=sum(m=0,sqrtint(n),(-1)^m*x^(m^2)/prod(k=1,m,1-x^k));
%o A005169 A=P/(Q+x*O(x^n));polcoeff(A,n)}  /* _Paul D. Hanna_ */
%o A005169 (Haskell)
%o A005169 a005169 0 = 1
%o A005169 a005169 n = a168396 n 1  -- _Reinhard Zumkeller_, Sep 13 2013; corrected by _R. J. Mathar_, Sep 16 2013
%Y A005169 Cf. A001524, A192728, A192729, A192730, A111317, A143951, A285903, A226999 (inverse Euler transform), A291148 (convolution inverse).
%Y A005169 First column of A168396. - _Franklin T. Adams-Watters_, Nov 24 2009
%Y A005169 Diagonal of A185646.
%Y A005169 Row sums of A047998. Column sums of A138158. - _Emeric Deutsch_, Mar 22 2008
%K A005169 nonn,easy,nice
%O A005169 0,4
%A A005169 _N. J. A. Sloane_
%E A005169 More terms from _David W. Wilson_, Apr 30 2001