A191316 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths of length n having k UDU's, where U = (1,1) and D = (1,-1).

1, 1, 2, 3, 5, 1, 8, 2, 14, 5, 1, 23, 10, 2, 40, 23, 6, 1, 67, 44, 13, 2, 117, 92, 35, 7, 1, 198, 174, 72, 16, 2, 346, 350, 170, 49, 8, 1, 590, 654, 345, 106, 19, 2, 1032, 1280, 768, 277, 65, 9, 1, 1769, 2374, 1530, 592, 146, 22, 2, 3096, 4564, 3263, 1436, 417, 83, 10, 1, 5328, 8414, 6417, 3004, 928, 192, 25, 2

Offset: 0

Author

Emeric Deutsch, Jun 01 2011

Keywords

• nonn
• tabf

Comments

A dispersed Dyck paths of length n is a Motzkin path of length n with no (1,0) steps at positive heights.

Row n>=2 has floor(n/2) entries (n>=2).

Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).

Sum_{k>=0} k*T(n,k) = A107373(n-1).

Addendum Jun 18 2011: (Start)

T(n,k) is also the number of length n left factors of Dyck paths having k DUD's.

T(n,k) is also the number of dispersed Dyck paths of length n having k DUD's. Example: T(7,2)=2 because we have HU(DU[D)UD] and U(DU[D)UD]H, where H = (1,0) (the DUD's are shown between parentheses). (End)

Examples

			T(7,2)=2 because we have H(UD[U)DU]D and (UD[U)DU]DH, where U=(1,1), D=(1,-1), H=(1,0) (the UDU's are shown between parentheses).
T(7,2)=2 because we have U(DU[D)UD]U and UU(DU[D)UD], where U=(1,1) and D=(1,-1) (the DUD's are shown between parentheses).
Triangle starts:
   1;
   1;
   2;
   3;
   5,  1;
   8,  2;
  14,  5,  1;
  23, 10,  2;
  40, 23,  6,  1;
		

Crossrefs

Cf. A001405, A107373, A191317.

Programs

Maple

eq := z*(1-2*z+z^2-z^3-t*z^2+t*z^3)*G^2+(1-2*z)*(1+z^2-t*z^2)*G-1-z^2+t*z^2 = 0: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 20)): for n from 0 to 17 do P[n] := sort(coeff(Gser, z, n)) end do: 1; 1; for n from 2 to 17 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)-1) end do; # yields sequence in triangular form
# alternative, added Jun 18 2011:
eq := z^2*C^2-(1+z^2-t*z^2)*C+1+z^2-t*z^2: C := RootOf(eq, C): G := C/(1-z*C): Gser := simplify(series(G, z = 0, 20)): for n from 0 to 17 do P[n] := sort(coeff(Gser, z, n)) end do: 1 1; for n from 2 to 17 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)-1) end do;

Formula

G.f.: G=G(t,z) is given by z*(1-2*z+z^2-z^3-t*z^2+t*z^3)*G^2 +(1-2*z)*(1+z^2-t*z^2)*G -(1+z^2-t*z^2)=0.

This can also be written as G = C/(1-z*C), where C=C(t,z) is given by z^2*C^2 - (1 + z^2 - t*z^2)*C + 1 + z^2 - t*z^2 = 0. - Emeric Deutsch, Jun 18 2011

T(n,0) = A191317(n).