A338726 a(n) = Catalan(n) + 2^n - n - 1.

1, 1, 3, 9, 25, 68, 189, 549, 1677, 5364, 17809, 60822, 212095, 751078, 2690809, 9727597, 35423189, 129775844, 477900825, 1767787458, 6565168975, 24468364150, 91486757921, 343068002234, 1289920924515, 4861979955858, 18367420180989, 69533685133704, 263748220185787, 1002242753522250

Offset

0,3

Links

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

Matteo Cervetti and Luca Ferrari, Pattern avoidance in the matching pattern poset, arXiv:2009.01024 [math.CO], 2020.

Matteo Cervetti and Luca Ferrari, Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse into the Matching Pattern Poset, Annals of Combinatorics (2022).

Formula

G.f.: (1-sqrt(1-4*x))/(2*x) + 1/(1-2*x) - 1/(x-1)^2. - Alois P. Heinz, Dec 01 2020

D-finite with recurrence -(n+1)*(385*n-1369)*a(n) +2*(1651*n^2 -6079*n +1369)*a(n-1) +(-9639*n^2 +44846*n -43507)*a(n-2) +2*(5789*n^2 -31763*n +43223)*a(n-3) -4*(607*n -1524)*(2*n-7)*a(n-4)=0. - R. J. Mathar, Dec 11 2020

a(n) = A000108(n) + A000295(n). - Omar E. Pol, Dec 11 2020

Maple

a:= proc(n) option remember; `if`(n<4, ceil(3^(n-1)),
      ((2*(1651*n^2-6079*n+1369))*a(n-1)-(9639*n^2-44846*n+43507)*
       a(n-2)+(2*(5789*n^2-31763*n+43223))*a(n-3)-(4*(607*n-1524))*
       (2*n-7)*a(n-4))/((n+1)*(385*n-1369)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 05 2020

Mathematica

Table[CatalanNumber[n]+2^n-n-1, {n, 0, 30}] (* Harvey P. Dale, Nov 24 2022 *)

Crossrefs

Cf. A000079, A000108, A000295.

Sequence in context: A295571 A291019 A236570 * A323362 A201533 A000242

Adjacent sequences: A338723 A338724 A338725 * A338727 A338728 A338729

Keyword

nonn

Author

N. J. A. Sloane, Nov 30 2020

Status

approved