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,4

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

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.

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

Example

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

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}]

Prog

(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

Crossrefs

Cf. A109081, A106228, A114465.

Sequence in context: A068991 A187491 A178852 * A008928 A124343 A324407

Adjacent sequences: A215064 A215065 A215066 * A215068 A215069 A215070

Keyword

nonn

Author

David Scambler, Aug 02 2012

Status

approved