A193364 Number of permutations that have a fixed point and contain 123.

0, 0, 0, 1, 1, 3, 11, 59, 369, 2665, 21823, 199983, 2028701, 22577141, 273551115, 3585133147, 50540288857, 762641865009, 12265883397719, 209475278413895, 3785852926650453, 72191462591370733, 1448516763956727331, 30507960955933725171, 672958104387944656145

Offset: 0

Author

Jon Perry, Dec 20 2012

Keywords

• nonn

Comments

A000142(n-2) gives number of permutations with a 123 present.

It appears that a(n) = A180191(n-2) - A018934(n-3) for n>3.

Examples

			For n=5 we have 12345, 12354 and 41235, so a(5)=3.
For n=6 we have 123456, 123465, 123546, 123465, 123645, 123654, 412356, 451236, 512346, 541236 and 612354, so a(6)=11.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A000142, A002467, A018934.

Programs

Maple

a:= proc(n) option remember;
      `if`(n<7, [0$3, 1$2, 3, 11][n+1],
       ((4*n^3-42*n^2+92*n+39) *a(n-1)
        +(32*n^3-2*n^4-163*n^2+223*n+204) *a(n-2)
        -(n-4)*(n-7)*(2*n^2-10*n-15) *a(n-3)) / (2*n^2-14*n-3))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 07 2013

Mathematica

a[n_] := a[n] = If[n<7, {0, 0, 0, 1, 1, 3, 11}[[n+1]], ((4n^3 - 42n^2 + 92n + 39) a[n-1] + (32n^3 - 2n^4 - 163n^2 + 223n + 204) a[n-2] - (n-4)(n-7) (2n^2 - 10n - 15) a[n-3])/(2n^2 - 14n - 3)];
a /@ Range[0, 30] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)