|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
