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

 

Logo


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

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 March 26 23:02 EDT 2019. Contains 321565 sequences. (Running on oeis4.)