|
|
A047998
|
|
Triangle of numbers a(n,k) = number of "fountains" with n coins, k in the bottom row.
|
|
11
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
See A005169 for further references.
|
|
LINKS
|
|
|
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;
...
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)):
|
|
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]];
|
|
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
|
|
CROSSREFS
|
Row sums give A005169 (set x=1 in the g.f.).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|