login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.

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ı́mssonCatalan 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 * A017847 A127841 A091006

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 03:25 EDT 2019. Contains 328135 sequences. (Running on oeis4.)