login
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, 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,3
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)
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).
EXAMPLE
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;
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;
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jun 01 2011
STATUS
approved