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

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.

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

Example

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

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
       +157931232)*a(n-2) -(157058865*n^4-1556016371*n^3
       +3706209891*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}]

Prog

(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

Crossrefs

Cf. A001006, A000108.

Sequence in context: A305750 A107857 A107858 * A143926 A112840 A014981

Adjacent sequences: A214935 A214936 A214937 * A214939 A214940 A214941

Keyword

nonn

Author

David Scambler, Jul 30 2012

Status

approved