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

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

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.

Mathematica

G[z_, t_] = (1-t*z - ((1-t*z)^2 + 4z(-1-z+t*z))^(1/2))/(2z(1+z-t*z));
CoefficientList[#, t]& /@ CoefficientList[G[z, t] + O[z]^11, z] // Flatten (* Jean-François Alcover, Oct 06 2019 *)

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