A054392 Number of permutations with certain forbidden subsequences.

1, 1, 2, 5, 14, 42, 131, 418, 1352, 4410, 14463, 47605, 157084, 519255, 1718653, 5693903, 18877509, 62620857, 207816230, 689899944, 2290913666, 7608939443, 25276349558, 83977959853, 279039638062, 927272169336, 3081641953082

Offset: 0

Author

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

Keywords

• nonn

Comments

Apparently the Motzkin transform of A005251, after A005251(0) is set to 1. - R. J. Mathar, Dec 11 2008

Examples

			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 + ...
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
• Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

Crossrefs

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

Cf. A005773, A054391-A054394.

Programs

Magma

R:=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

Maple

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

Mathematica

a[0] = 1; a[n_]:= Module[{M}, M = Table[If[jJean-François Alcover, Aug 16 2018, after A054391 *)
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 *)

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 */

Sage

def A054392_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    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()
A054392_list(30) # G. C. Greubel, Feb 14 2020

Formula

(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

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