login
Number of permutations with certain forbidden subsequences.
3

%I #28 Oct 16 2018 03:56:31

%S 1,1,2,5,14,42,132,428,1417,4757,16119,54963,188219,646460,2224944,

%T 7668915,26461005,91371594,315689675,1091166442,3772747245,

%U 13047503222,45131078409,156129312025,540181837728,1869097588540,6467740095295

%N Number of permutations with certain forbidden subsequences.

%H E. Barcucci et al., <a href="http://dx.doi.org/10.1016/S0012-365X(99)00254-X">From Motzkin to Catalan Permutations</a>, Discr. Math., 217 (2000), 33-49.

%H Nickolas Hein, Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.

%H J. W. Layman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.

%F 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

%t 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]]];

%t Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Aug 16 2018, after A054391 *)

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

%Y Cf. A005773, A054391, A054392, A054394.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000