OFFSET
0,14
COMMENTS
The number a(n,k) of (n,k) fountains equals the number of 231-avoiding permutations in the symmetric group S_{k} with exactly n - k inversions (Brändén et al., Proposition 4).
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.
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
EXAMPLE
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)
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 *)
PROG
(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
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.
KEYWORD
AUTHOR
EXTENSIONS
More terms from Joerg Arndt, Mar 08 2011
STATUS
approved