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

Author

David Callan, Jul 25 2005

Keywords

• nonn
• tabl

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).

Examples

			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.
		

Links

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

Crossrefs

Column k=0 is A052709 shifted left. Cf. A110446.

Programs

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 *)

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)).