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

Sequence in context: A284938 A186084 A301345 * A127841 A017847 A350753

Adjacent sequences: A047995 A047996 A047997 * A047999 A048000 A048001

Keyword

nonn,tabl,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Joerg Arndt, Mar 08 2011

Status

approved