A341439 Table of generalized ménage numbers read by antidiagonals upward: T(n,k) is the number of permutations pi in S_k such that pi(i) != i, i+n (mod k) for all i; n, k >= 1.

0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 0, 1, 2, 4, 13, 0, 0, 1, 2, 13, 80, 0, 1, 1, 9, 13, 82, 579, 0, 0, 2, 2, 13, 80, 579, 4738, 0, 1, 1, 4, 44, 82, 579, 4740, 43387, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 0, 1, 2, 9, 13, 265, 579, 4752, 43390, 439794, 4890741

Offset: 1

Author

Peter Kagey, Feb 11 2021

Keywords

• nonn
• tabl

Comments

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

Examples

			Table begins:
n\k | 1 2 3 4  5   6    7     8
----+--------------------------
  1 | 0 0 1 2 13  80  579  4738
  2 | 0 1 1 4 13  82  579  4740
  3 | 0 0 2 2 13  80  579  4738
  4 | 0 1 1 9 13  82  579  4752
  5 | 0 0 1 2 44  80  579  4738
  6 | 0 1 2 4 13 265  579  4740
  7 | 0 0 1 2 13  80 1854  4738
  8 | 0 1 1 9 13  82  579 14833
		

Links

• D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Crossrefs

Cf. A000166, A000179, A277256, A354408.

Formula

T(n,n) = A000166(n) for n >= 1.

T(1,k) = A000179(k).

T(k-1,k) = A000179(k) for k >= 2.

T(n,k) = T(n+k, k).

T(2,k) = k*T(2,k-1) + 3*T(2,k-2) + (-2*k+6)*T(2,k-3) - 3*T(2,k-4) + (k-6)*T(2,k-5) + T(2,k-6) for k > 8.

T(n,k) = A277256(gcd(n,k),k/gcd(n,k)). - Pontus von Brömssen, May 31 2022