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

%I #15 Oct 06 2019 05:22:14

%S 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,

%T 45,6,1,1697,3017,2373,1085,315,63,7,1,6847,13576,12068,6328,2170,504,

%U 84,8,1,28161,61623,61092,36204,14238,3906,756,108,9,1,117631,281610,308115,203640,90510,28476,6510,1080,135,10,1

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

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

%H Alois P. Heinz, <a href="/A108916/b108916.txt">Rows n = 0..140, flattened</a>

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

%e Table begins:

%e \ k..0...1...2...3...4...

%e n\

%e 0 |..1

%e 1 |..1...1

%e 2 |..3...2...1

%e 3 |..9...9...3...1

%e 4 |.31..36..18...4...1

%e 5 |113.155..90..30...5...1

%e The paths ENDD, DEND, DDEN each have 2 Ds not preceded by an E and so T(3,2)=3.

%t G[z_, t_] = (1-t*z - ((1-t*z)^2 + 4z(-1-z+t*z))^(1/2))/(2z(1+z-t*z));

%t CoefficientList[#, t]& /@ CoefficientList[G[z, t] + O[z]^11, z] // Flatten (* _Jean-François Alcover_, Oct 06 2019 *)

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

%K nonn,tabl

%O 0,4

%A _David Callan_, Jul 25 2005