|
%I #7 Jul 20 2017 01:54:55
%S 1,1,1,1,1,1,2,1,1,3,2,1,1,1,4,4,2,3,2,1,1,5,7,5,5,5,5,2,1,1,1,6,11,
%T 10,10,10,10,8,6,4,3,2,1,1,7,16,18,18,21,21,17,16,14,11,9,7,5,2,1,1,1,
%U 8,22,30,32,38,43,40,34,32,32,26,23,20,14,10,8,4,3,2,1,1,9,29,47,55,67,79,83
%N Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n for which the area below the path minus the number of U-steps is k (n>=0, k>=0).
%C The considered statistic (area below the path minus number of U-steps) in RNA secondary structure terminology is called density (see the Willenbring reference, p. 1611).
%C Number of entries in row n is 1 + floor((n-1)^2/4).
%C Sum of entries in row n = A004148(n) (the secondary structure numbers).
%C Sum_{k>=0} k*T(n,k) = A171851(n).
%H R. Willenbring, <a href="https://doi.org/10.1016/j.dam.2008.10.002">RNA structure, permutations and statistics</a>, Discrete Appl. Math., 157, 2009, 1607-1614.
%F The trivariate g.f. G=G(t,u,z), where z marks length, t marks the area below the path, and x marks number of U-steps, satisfies G(t,x,z) = 1 + zG(t,x,z) + txz^2*(G(t,x,tz) - 1)G(t,x,z) (yielding a continued fraction expression for G(t,1/t,z)).
%e T(4,2)=1 because we have UHHD, where U=(1,1), H=(1,0), D=(1,-1).
%e Triangle starts:
%e 1;
%e 1;
%e 1;
%e 1, 1;
%e 1, 2, 1;
%e 1, 3, 2, 1, 1;
%e 1, 4, 4, 2, 3, 2, 1;
%e 1, 5, 7, 5, 5, 5, 5, 2, 1, 1;
%e 1, 6, 11, 10, 10, 10, 10, 8, 6, 4, 3, 2, 1;
%p g[0] := 1/(1-z+z^2-z^2*g[1]): for n to 12 do g[n] := subs({z = t*z, g[n] = g[n+1]}, g[n-1]) end do: G := subs(g[16] = 0, g[0]): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 11 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 11 do seq(coeff(P[n], t, k), k = 0 .. floor((1/4)*(n-1)^2)) end do; # yields sequence in triangular form
%Y Cf. A004148, A171851.
%K nonn,tabf
%O 0,7
%A _Emeric Deutsch_, Feb 08 2010
|
