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