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

Author

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

Keywords

• nonn

Links

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

Crossrefs

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

Cf. A005773, A054391, A054392, A054394.

Programs

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

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