login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A239927
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength k such that the area between the x-axis and the path is n (n>=0; 0<=k<=n).
11
1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 3, 0, 1, 0, 0, 0, 1, 0, 4, 0, 1, 0, 0, 0, 0, 3, 0, 5, 0, 1, 0, 0, 0, 1, 0, 6, 0, 6, 0, 1, 0, 0, 0, 0, 3, 0, 10, 0, 7, 0, 1, 0, 0, 0, 0, 0, 7, 0, 15, 0, 8, 0, 1, 0, 0, 0, 0, 2, 0, 14, 0, 21, 0, 9, 0, 1, 0, 0, 0, 0, 0, 7, 0, 25, 0, 28, 0, 10, 0, 1, 0, 0, 0, 0, 1, 0, 17, 0, 41, 0, 36, 0, 11, 0, 1
OFFSET
0,19
COMMENTS
Triangle A129182 transposed.
Column sums give the Catalan numbers (A000108).
Row sums give A143951.
Sums along falling diagonals give A005169.
T(4n,2n) = A240008(n). - Alois P. Heinz, Mar 30 2014
LINKS
Joerg Arndt and Alois P. Heinz, Rows n = 0..140, flattened
FORMULA
G.f.: F(x,y) satisfies F(x,y) = 1 / (1 - x*y * F(x, x^2*y) ).
G.f.: 1/(1 - y*x/(1 - y*x^3/(1 - y*x^5/(1 - y*x^7/(1 - y*x^9/( ... )))))).
EXAMPLE
Triangle begins:
00: 1;
01: 0, 1;
02: 0, 0, 1;
03: 0, 0, 0, 1;
04: 0, 0, 1, 0, 1;
05: 0, 0, 0, 2, 0, 1;
06: 0, 0, 0, 0, 3, 0, 1;
07: 0, 0, 0, 1, 0, 4, 0, 1;
08: 0, 0, 0, 0, 3, 0, 5, 0, 1;
09: 0, 0, 0, 1, 0, 6, 0, 6, 0, 1;
10: 0, 0, 0, 0, 3, 0, 10, 0, 7, 0, 1;
11: 0, 0, 0, 0, 0, 7, 0, 15, 0, 8, 0, 1;
12: 0, 0, 0, 0, 2, 0, 14, 0, 21, 0, 9, 0, 1;
13: 0, 0, 0, 0, 0, 7, 0, 25, 0, 28, 0, 10, 0, 1;
14: 0, 0, 0, 0, 1, 0, 17, 0, 41, 0, 36, 0, 11, 0, 1;
15: 0, 0, 0, 0, 0, 5, 0, 35, 0, 63, 0, 45, 0, 12, 0, 1;
16: 0, 0, 0, 0, 1, 0, 16, 0, 65, 0, 92, 0, 55, 0, 13, 0, 1;
17: 0, 0, 0, 0, 0, 5, 0, 40, 0, 112, 0, 129, 0, 66, 0, 14, 0, 1;
18: 0, 0, 0, 0, 0, 0, 16, 0, 86, 0, 182, 0, 175, 0, 78, 0, 15, 0, 1;
19: 0, 0, 0, 0, 0, 3, 0, 43, 0, 167, 0, 282, 0, 231, 0, 91, 0, 16, 0, 1;
20: 0, 0, 0, 0, 0, 0, 14, 0, 102, 0, 301, 0, 420, 0, 298, 0, 105, 0, 17, 0, 1;
...
Column k=4 corresponds to the following 14 paths (dots denote zeros):
#: path area steps (Dyck word)
01: [ . 1 . 1 . 1 . 1 . ] 4 + - + - + - + -
02: [ . 1 . 1 . 1 2 1 . ] 6 + - + - + + - -
03: [ . 1 . 1 2 1 . 1 . ] 6 + - + + - - + -
04: [ . 1 . 1 2 1 2 1 . ] 8 + - + + - + - -
05: [ . 1 . 1 2 3 2 1 . ] 10 + - + + + - - -
06: [ . 1 2 1 . 1 . 1 . ] 6 + + - - + - + -
07: [ . 1 2 1 . 1 2 1 . ] 8 + + - - + + - -
08: [ . 1 2 1 2 1 . 1 . ] 8 + + - + - - + -
09: [ . 1 2 1 2 1 2 1 . ] 10 + + - + - + - -
10: [ . 1 2 1 2 3 2 1 . ] 12 + + - + + - - -
11: [ . 1 2 3 2 1 . 1 . ] 10 + + + - - - + -
12: [ . 1 2 3 2 1 2 1 . ] 12 + + + - - + - -
13: [ . 1 2 3 2 3 2 1 . ] 14 + + + - + - - -
14: [ . 1 2 3 4 3 2 1 . ] 16 + + + + - - - -
There are no paths with weight < 4, one with weight 4, none with weight 5, 3 with weight 6, etc., therefore column k=4 is
[0, 0, 0, 0, 1, 0, 3, 0, 3, 0, 3, 0, 2, 0, 1, 0, 1, 0, 0, 0, ...].
Row n=8 is [0, 0, 0, 0, 3, 0, 5, 0, 1], the corresponding paths of weight=8 are:
Semilength 4:
[ . 1 . 1 2 1 2 1 . ]
[ . 1 2 1 . 1 2 1 . ]
[ . 1 2 1 2 1 . 1 . ]
Semilength 6:
[ . 1 . 1 . 1 . 1 . 1 2 1 . ]
[ . 1 . 1 . 1 . 1 2 1 . 1 . ]
[ . 1 . 1 . 1 2 1 . 1 . 1 . ]
[ . 1 . 1 2 1 . 1 . 1 . 1 . ]
[ . 1 2 1 . 1 . 1 . 1 . 1 . ]
Semilength 8:
[ . 1 . 1 . 1 . 1 . 1 . 1 . 1 . 1 . ]
MAPLE
b:= proc(x, y, k) option remember;
`if`(y<0 or y>x or k<0, 0, `if`(x=0, `if`(k=0, 1, 0),
b(x-1, y-1, k-y+1/2)+ b(x-1, y+1, k-y-1/2)))
end:
T:= (n, k)-> b(2*k, 0, n):
seq(seq(T(n, k), k=0..n), n=0..20); # Alois P. Heinz, Mar 29 2014
MATHEMATICA
b[x_, y_, k_] := b[x, y, k] = If[y<0 || y>x || k<0, 0, If[x == 0, If[k == 0, 1, 0], b[x-1, y-1, k-y+1/2] + b[x-1, y+1, k-y-1/2]]]; T[n_, k_] := b[2*k, 0, n]; Table[ Table[T[n, k], {k, 0, n}], {n, 0, 20}] // Flatten (* Jean-François Alcover, Feb 18 2015, after Alois P. Heinz *)
PROG
(PARI)
rvec(V) = { V=Vec(V); my(n=#V); vector(n, j, V[n+1-j] ); }
print_triangle(V)= { my( N=#V ); for(n=1, N, print( rvec( V[n]) ) ); }
N=20; x='x+O('x^N);
F(x, y, d=0)=if (d>N, 1, 1 / (1-x*y * F(x, x^2*y, d+1) ) );
v= Vec( F(x, y) );
print_triangle(v)
CROSSREFS
Sequences obtained by particular choices for x and y in the g.f. F(x,y) are: A000108 (F(1, x)), A143951 (F(x, 1)), A005169 (F(sqrt(x), sqrt(x))), A227310 (1+x*F(x, x^2), also 2-1/F(x, 1)), A239928 (F(x^2, x)), A052709 (x*F(1,x+x^2)), A125305 (F(1, x+x^3)), A002212 (F(1, x/(1-x))).
Cf. A129181.
Sequence in context: A288318 A354099 A219483 * A069846 A374092 A239657
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt, Mar 29 2014
STATUS
approved