A047998 Triangle of numbers a(n,k) = number of "fountains" with n coins, k in the bottom row.
1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 3, 4, 1, 0, 0, 0, 0, 3, 6, 5, 1, 0, 0, 0, 0, 2, 7, 10, 6, 1, 0, 0, 0, 0, 1, 7, 14, 15, 7, 1, 0, 0, 0, 0, 1, 5, 17, 25, 21, 8, 1, 0, 0, 0, 0, 0, 5, 16, 35, 41, 28, 9, 1, 0, 0, 0, 0, 0, 3, 16, 40, 65, 63, 36, 10, 1, 0, 0, 0, 0, 0, 2, 14, 43, 86, 112, 92, 45, 11, 1, 0, 0, 0, 0, 0, 1, 11, 44, 102, 167, 182, 129, 55, 12, 1, 0, 0, 0, 0, 0, 1, 9, 40, 115, 219, 301, 282, 175, 66, 13, 1
Offset: 0
Examples
Triangle begins: 00: 1; 01: 0,1; 02: 0,0,1; 03: 0,0,1,1; 04: 0,0,0,2,1; 05: 0,0,0,1,3,1; 06: 0,0,0,1,3,4,1; 07: 0,0,0,0,3,6,5,1; 08: 0,0,0,0,2,7,10,6,1; 09: 0,0,0,0,1,7,14,15,7,1; 10: 0,0,0,0,1,5,17,25,21,8,1; 11: 0,0,0,0,0,5,16,35,41,28,9,1; 12: 0,0,0,0,0,3,16,40,65,63,36,10,1; 13: 0,0,0,0,0,2,14,43,86,112,92,45,11,1; 14: 0,0,0,0,0,1,11,44,102,167,182,129,55,12,1; 15: 0,0,0,0,0,1,9,40,115,219,301,282,175,66,13,1; 16: 0,0,0,0,0,0,7,37,118,268,434,512,420,231,78,14,1; 17: 0,0,0,0,0,0,5,32,118,303,574,806,831,605,298,91,15,1; ... From _Joerg Arndt_, Mar 25 2014: (Start) The compositions (compositions starting with part 1 and up-steps <= 1) corresponding to row n=8 with their base lengths are: 01: [ 1 2 3 2 ] 4 02: [ 1 2 2 3 ] 4 03: [ 1 2 3 1 1 ] 5 04: [ 1 2 2 2 1 ] 5 05: [ 1 1 2 3 1 ] 5 06: [ 1 2 2 1 2 ] 5 07: [ 1 2 1 2 2 ] 5 08: [ 1 1 2 2 2 ] 5 09: [ 1 1 1 2 3 ] 5 10: [ 1 2 2 1 1 1 ] 6 11: [ 1 2 1 2 1 1 ] 6 12: [ 1 1 2 2 1 1 ] 6 13: [ 1 2 1 1 2 1 ] 6 14: [ 1 1 2 1 2 1 ] 6 15: [ 1 1 1 2 2 1 ] 6 16: [ 1 2 1 1 1 2 ] 6 17: [ 1 1 2 1 1 2 ] 6 18: [ 1 1 1 2 1 2 ] 6 19: [ 1 1 1 1 2 2 ] 6 20: [ 1 2 1 1 1 1 1 ] 7 21: [ 1 1 2 1 1 1 1 ] 7 22: [ 1 1 1 2 1 1 1 ] 7 23: [ 1 1 1 1 2 1 1 ] 7 24: [ 1 1 1 1 1 2 1 ] 7 25: [ 1 1 1 1 1 1 2 ] 7 26: [ 1 1 1 1 1 1 1 1 ] 8 There are none with base length <= 3, two with base length 4, etc., giving row 8 [0,0,0,0,2,7,10,6,1]. (End)
References
- B. C. Berndt, Ramanujan's Notebooks, Part III, Springer Verlag, New York, 1991.
- R. K. Guy, personal communication to N. J. A. Sloane.
- See A005169 for further references.
Links
- Alois P. Heinz, Rows n = 0..200, flattened
- P. Brändén, A. Claesson, E. Steingrímsson, Catalan continued fractions and increasing subsequences in permutations, Discrete Mathematics, Vol. 258, Issues 1-3, Dec. 2002, 275-287.
- H. W. Gould, R. K. Guy, and N. J. A. Sloane, Correspondence, 1987.
- A. M. Odlyzko and H. S. Wilf, The editor's corner: n coins in a fountain, Amer. Math. Monthly, 95 (1988), 840-843.
Crossrefs
Row sums give A005169 (set x=1 in the g.f.).
Column sums give A000108 (set y=1 in the g.f.). - Joerg Arndt, Mar 25 2014
T(2n+1,n+1) gives A058300(n). - Alois P. Heinz, Jun 24 2015
Cf. A161492.
Programs
-
Maple
b:= proc(n, i) option remember; expand(`if`(n=0, 1, add(b(n-j, j)*x, j=1..min(i+1, n)))) end: T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)): seq(T(n), n=0..20); # Alois P. Heinz, Oct 05 2017 -
Mathematica
b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j]*x, {j, 1, Min[i+1, n]}]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Jul 11 2018, after Alois P. Heinz *) -
PARI
N=22; x='x+O('x^N); G(k)=if (k>N, 1, 1/(1-y*x^k*G(k+1))); V=Vec( G(1) ); my( N=#V ); rvec(V) = { V=Vec(V); my(n=#V); vector(n, j, V[n+1-j] ); } for(n=1, N, print( rvec( V[n]) ) ); \\ print triangle \\ Joerg Arndt, Mar 25 2014
Formula
G.f.: 1/(1 - y*x / (1 - y*x^2 / (1 - y*x^3 / ( ... )))), from the Odlyzko/Wilf reference. - Joerg Arndt, Mar 25 2014
G.f.: ( Sum_{n >= 0} (-y)^n*x^(n*(n+1))/Product_{k = 1..n} (1 - x^k) )/ ( Sum_{n >= 0} (-y)^n*x^(n^2)/Product_{k = 1..n} (1 - x^k) ) = 1 + y*x + y^2*x^2 + (y^2 + y^3)*x^3 + (2*y^3 + y^4)*x^4 + ... (see Berndt, Cor. to Entry 15, ch. 16). - Peter Bala, Jun 20 2019
Extensions
More terms from Joerg Arndt, Mar 08 2011
Comments