A352916 a(n) = A025179(n-2) + A102839(n-4), for n >= 4, with a(0) = a(2) = 0 and a(1) = a(3) = 1.

0, 1, 0, 1, 1, 5, 13, 41, 121, 366, 1100, 3319, 10015, 30253, 91433, 276475, 836291, 2530321, 7657317, 23175867, 70150875, 212349687, 642803631, 1945819299, 5890003539, 17828324220, 53961228258, 163314594513, 494238394601, 1495593167851, 4525366817455

Offset

0,6

Comments

a(n) + 2*A025565(n) is the number of Dyck paths of semi-length n+2 with L(D) = 4 where L(D) is the product of binomial coefficients (u_i(D)+d_i(D) choose u_i(D)), where u_i(D) is the number of up-steps between the i-th and (i+1)-st down step and d_i(D) is the number of down-steps between the i-th and (i+1)-st up step.

Links

Table of n, a(n) for n=0..30.

Kassie Archer and Christina Graves, Pattern-restricted permutations composed of 3-cycles, arXiv:2104.12664 [math.CO], 2021.

Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.

Formula

a(n) = m(n-3) + binomial(n-3,2)*m(n-5) + 2*Sum_{i=0..n-5} (i+1)*m(i)*m(n-5-i) for n>=3, where m(n) = A001006(n) is the n-th Motzkin number.

a(n) ~ sqrt(n) * 3^(n - 7/2) / (4*sqrt(Pi)). - Vaclav Kotesovec, Jun 03 2022

D-finite with recurrence (n-1)*(n-69)*a(n) +(n^2+221*n-513)*a(n-1) +(-37*n^2+356*n-312)*a(n-2) +(47*n^2-859*n+2820)*a(n-3) +12*(7*n-30)*(n-6)*a(n-4)=0. - R. J. Mathar, Jul 17 2023

Maple

a:= proc(n) option remember; `if`(n<4, irem(n, 2),
     ((3*(n-4))*(n^4+6*n^3-41*n^2+18*n+76)*a(n-2)+
      (2*n^5+3*n^4-136*n^3+525*n^2-658*n+132)*a(n-1))/
      ((n^4+2*n^3-53*n^2+114*n+12)*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 19 2022

Mathematica

m[n_] := m[n] = If[n == 0, 1, m[n-1] + Sum[m[k]*m[n-2-k], {k, 0, n-2}]];
a[n_] := Switch[n, 0|2, 0, 1|3|4, 1, _, m[n-3] + Binomial[n-3, 2]*m[n-5] + 2*Sum[(i+1)*m[i]*m[n-5-i], {i, 0, n-5}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 26 2022 *)

Prog

(PARI) m(n) = polcoeff( ( 1 - x - sqrt((1 - x)^2 - 4 * x^2 + x^3 * O(x^n))) / (2 * x^2), n); \\ A001006
a(n) = if (n<=3, n%2, m(n-3) + binomial(n-3, 2)*m(n-5) + 2*sum(i=0, n-5, (i+1)*m(i)*m(n-5-i))); \\ Michel Marcus, May 19 2022

Crossrefs

Cf. A001006, A025179, A025565, A102839.

Sequence in context: A080925 A164907 A046717 * A085601 A147718 A111009

Adjacent sequences: A352913 A352914 A352915 * A352917 A352918 A352919

Keyword

nonn

Author

Kassie Archer, Apr 26 2022

Status

approved