

A108916


Triangle of Schroeder paths counted by number of diagonal steps not preceded by an east step.


1



1, 1, 1, 3, 2, 1, 9, 9, 3, 1, 31, 36, 18, 4, 1, 113, 155, 90, 30, 5, 1, 431, 678, 465, 180, 45, 6, 1, 1697, 3017, 2373, 1085, 315, 63, 7, 1, 6847, 13576, 12068, 6328, 2170, 504, 84, 8, 1, 28161, 61623, 61092, 36204, 14238, 3906, 756, 108, 9, 1, 117631, 281610, 308115, 203640, 90510, 28476, 6510, 1080, 135, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

T(n,k) = number of Schroeder (= underdiagonal Delannoy) paths of steps east(E), north(N) and diagonal (D) (i.e., northeast) from (0,0) to (n,n) containing k Ds not preceded by an E. Also, T(n,k) = number of Schroeder paths from (0,0) to (n,n) containing k Ds not preceded by an N. This is because there is a simple bijection on Schroeder paths that interchanges the statistics "# Ds not preceded by an E" and "# Ds not preceded by an N": for each E and its matching N, interchange the diagonal segments (possibly empty) immediately following them (a diagonal segment is a maximal sequence of contiguous Ds).


LINKS

Alois P. Heinz, Rows n = 0..140, flattened


FORMULA

G.f.: G(z,t) = Sum_{n>=k>=0} T(n,k)*z^n*t^k satisfies G = 1 + z*t*G + z(1 + z  z*t)G^2 with solution G(z,t) = (1  t*z  ((1  t*z)^2 + 4*z*(1  z + t*z))^(1/2))/(2*z*(1 + z  t*z)).


EXAMPLE

Table begins:
\ k..0...1...2...3...4...
n\
0 ..1
1 ..1...1
2 ..3...2...1
3 ..9...9...3...1
4 .31..36..18...4...1
5 113.155..90..30...5...1
The paths ENDD, DEND, DDEN each have 2 Ds not preceded by an E and so T(3,2)=3.


CROSSREFS

Column k=0 is A052709 shifted left. Cf. A110446.
Sequence in context: A108073 A057731 A126074 * A119421 A121581 A162976
Adjacent sequences: A108913 A108914 A108915 * A108917 A108918 A108919


KEYWORD

nonn,tabl


AUTHOR

David Callan, Jul 25 2005


STATUS

approved



