login
A171848
Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n for which the area below the level steps (i.e., the sum of the altitudes of the level steps) is k (n>=0, k>=0).
1
1, 1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 2, 1, 5, 10, 10, 7, 3, 1, 1, 6, 15, 20, 18, 12, 7, 2, 1, 1, 7, 21, 35, 39, 33, 24, 14, 7, 3, 1, 1, 8, 28, 56, 75, 76, 65, 48, 32, 18, 10, 4, 2, 1, 9, 36, 84, 132, 156, 153, 131, 102, 72, 47, 28, 16, 7, 3, 1, 1, 10, 45, 120, 217, 294, 326
OFFSET
0,7
COMMENTS
The considered statistic (area below level steps) in RNA secondary structure terminology is called concentration (see the Willenbring reference, p. 1610).
Row n has 1 + Sum_{k=0..n+1} floor(k/4) entries.
Sum of entries in row n = A004148(n) (the secondary structure numbers).
Sum_{k>=0} k*T(n,k) = A171849(n).
LINKS
R. Willenbring, RNA structure, permutations and statistics, Discrete Appl. Math., 157, 2009, 1607-1614.
FORMULA
The trivariate g.f. G=G(t,u,z), where z marks length, t marks area below the level steps, and u marks number of level steps, satisfies G(t,u,z) = 1 + uzG(t,u,z) + z^2*(G(t,tu,z) - 1)G(t,u,z).
EXAMPLE
T(4,2)=1 because we have UHHD, where U=(1,1), H=(1,0), D=(1,-1).
Triangle starts:
1;
1;
1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 2;
1, 5, 10, 10, 7, 3, 1;
MAPLE
g[0] := 1/(1-u*z+z^2-z^2*g[1]): for n to 15 do g[n] := subs({u = t*u, g[n] = g[n+1]}, g[n-1]) end do: G := subs({u = 1, g[16] = 0}, g[0]): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 12 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 12 do seq(coeff(P[n], t, k), k = 0 .. sum(floor((1/4)*j), j = 0 .. n+1)) end do; # yields sequence in triangular form
CROSSREFS
Sequence in context: A281587 A026022 A073714 * A144151 A022818 A050447
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Feb 08 2010
STATUS
approved