A215067 Number of Motzkin n-paths avoiding odd-numbered steps that are up steps.

1, 1, 1, 2, 3, 6, 10, 21, 37, 80, 146, 322, 602, 1347, 2563, 5798, 11181, 25512, 49720, 114236, 224540, 518848, 1027038, 2384538, 4748042, 11068567, 22150519, 51817118, 104146733, 244370806, 493012682, 1159883685, 2347796965, 5536508864, 11239697816, 26560581688, 54061835288

Offset: 0

Author

David Scambler, Aug 02 2012

Keywords

• nonn

Comments

This sequence interleaves the counts of the closely related sequences A109081 and A106228.

a(n) is the number of (peakless) Motzkin paths of length n where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on n vertices where only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021

Examples

			a(5) = 6: fUfFd, fUfDf, fUdUd, fUdFf, fFfUd, fFfFf showing odd-numbered steps in lower case.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.

Crossrefs

Cf. A109081, A106228, A114465, A084075.

Programs

Maple

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, b(x-1, y) +b(x-1, y+1) +
      `if`(irem(x, 2)=1, 0, b(x-1, y-1)) ))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 04 2013

Mathematica

f[n_,x_,y_]:=f[n,x,y] = If[x>n||y<0,0,If[x==n&&y==0,1, If[EvenQ[x],0,f[n,x+1,y+1]] +f[n,x+1,y-1] + f[n,x+1,y]]]; Table[f[n,0,0],{n,0,35}]

PARI

{a(n)=polcoeff((1/x)*serreverse(x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)+x^2*O(x^n)))/(2*(1+x+x^2+x^2*O(x^n)))),n)} \\ Paul D. Hanna, Aug 02 2012

Sage

from mpmath import mp
mp.dps = 25; mp.pretty = True
def A215067(n) :
    m = n%2; r = n//2 if n>0 else 1
    return r^(1-m)*mp.hyper([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)
[int(A215067(i)) for i in (0..32)]  # Peter Luschny, Aug 03 2012

Formula

a(2*n) = Sum_{k=0..n} binomial(n+k-1,n-k) * binomial(n,k)/(n-k+1);

a(2*n+1) = Sum_{k=0..n} binomial(n+k+1,n-k) * binomial(n,k)/(n-k+1).

G.f.: (1/x)*Series_Reversion( x*(3+2*x+x^2 - sqrt((1+x^2)*(1+4*x+x^2)))/(2*(1+x+x^2)) ). - Paul D. Hanna, Aug 02 2012

G.f. satisfies: A(x) = G(x*A(x)) where G(x) = A(x/G(x)) = (3+2*x+x^2 + sqrt((1+x^2)*(1+4*x+x^2)))/4. - Paul D. Hanna, Aug 02 2012

G.f. satisfies: Series_Reversion(x*A(x)) = x - x^2*F(-x) where F(x) = g.f. of A114465. - Paul D. Hanna, Aug 02 2012

a(n) = 3_F_2([-r,1-r-2*m,1+r+m],[(3-m)/2,(4-m)/2],1/4)*r^(1-m) for n>0 where m = n mod 2 and r = floor(n/2). - Peter Luschny, Aug 03 2012