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,4

Links

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

Wikipedia, Permutation.

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

Example

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.

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 - k, k] * Subfactorial[k], {k, 0, n/2}];
Table[a[n], {n, 0, 31}]  # Peter Luschny, Apr 24 2024

Crossrefs

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

Sequence in context: A036613 A036614 A036718 * A134964 A318798 A318851

Adjacent sequences: A372099 A372100 A372101 * A372103 A372104 A372105

Keyword

nonn

Author

Alois P. Heinz, Apr 18 2024

Status

approved