cp's OEIS Frontend

A047998 Triangle of numbers a(n,k) = number of "fountains" with n coins, k in the bottom row.

%I A047998 #63 Mar 11 2023 08:43:32
%S A047998 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,
%T A047998 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,
%U A047998 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
%N A047998 Triangle of numbers a(n,k) = number of "fountains" with n coins, k in the bottom row.
%C A047998 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).
%D A047998 B. C. Berndt, Ramanujan's Notebooks, Part III, Springer Verlag, New York, 1991.
%D A047998 R. K. Guy, personal communication to _N. J. A. Sloane_.
%D A047998 See A005169 for further references.
%H A047998 Alois P. Heinz, <a href="/A047998/b047998.txt">Rows n = 0..200, flattened</a>
%H A047998 P. Brändén, A. Claesson, E. Steingrímsson, <a href="https://doi.org/10.1016/S0012-365X(02)00353-9">Catalan continued fractions and increasing subsequences in permutations</a>, Discrete Mathematics, Vol. 258, Issues 1-3, Dec. 2002, 275-287.
%H A047998 H. W. Gould, R. K. Guy, and N. J. A. Sloane, <a href="/A005169/a005169_5.pdf">Correspondence</a>, 1987.
%H A047998 A. M. Odlyzko and H. S. Wilf, <a href="http://www.jstor.org/stable/2322898">The editor's corner: n coins in a fountain</a>, Amer. Math. Monthly, 95 (1988), 840-843.
%F A047998 G.f.: 1/(1 - y*x / (1 - y*x^2 / (1 - y*x^3 / ( ... )))), from the Odlyzko/Wilf reference. - _Joerg Arndt_, Mar 25 2014
%F A047998 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
%e A047998 Triangle begins:
%e A047998 00:  1;
%e A047998 01:  0,1;
%e A047998 02:  0,0,1;
%e A047998 03:  0,0,1,1;
%e A047998 04:  0,0,0,2,1;
%e A047998 05:  0,0,0,1,3,1;
%e A047998 06:  0,0,0,1,3,4,1;
%e A047998 07:  0,0,0,0,3,6,5,1;
%e A047998 08:  0,0,0,0,2,7,10,6,1;
%e A047998 09:  0,0,0,0,1,7,14,15,7,1;
%e A047998 10:  0,0,0,0,1,5,17,25,21,8,1;
%e A047998 11:  0,0,0,0,0,5,16,35,41,28,9,1;
%e A047998 12:  0,0,0,0,0,3,16,40,65,63,36,10,1;
%e A047998 13:  0,0,0,0,0,2,14,43,86,112,92,45,11,1;
%e A047998 14:  0,0,0,0,0,1,11,44,102,167,182,129,55,12,1;
%e A047998 15:  0,0,0,0,0,1,9,40,115,219,301,282,175,66,13,1;
%e A047998 16:  0,0,0,0,0,0,7,37,118,268,434,512,420,231,78,14,1;
%e A047998 17:  0,0,0,0,0,0,5,32,118,303,574,806,831,605,298,91,15,1;
%e A047998 ...
%e A047998 From _Joerg Arndt_, Mar 25 2014: (Start)
%e A047998 The compositions (compositions starting with part 1 and up-steps <= 1) corresponding to row n=8 with their base lengths are:
%e A047998 01:    [ 1 2 3 2 ]               4
%e A047998 02:    [ 1 2 2 3 ]               4
%e A047998 03:    [ 1 2 3 1 1 ]             5
%e A047998 04:    [ 1 2 2 2 1 ]             5
%e A047998 05:    [ 1 1 2 3 1 ]             5
%e A047998 06:    [ 1 2 2 1 2 ]             5
%e A047998 07:    [ 1 2 1 2 2 ]             5
%e A047998 08:    [ 1 1 2 2 2 ]             5
%e A047998 09:    [ 1 1 1 2 3 ]             5
%e A047998 10:    [ 1 2 2 1 1 1 ]           6
%e A047998 11:    [ 1 2 1 2 1 1 ]           6
%e A047998 12:    [ 1 1 2 2 1 1 ]           6
%e A047998 13:    [ 1 2 1 1 2 1 ]           6
%e A047998 14:    [ 1 1 2 1 2 1 ]           6
%e A047998 15:    [ 1 1 1 2 2 1 ]           6
%e A047998 16:    [ 1 2 1 1 1 2 ]           6
%e A047998 17:    [ 1 1 2 1 1 2 ]           6
%e A047998 18:    [ 1 1 1 2 1 2 ]           6
%e A047998 19:    [ 1 1 1 1 2 2 ]           6
%e A047998 20:    [ 1 2 1 1 1 1 1 ]         7
%e A047998 21:    [ 1 1 2 1 1 1 1 ]         7
%e A047998 22:    [ 1 1 1 2 1 1 1 ]         7
%e A047998 23:    [ 1 1 1 1 2 1 1 ]         7
%e A047998 24:    [ 1 1 1 1 1 2 1 ]         7
%e A047998 25:    [ 1 1 1 1 1 1 2 ]         7
%e A047998 26:    [ 1 1 1 1 1 1 1 1 ]       8
%e A047998 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].
%e A047998 (End)
%p A047998 b:= proc(n, i) option remember; expand(`if`(n=0, 1,
%p A047998       add(b(n-j, j)*x, j=1..min(i+1, n))))
%p A047998     end:
%p A047998 T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
%p A047998 seq(T(n), n=0..20);  # _Alois P. Heinz_, Oct 05 2017
%t A047998 b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j]*x, {j, 1, Min[i+1, n]}]];
%t A047998 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]];
%t A047998 Table[T[n], {n, 0, 20}] // Flatten (* _Jean-François Alcover_, Jul 11 2018, after _Alois P. Heinz_ *)
%o A047998 (PARI)
%o A047998 N=22; x='x+O('x^N);
%o A047998 G(k)=if (k>N, 1, 1/(1-y*x^k*G(k+1)));
%o A047998 V=Vec( G(1) );
%o A047998 my( N=#V );
%o A047998 rvec(V) = { V=Vec(V); my(n=#V); vector(n, j, V[n+1-j] ); }
%o A047998 for(n=1, N, print( rvec( V[n]) ) ); \\ print triangle
%o A047998 \\ _Joerg Arndt_, Mar 25 2014
%Y A047998 Row sums give A005169 (set x=1 in the g.f.).
%Y A047998 Column sums give A000108 (set y=1 in the g.f.). - _Joerg Arndt_, Mar 25 2014
%Y A047998 T(2n+1,n+1) gives A058300(n). - _Alois P. Heinz_, Jun 24 2015
%Y A047998 Cf. A161492.
%K A047998 nonn,tabl,easy,nice
%O A047998 0,14
%A A047998 _N. J. A. Sloane_
%E A047998 More terms from _Joerg Arndt_, Mar 08 2011