A372102 Number of permutations of [n] whose non-fixed points are not neighbors.

1, 1, 1, 2, 4, 9, 19, 45, 107, 278, 728, 2033, 5749, 17105, 51669, 162674, 520524, 1724329, 5807143, 20146861, 71048431, 257139686, 945626800, 3558489633, 13599579817, 53060155137, 210124405097, 847904374466, 3470756061140, 14453943647561, 61023690771451

Offset: 0

Author

Alois P. Heinz, Apr 18 2024

Keywords

• nonn

Examples

			a(3) = 2: 123, 321.
a(4) = 4: 1234, 1432, 3214, 4231.
a(5) = 9: 12345, 12543, 14325, 15342, 32145, 32541, 42315, 52143, 52341.
a(6) = 19: 123456, 123654, 125436, 126453, 143256, 143652, 153426, 163254, 163452, 321456, 325416, 326451, 423156, 423651, 521436, 523416, 621453, 623154, 623451.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..892
• Wikipedia, Permutation.

Crossrefs

Cf. A000142, A000166, A001629, A011973, A098825, A131735, A162969, A165961, A371995.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, [2$3, 4][n+1],
      3*a(n-1)+(n-2)*a(n-2)+(n-1)*(a(n-4)-a(n-3)))/2
    end:
seq(a(n), n=0..30);

Mathematica

a[n_] := Sum[Binomial[n + 1 - k, k] * Subfactorial[k], {k, 0, (n + 1)/2}];
Table[a[n], {n, 0, 30}] (* Peter Luschny, Apr 24 2024 *)

Formula

a(n) = Sum_{j=0..floor((n+1)/2)} A000166(j)*A011973(n+1,j).

a(n) mod 2 = A131735(n+3).

Row sums of A371995(n+1), which are the antidiagonals of A098825. - Peter Luschny, Apr 24 2024

a(n) ~ sqrt(Pi) * exp(sqrt(n/2) - n/2 - 7/8) * n^(n/2 + 1) / 2^((n+3)/2). - Vaclav Kotesovec, Apr 25 2024