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,3

Comments

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

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.

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

Example

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

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[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 *)
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 *)

Prog

(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 */
(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
(Sage)
def A054392_list(prec):
    P.<x> = 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

Crossrefs

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

Cf. A005773, A054391-A054394.

Sequence in context: A290134 A080937 A196417 * A261588 A006930 A036767

Adjacent sequences: A054389 A054390 A054391 * A054393 A054394 A054395

Keyword

nonn

Author

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

Status

approved