cp's OEIS Frontend

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

%I A108916 #15 Oct 06 2019 05:22:14
%S A108916 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 A108916 45,6,1,1697,3017,2373,1085,315,63,7,1,6847,13576,12068,6328,2170,504,
%U A108916 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 A108916 Triangle of Schroeder paths counted by number of diagonal steps not preceded by an east step.
%C A108916 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 A108916 Alois P. Heinz, <a href="/A108916/b108916.txt">Rows n = 0..140, flattened</a>
%F A108916 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 A108916 Table begins:
%e A108916 \ k..0...1...2...3...4...
%e A108916 n\
%e A108916 0 |..1
%e A108916 1 |..1...1
%e A108916 2 |..3...2...1
%e A108916 3 |..9...9...3...1
%e A108916 4 |.31..36..18...4...1
%e A108916 5 |113.155..90..30...5...1
%e A108916 The paths ENDD, DEND, DDEN each have 2 Ds not preceded by an E and so T(3,2)=3.
%t A108916 G[z_, t_] = (1-t*z - ((1-t*z)^2 + 4z(-1-z+t*z))^(1/2))/(2z(1+z-t*z));
%t A108916 CoefficientList[#, t]& /@ CoefficientList[G[z, t] + O[z]^11, z] // Flatten (* _Jean-François Alcover_, Oct 06 2019 *)
%Y A108916 Column k=0 is A052709 shifted left. Cf. A110446.
%K A108916 nonn,tabl
%O A108916 0,4
%A A108916 _David Callan_, Jul 25 2005