A054394 Number of permutations with certain forbidden subsequences.

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4847, 16660, 57820, 202086, 709928, 2503266, 8850681, 31355020, 111242127, 395091069, 1404332528, 4994581900, 17771328588, 63253477326, 225194224134, 801884971816, 2855809269782, 10171707099565

Offset

0,3

Links

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

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

Conjecture: g.f.(x)=1+z*(1-2z+z^2-z^3)/(1-3z+3z^2-3z^3+2z^4-z^5) where z=x*A001006(x) and A001006(x) is the g.f. of A001006. [R. J. Mathar, Jul 07 2009]

Mathematica

a[0] = 1; a[n_] := Module[{M}, M = Table[If[j < i || i == j && i <= 6 || 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 *)

Crossrefs

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054391-A054393.

Sequence in context: A287970 A058094 A080938 * A261590 A036769 A287971

Adjacent sequences: A054391 A054392 A054393 * A054395 A054396 A054397

Keyword

nonn

Author

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

Status

approved