A214938 Number of Motzkin n-paths avoiding even-numbered steps that are flat steps.

1, 1, 1, 2, 3, 7, 11, 28, 46, 122, 207, 562, 977, 2693, 4769, 13288, 23872, 67064, 121862, 344588, 631958, 1796518, 3319923, 9479780, 17630692, 50532640, 94493713, 271710662, 510468519, 1471935235, 2776629563, 8026070768, 15194389388, 44015873308, 83591476528

Offset: 0

Author

David Scambler, Jul 30 2012

Keywords

• nonn

Examples

			a(5) = 7: UuFdD, UuDdF, UdUdF UdFuD, FuUdD, FuFdF, FuDuD, showing even-numbered steps in lower case.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
• Veronika Irvine, Stephen Melczer, Frank Ruskey, Vertically constrained Motzkin-like paths inspired by bobbin lace, arXiv:1804.08725 [math.CO], 2018.

Crossrefs

Cf. A001006, A000108.

Programs

Maple

a:= proc(n) option remember; `if`(n<7, [1, 1, 1, 2, 3, 7, 11][n+1],
      (4*(n+1)*(5066415*n^3-39734381*n^2+51596519*n-4935351)*a(n-1)
      +(83427510*n^4-315565444*n^3-532176102*n^2+1458851596*n
       [phone])*a(n-2) -(157058865*n^4-1556016371*n^3
       [phone]*n^2+220948511*n-3544991136)*a(n-3) -(107648400*n^4
       -766240720*n^3+696027720*n^2+4498794592*n -8240373864)*a(n-4)
      +8*(n-4)*(25332075*n^3-234136810*n^2+385914455*n+722870772)*a(n-5)
      -24*(n-5)*(1345605*n^3-3657347*n^2-11033479*n+18898695)*a(n-6)
      +12*(n-5)*(n-6)*(5066415*n^2-14402306*n-21087469)*a(n-7)) /
      (8*(n+2)*(n+1)*(1345605*n^2-5002952*n-4935351)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Nov 02 2013

Mathematica

Table[Sum[Binomial[Floor[(n+1)/2],Mod[n,2]+2*(Floor[n/4]-k)] * CatalanNumber[k+Floor[(n+2)/4]],{k,0,Floor[n/4]}],{n,0,34}]

PARI

/* G.f. A(x) = B(x^2) + x*C(x^2): */ {a(n)=local(A,B,C);
B=(1/x)*serreverse(x*(1-x)*(1-2*x)^2/(1-4*x+5*x^2-2*x^3+x^4+x*O(x^n)));
C=(1/x)*serreverse(x/(1+2*x+3*x^2+2*x^3+(1-sqrt(1+4*x^2+x*O(x^n)))^3/4));
A=subst(B,x,x^2)+x*subst(C,x,x^2); polcoeff(A,n)} \\ Paul D. Hanna, Aug 03 2012

Formula

a(n) = Sum_{k=0..floor(n/4)} C(floor((n+1)/2), (n mod 2) + 2*(floor(n/4) - k)) * A000108(k + floor((n+2)/4)).

Let g.f. A(x) = B(x^2) + x*C(x^2), then

B(x) = (1/x)*Series_Reversion( x*(1-x)*(1-2*x)^2 / (1-4*x+5*x^2-2*x^3+x^4) ),

C(x) = (1/x)*Series_Reversion( x / (1+2*x+3*x^2+2*x^3 + 2*x^6*Catalan(-x^2)^3) )

where Catalan(x) = (1-sqrt(1-4*x))/(2*x). - Paul D. Hanna, Aug 03 2012

a(n) ~ c * 6^(n/2+1)/(5*sqrt(5*Pi)*n^(3/2)), where c = 2 * sqrt(3) if n is even and c = 3 * sqrt(2) if n is odd. - Vaclav Kotesovec, Nov 07 2013