A054393 Number of permutations with certain forbidden subsequences.

1, 1, 2, 5, 14, 42, 132, 428, 1417, 4757, 16119, 54963, 188219, 646460, 2224944, 7668915, 26461005, 91371594, 315689675, 1091166442, 3772747245, 13047503222, 45131078409, 156129312025, 540181837728, 1869097588540, 6467740095295

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.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Formula

Conjecture: (-n+3)*a(n) + (10*n-33)*a(n-1) + 5*(-7*n+24)*a(n-2) + 2*(22*n-63)*a(n-3) + 2*(5*n-78)*a(n-4) + (-55*n+357)*a(n-5) + (22*n-135)*a(n-6) + 3*(-n+6)*a(n-7) = 0. - R. J. Mathar, Aug 09 2015

Mathematica

a[0] = 1; a[n_] := Module[{M}, M = Table[If[j < i || i == j && i <= 5 || 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, A054392, A054394.

Sequence in context: A293499 A024175 A152226 * A261589 A036768 A287970

Adjacent sequences: A054390 A054391 A054392 * A054394 A054395 A054396

Keyword

nonn

Author

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

Status

approved