A291148 -id:A291148 - cp's OEIS frontend

A005169 Number of fountains of n coins.

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

Offset: 0

N. J. A. Sloane

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

			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)

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).

Alois P. Heinz, Table of n, a(n) for n = 0..4178 (first 501 terms from T. D. Noe)
Peter 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.
Atli Fannar Franklín, Pattern avoidance enumerated by inversions, arXiv:2410.07467 [math.CO], 2024. See pp. 2, 4.
Atli Fannar Franklín, Anders Claesson, Christian Bean, Henning Úlfarsson, and Jay Pantone, Restricted Permutations Enumerated by Inversions, arXiv:2406.16403 [cs.DM], 2024. See p. 2.
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.

Cf. A001524, A192728, A192729, A192730, A111317, A143951, A285903, A226999 (inverse Euler transform), A291148 (convolution inverse).
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

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

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

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];
c /@ Range[0, 50] // Accumulate  (* Jean-François Alcover, Nov 14 2020, after Alois P. Heinz in A289080 *)

/* 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 */

/* 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 */

/* 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 */

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.: 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 = 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

More terms from David W. Wilson, Apr 30 2001

A291874 Expansion of 1 - x/(1 - x^3/(1 - x^5/(1 - x^7/(1 - x^9/(1 - ... - x^(2*k-1)/(1 - ...)))))), a continued fraction.

Original entry on oeis.org

1, -1, 0, 0, -1, 0, 0, -1, 0, -1, -1, 0, -2, -1, -1, -3, -2, -3, -4, -4, -6, -7, -8, -11, -13, -16, -20, -24, -31, -37, -46, -58, -70, -88, -108, -133, -167, -204, -252, -315, -386, -479, -594, -731, -909, -1122, -1386, -1720, -2124, -2628, -3254, -4022, -4980

Offset: 0

Seiichi Manyama, Sep 04 2017

sign

Seiichi Manyama, Table of n, a(n) for n = 0..10000

Cf. A049346, A143951, A227310, A291148 (similar sequence).

Convolution inverse of A143951.

a(n) = -A227310(n) for n > 0.

A291147 Expansion of 1 - x/(1 - x^8/(1 - x^27/(1 - x^64/(1 - x^125/(1 - x^216/(1 - ... - x^(n^3)/(1 - ...))))))), a continued fraction.

Original entry on oeis.org

1, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, -2, 0, 0, 0, 0, -1, 0, 0, -3, 0, 0, 0, 0, -1, 0, 0, -4, 0, 0, -1, 0, -1, 0, 0, -5, 0, 0, -3, 0, -1, 0, 0, -6, 0, 0, -6, 0, -1

Offset: 0

Seiichi Manyama, Aug 18 2017

sign

Cf. A290975, A291148.

Convolution inverse of A291146.

A291701 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of k-th power of continued fraction 1 - x/(1 - x^2/(1 - x^3/(1 - x^4/(1 - x^5/(1 - ...))))).

Original entry on oeis.org

1, 1, 0, 1, -1, 0, 1, -2, 0, 0, 1, -3, 1, -1, 0, 1, -4, 3, -2, 0, 0, 1, -5, 6, -4, 2, -1, 0, 1, -6, 10, -8, 6, -2, -1, 0, 1, -7, 15, -15, 13, -6, 1, -1, 0, 1, -8, 21, -26, 25, -16, 6, 0, -2, 0, 1, -9, 28, -42, 45, -36, 18, -3, 0, -2, 0, 1, -10, 36, -64, 77, -72

Offset: 0

Seiichi Manyama, Aug 30 2017

			Square array begins:
   1,  1,  1,  1,  1, ...
   0, -1, -2, -3, -4, ...
   0,  0,  1,  3,  6, ...
   0, -1, -2, -4, -8, ...
   0,  0,  2,  6, 13, ...

Columns k=0..1 give A000007, A291148.
Rows n=0..1 give A000012, A001489.
Main diagonal gives A291702.
Cf. A291652.

G.f. of column k: (1 - x/(1 - x^2/(1 - x^3/(1 - x^4/(1 - x^5/(1 - ...))))))^k, a continued fraction.

A291875 Expansion of 1 - x/(1 - x/(1 - x^2/(1 - x^2/(1 - x^3/(1 - x^3/(1 - x^4/(1 - x^4/ ...))))))), a continued fraction.

Original entry on oeis.org

1, -1, -1, -1, -2, -3, -6, -10, -19, -34, -63, -115, -213, -391, -723, -1333, -2463, -4547, -8403, -15522, -28686, -53006, -97963, -181042, -334606, -618415, -1142994, -2112545, -3904592, -7216810, -13338856, -24654268, -45568784, -84225393, -155675230

Offset: 0

Seiichi Manyama, Sep 04 2017

sign

Cf. A006958, A227309, A291148 (similar sequence).

a(n) = -A227309(n-1) for n > 0.

A293719 Expansion of the series reversion of x/(1 - x^2/(1 - x^3/(1 - x^4/(1 - x^5/(1 - ...))))), a continued fraction.

Original entry on oeis.org

