A338726 - OEIS

%I #23 Nov 24 2022 11:51:15

%S 1,1,3,9,25,68,189,549,1677,5364,17809,60822,212095,751078,2690809,

%T 9727597,35423189,129775844,477900825,1767787458,6565168975,

%U 24468364150,91486757921,343068002234,1289920924515,4861979955858,18367420180989,69533685133704,263748220185787,1002242753522250

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

%H Matteo Cervetti and Luca Ferrari, <a href="https://arxiv.org/abs/2009.01024">Pattern avoidance in the matching pattern poset</a>, arXiv:2009.01024 [math.CO], 2020.

%H Matteo Cervetti and Luca Ferrari, <a href="https://doi.org/10.1007/s00026-022-00596-1">Enumeration of Some Classes of Pattern Avoiding Matchings, with a Glimpse into the Matching Pattern Poset</a>, Annals of Combinatorics (2022).

%F G.f.: (1-sqrt(1-4*x))/(2*x) + 1/(1-2*x) - 1/(x-1)^2. - _Alois P. Heinz_, Dec 01 2020

%F 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

%F a(n) = A000108(n) + A000295(n). - _Omar E. Pol_, Dec 11 2020

%p a:= proc(n) option remember; `if`(n<4, ceil(3^(n-1)),

%p       ((2*(1651*n^2-6079*n+1369))*a(n-1)-(9639*n^2-44846*n+43507)*

%p        a(n-2)+(2*(5789*n^2-31763*n+43223))*a(n-3)-(4*(607*n-1524))*

%p        (2*n-7)*a(n-4))/((n+1)*(385*n-1369)))

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Dec 05 2020

%t Table[CatalanNumber[n]+2^n-n-1,{n,0,30}] (* _Harvey P. Dale_, Nov 24 2022 *)

%Y Cf. A000079, A000108, A000295.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Nov 30 2020