A354152 a(n) is the number of permutations pi in S_n such that pi(i) - i != 1 (mod n) and pi(i) - i != -1 (mod n) for all i.

1, 0, 1, 1, 4, 13, 82, 579, 4740, 43387, 439794, 4890741, 59216644, 775596313, 10927434466, 164806435783, 2649391469060, 45226435601207, 817056406224418, 15574618910994665, 312400218671253764, 6577618644576902053, 145051250421230224306, 3343382818203784146955

Offset: 0

Author

Peter Kagey, May 27 2022

Keywords

• nonn

Comments

For n > 1, this is the number of ways of rearranging guests sitting at a circular table such that a guest may stay in the same seat, but cannot move exactly one seat to their left or right.

The recurrence comes from Doron Zeilberger's MENAGE program, available via the arXiv reference.

Examples

			For n = 5, the a(5) = 13 permutations are 12345, 12543, 14325, 14523, 15342, 32145, 34125, 34512, 35142, 42315, 42513, 45123, and 45312.
The first letter is never 2 or 5, the second letter is never 1 or 3, the third letter is never 2 or 4, the fourth letter is never 3 or 5 and the fifth letter is never 1 or 4.
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..400
• D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Crossrefs

Cf. A000179, A341439, A354408.

Formula

a(n) = n*a(n-1) + 3*a(n-2) + (-2n+6)*a(n-3) - 3*a(n-4) + (n-6)*a(n-5) + a(n-6) for n > 8.

a(2k+1) = A000179(2k+1) for k > 1.

Conjecture: a(2k) = A000179(2k) + 2 for k > 1.