login
Number of peakless Motzkin paths with no U H...HU's where U=(1,1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).
1

%I #11 Jul 30 2022 12:20:06

%S 1,1,1,2,4,8,16,32,65,134,280,592,1264,2722,5906,12900,28344,62608,

%T 138949,309692,692905,1555718,3504016,7915182,17927154,40702926,

%U 92623758,211217180,482593474,1104640484,2532768508,5816447840

%N Number of peakless Motzkin paths with no U H...HU's where U=(1,1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).

%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.

%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1979), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

%F G.f.: G=G(z) satisfies G=1+zG+z^2*G[G-1-zG+z/(1-z)].

%F D-finite with recurrence (n+2)*a(n) +5*(-n-1)*a(n-1) +2*(4*n+1)*a(n-2) -4*n*a(n-3) +2*(-2*n+11)*a(n-5) +2*(4*n-23)*a(n-6) +4*(-n+6)*a(n-7)=0. - _R. J. Mathar_, Jul 24 2022

%e a(4)=4 because we have HHHH, UHDU, HUHD and UHHD; a(6)=16 because among all 17 peakless Motzkin paths of length 6 (see A004148) only (UHU)HDD does not qualify.

%p G:=(1-2*z+2*z^2-2*z^3-sqrt(1-4*z+4*z^2-4*z^5+4*z^6))/2/z^2/(1-z)^2: Gser:=series(G,z=0,35): 1, seq(coeff(Gser,z^n),n=1..32);

%Y Cf. A004148.

%K nonn

%O 0,4

%A _Emeric Deutsch_, Sep 11 2004