A354408 Triangle read by rows of generalized ménage numbers: T(n,k) is the number of permutations pi in S_n such that pi(i) != i and pi(i) != i+k (mod n) for all i; n, 1 <= k < n.

0, 1, 1, 2, 4, 2, 13, 13, 13, 13, 80, 82, 80, 82, 80, 579, 579, 579, 579, 579, 579, 4738, 4740, 4738, 4752, 4738, 4740, 4738, 43387, 43387, 43390, 43387, 43387, 43390, 43387, 43387, 439792, 439794, 439792, 439794, 440192, 439794, 439792, 439794, 439792

Offset

2,4

Comments

Conjectures: (Start)

T(n,1) <= T(n,k) for all 1 < k < n.

With the exception of T(6,3) = 80, T(n,k) > T(n,1) whenever gcd(n,k) > 1. (End)

Links

Table of n, a(n) for n=2..46.

Brian Moehring, Counting permutations pi in S_n such that pi(i) != i and pi(i) - k != i mod n, Mathematics Stack Exchange.

Formula

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

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

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

T(n,k) = A000179(n) if k is coprime to n.

T(n,j) = T(n,k) if gcd(n,j) = gcd(n,k). - Pontus von Brömssen, May 30 2022

Conjecture: T(n,j) < T(n,k) if gcd(n,j) < gcd(n,k) and (n,k) != (6,3). - Pontus von Brömssen, May 31 2022

Example

Triangle begins:
  n\k|     1     2     3     4     5     6     7     8
-----+------------------------------------------------
   2 |     0
   3 |     1     1
   4 |     2     4     2
   5 |    13    13    13    13
   6 |    80    82    80    82    80
   7 |   579   579   579   579   579   579
   8 |  4738  4740  4738  4752  4738  4740  4738
   9 | 43387 43387 43390 43387 43387 43390 43387 43387
  ...

Prog

(Python)
from sympy import Matrix
def A354408(n, k):
    return Matrix(n, n, lambda i, j:int(i!=j and i!=(j+k)%n)).per() # Pontus von Brömssen, May 31 2022
(Python)
# This version, based on the formula in A277256, is much faster than the version using permanents, at least for large n.
from sympy import factorial, gcd, sqrt
from sympy.abc import z
def A354408(n, k):
    k=gcd(n, k)
    F=((1-sqrt(1+4*z))/2)**(2*(n//k))+((1+sqrt(1+4*z))/2)**(2*(n//k))
    p=(F**k).series(z, 0, n+1)
    return sum((-1)**j*factorial(n-j)*p.coeff(z, j) for j in range(n+1)) # Pontus von Brömssen, Jun 02 2022

Crossrefs

Cf. A277256, A341439, A354409 (record values in rows).

Cf. A000179 (column 1), A354152 (column 2).

Sequence in context: A006018 A152666 A153801 * A062867 A264027 A113539

Adjacent sequences: A354405 A354406 A354407 * A354409 A354410 A354411

Keyword

nonn,tabl

Author

Peter Kagey, May 25 2022

Status

approved