1, 0, -1, 0, 2, -1, -5, 7, 13, -37, -27, 175, -2, -768, 521, 3120, -4457, -11394, 28363, 34269, -157108, -56124, 790091, -270661, -3638871, 3821242, 15153860, -29235087, -54470264, 182441139, 143800906, -1008933847, -16080652, 5067562024, -3456404771, -23114068193, 33623924709, 93441615451

Offset: 1

Ilya Gutkovskiy, Oct 15 2017

sign

Reversion of 1 - 1/g(x) where g(x) = g.f. for A005169.

N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Series Reversion
Index entries for reversions of series

Cf. A005169, A291148, A291377.

nmax = 38; Rest[CoefficientList[InverseSeries[Series[x/(1 + ContinuedFractionK[-x^k, 1, {k, 2, nmax}]), {x, 0, nmax}], x], x]]
nmax = 38; Rest[CoefficientList[InverseSeries[Series[1 - Sum[(-1)^i x^(i^2)/Product[(1 - x^j), {j, 1, i}], {i, 0, nmax}]/Sum[(-1)^i x^(i (i + 1))/Product[(1 - x^j), {j, 1, i}], {i, 0, nmax}], {x, 0, nmax}], x], x]]

G.f. A(x) satisfies: A(x)/(1 - A(x)^2/(1 - A(x)^3/(1 - A(x)^4/(1 - A(x)^5/(1 - ...))))) = x.

A337048 Triangle T(n,k) read by rows: the number of fountains of n coins composed of k inseparable fountains of coins placed side-by-side.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 1, 0, 3, 0, 1, 1, 3, 0, 4, 0, 1, 1, 2, 6, 0, 5, 0, 1, 2, 4, 3, 10, 0, 6, 0, 1, 2, 6, 10, 4, 15, 0, 7, 0, 1, 4, 7, 12, 20, 5, 21, 0, 8, 0, 1, 4, 14, 18, 20, 35, 6, 28, 0, 9, 0, 1, 7, 15, 33, 39, 30, 56, 7, 36, 0, 10, 0, 1, 9, 28, 39, 64, 75, 42, 84, 8, 45, 0, 11, 0, 1, 13, 35, 75, 86, 110

Offset: 1

R. J. Mathar, Aug 12 2020

A fountain of coins is called "inseparable" here if it cannot be split into 2 fountains of coins by a vertical cut without slicing a coin. That means: inseparable fountains have "full" second rows. They are basically counted in A291148 (apart from a sign).

The ordinary generating function of column k is g(x)^k, where g(x) = x +x^3 +x5 +x^6+.. is the ordinary generating function of column k=1 and g(x) is also the INVERTi transform of A005169.

			The triangle starts for n>=1, 1<=k<=n (row sums after semicolons) as
   1 ; 1
   0   1 ; 1
   1   0   1 ; 2
   0   2   0   1 ; 3
   1   0   3   0   1 ; 5
   1   3   0   4   0   1 ; 9
   1   2   6   0   5   0   1 ; 15
   2   4   3  10   0   6   0   1 ; 26
   2   6  10   4  15   0   7   0   1 ; 45
   4   7  12  20   5  21   0   8   0   1 ; 78
   4  14  18  20  35   6  28   0   9   0   1 ; 135
   7  15  33  39  30  56   7  36   0  10   0   1 ; 234
   9  28  39  64  75  42  84   8  45   0  11   0   1 ; 406
  13  35  75  86 110 132  56 120   9  55   0  12   0   1 ; 704
  19  56  94 164 171 174 217  72 165  10  66   0  13   0   1 ; 1222
  25  80 162 212 315 315 259 338  90 220  11  78   0  14   0   1 ; 2120
  38 114 228 384 430 552 546 368 504 110 286  12  91   0  15   0   1 ; 3679
  51 174 349 538 800 810 903 900 504 725 132 364  13 105   0  16   0   1 ; 6385

Cf. A005169 (row sums), A291148 (k=1, reversed sign).

cp's OEIS Frontend

A005169 Number of fountains of n coins.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A291874 Expansion of 1 - x/(1 - x^3/(1 - x^5/(1 - x^7/(1 - x^9/(1 - ... - x^(2*k-1)/(1 - ...)))))), a continued fraction.

Views

Author

Keywords

Links

Crossrefs

Formula

A291147 Expansion of 1 - x/(1 - x^8/(1 - x^27/(1 - x^64/(1 - x^125/(1 - x^216/(1 - ... - x^(n^3)/(1 - ...))))))), a continued fraction.

Views

Author

Keywords

Crossrefs

Formula

A291701 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of k-th power of continued fraction 1 - x/(1 - x^2/(1 - x^3/(1 - x^4/(1 - x^5/(1 - ...))))).

Views

Author

Keywords

Examples

Crossrefs

Formula

A291875 Expansion of 1 - x/(1 - x/(1 - x^2/(1 - x^2/(1 - x^3/(1 - x^3/(1 - x^4/(1 - x^4/ ...))))))), a continued fraction.

Views

Author

Keywords

Crossrefs

Formula

A293719 Expansion of the series reversion of x/(1 - x^2/(1 - x^3/(1 - x^4/(1 - x^5/(1 - ...))))), a continued fraction.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A337048 Triangle T(n,k) read by rows: the number of fountains of n coins composed of k inseparable fountains of coins placed side-by-side.

Views

Author

Keywords

Comments

Examples

Crossrefs