|
%I #23 Jul 17 2017 02:18:24
%S 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,
%T 198,174,72,16,2,346,350,170,49,8,1,590,654,345,106,19,2,1032,1280,
%U 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
%N 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).
%C A dispersed Dyck paths of length n is a Motzkin path of length n with no (1,0) steps at positive heights.
%C Row n>=2 has floor(n/2) entries (n>=2).
%C Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).
%C Sum_{k>=0} k*T(n,k) = A107373(n-1).
%C Addendum Jun 18 2011: (Start)
%C T(n,k) is also the number of length n left factors of Dyck paths having k DUD's.
%C 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)
%F 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.
%F 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
%F T(n,0) = A191317(n).
%e 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).
%e 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).
%e Triangle starts:
%e 1;
%e 1;
%e 2;
%e 3;
%e 5, 1;
%e 8, 2;
%e 14, 5, 1;
%e 23, 10, 2;
%e 40, 23, 6, 1;
%p 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
%p # alternative, added Jun 18 2011:
%p 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;
%Y Cf. A001405, A107373, A191317.
%K nonn,tabf
%O 0,3
%A _Emeric Deutsch_, Jun 01 2011
|
