A354152 - OEIS

%I #17 May 28 2022 17:36:21

%S 1,0,1,1,4,13,82,579,4740,43387,439794,4890741,59216644,775596313,

%T 10927434466,164806435783,2649391469060,45226435601207,

%U 817056406224418,15574618910994665,312400218671253764,6577618644576902053,145051250421230224306,3343382818203784146955

%N 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.

%C 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.

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

%H Peter Kagey, <a href="/A354152/b354152.txt">Table of n, a(n) for n = 0..400</a>

%H D. Zeilberger, <a href="https://arxiv.org/abs/1401.1089">Automatic Enumeration of Generalized Menage Numbers</a>, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

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

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

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

%e For n = 5, the a(5) = 13 permutations are 12345, 12543, 14325, 14523, 15342, 32145, 34125, 34512, 35142, 42315, 42513, 45123, and 45312.

%e 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.

%Y Cf. A000179, A341439, A354408.

%K nonn

%O 0,5

%A _Peter Kagey_, May 27 2022