A166291 Triangle read by rows: T(n,k) is the number of Dyck paths with no UUU's and no DDD's, of semilength n and having k peaks at odd level (0<=k<=n; U=(1,1), D=(1,-1)).

1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 2, 3, 0, 1, 3, 6, 3, 4, 0, 1, 5, 10, 12, 4, 5, 0, 1, 8, 20, 22, 20, 5, 6, 0, 1, 13, 36, 52, 40, 30, 6, 7, 0, 1, 21, 66, 104, 109, 65, 42, 7, 8, 0, 1, 34, 118, 214, 240, 200, 98, 56, 8, 9, 0, 1, 55, 210, 421, 549, 481, 335, 140, 72, 9, 10, 0, 1, 89, 370

Offset: 0

Author

Emeric Deutsch, Oct 12 2009

Keywords

• nonn
• tabl

Comments

Sum of entries in row n = A004148(n+1) (the secondary structure numbers).

T(n,0)=A000045(n-1) (the Fibonacci numbers).

Sum(k*T(n,k), k=0..n)=A166292(n).

Examples

			T(4,2)=3 because we have (UD)(UD)UUDD, (UD)UUDD(UD), and UUDD(UD)(UD) (the odd level peaks are shown between parentheses).
Triangle starts:
1;
0,1;
1,0,1;
1,2,0,1;
2,2,3,0,1;
3,6,3,4,0,1.
		

Crossrefs

Cf. A004148, A000045, A166292, A166293, A166294

Programs

Maple

p1 := -G+1+t*z*G+s*z^2*G+s^2*z^3*H*G: p2 := subs({t = s, s = t, G = H, H = G}, p1): r := resultant(p1, p2, H): G := RootOf(subs(s = 1, r), G): 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, j), j = 0 .. n) end do; yields sequence in triangular form

Formula

The trivariate g.f. G=G(t,s,z), where z marks semilength, t marks odd-level peaks and s marks even-level peaks, satisfies G = 1 + tzG + sz^2*G + s^2*z^3*HG, where H=G(s,t,z) (interchanging t and s and eliminating H, one obtains G(t,s,z); see the Maple program).