A054392 - OEIS

%I #35 Sep 08 2022 08:45:00

%S 1,1,2,5,14,42,131,418,1352,4410,14463,47605,157084,519255,1718653,

%T 5693903,18877509,62620857,207816230,689899944,2290913666,7608939443,

%U 25276349558,83977959853,279039638062,927272169336,3081641953082

%N Number of permutations with certain forbidden subsequences.

%C Apparently the Motzkin transform of A005251, after A005251(0) is set to 1. - _R. J. Mathar_, Dec 11 2008

%H G. C. Greubel, <a href="/A054392/b054392.txt">Table of n, a(n) for n = 0..1000</a>

%H E. Barcucci et al., <a href="http://dx.doi.org/10.1016/S0012-365X(99)00254-X">From Motzkin to Catalan Permutations</a>, Discr. Math., 217 (2000), 33-49.

%H Nickolas Hein, Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.

%F (n-2)*a(n) = (8*n-19)*a(n-1) - (20*n-49)*a(n-2) + (11*n-1)*a(n-3) + (19*n-116) * a(n-4) - 21*(n-5)*a(n-5). - _R. J. Mathar_, Aug 09 2015

%F G.f.: (2 -10*x +13*x^2 -5*x^3 +x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2-14*x^3). - _Michael D. Weiner_, Feb 07 2020

%e G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 131*x^6 + 418*x^7 + 1352*x^8 + ...

%p m:=30; S:=series((2-10*x+13*x^2-5*x^3+x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2 -14*x^3), x, m+1): seq(coeff(S, x, j), j=0..m); # _G. C. Greubel_, Feb 14 2020

%t a[0] = 1; a[n_]:= Module[{M}, M = Table[If[j<i || i==j && i<=4 || j==i+1, 1, 0], {i, 1, n}, {j, 1, n}]; MatrixPower[M, n][[1, 1]]]; Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Aug 16 2018, after A054391 *)

%t a[n_]:= a[n]= If[n<2, 1, If[n==2, 2, If[3<=n<=4, 9*n-22, ((8*n-19)*a[n-1] - (20*n-49)*a[n-2] +(11*n-1)*a[n-3] +(19*n-116)*a[n-4] -21*(n-5)*a[n-5])/(n-2) ]]]; Table[a[n], {n,0,30}] (* _G. C. Greubel_, Feb 14 2020 *)

%o (PARI) {a(n) = if( n<1, n==0, polcoeff( subst( x * (1 - x) / (1 - 2*x + x^2 - x^3), x, serreverse( x / (1 + x + x^2) + x * O(x^n))), n))}; /* _Michael Somos_, Aug 06 2014 */

%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (2 -10*x +13*x^2 -5*x^3 +x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2-14*x^3) )); // _G. C. Greubel_, Feb 14 2020

%o (Sage)

%o def A054392_list(prec):

%o     P.<x> = PowerSeriesRing(ZZ, prec)

%o     return P( (2-10*x+13*x^2-5*x^3+x^2*sqrt(1-2*x-3*x^2))/(2-12*x+22*x^2-14*x^3) ).list()

%o A054392_list(30) # _G. C. Greubel_, Feb 14 2020

%Y Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108).

%Y Cf. A005773, A054391-A054394.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000