cp's OEIS Frontend

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.

%I A354408 #46 Aug 12 2022 20:18:17
%S A354408 0,1,1,2,4,2,13,13,13,13,80,82,80,82,80,579,579,579,579,579,579,4738,
%T A354408 4740,4738,4752,4738,4740,4738,43387,43387,43390,43387,43387,43390,
%U A354408 43387,43387,439792,439794,439792,439794,440192,439794,439792,439794,439792
%N 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.
%C A354408 Conjectures: (Start)
%C A354408 T(n,1) <= T(n,k) for all 1 < k < n.
%C A354408 With the exception of T(6,3) = 80, T(n,k) > T(n,1) whenever gcd(n,k) > 1. (End)
%H A354408 Brian Moehring, <a href="https://math.stackexchange.com/q/4458625/121988#comment9340570_4458625">Counting permutations pi in S_n such that pi(i) != i and pi(i) - k != i mod n</a>, Mathematics Stack Exchange.
%F A354408 T(n,1) = A000179(n).
%F A354408 T(n,k) = T(n,n-k).
%F A354408 T(n,k) = A341439(k,n).
%F A354408 T(n,k) = A000179(n) if k is coprime to n.
%F A354408 T(n,j) = T(n,k) if gcd(n,j) = gcd(n,k). - _Pontus von Brömssen_, May 30 2022
%F A354408 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
%e A354408 Triangle begins:
%e A354408   n\k|     1     2     3     4     5     6     7     8
%e A354408 -----+------------------------------------------------
%e A354408    2 |     0
%e A354408    3 |     1     1
%e A354408    4 |     2     4     2
%e A354408    5 |    13    13    13    13
%e A354408    6 |    80    82    80    82    80
%e A354408    7 |   579   579   579   579   579   579
%e A354408    8 |  4738  4740  4738  4752  4738  4740  4738
%e A354408    9 | 43387 43387 43390 43387 43387 43390 43387 43387
%e A354408   ...
%o A354408 (Python)
%o A354408 from sympy import Matrix
%o A354408 def A354408(n,k):
%o A354408     return Matrix(n,n,lambda i,j:int(i!=j and i!=(j+k)%n)).per() # _Pontus von Brömssen_, May 31 2022
%o A354408 (Python)
%o A354408 # This version, based on the formula in A277256, is much faster than the version using permanents, at least for large n.
%o A354408 from sympy import factorial,gcd,sqrt
%o A354408 from sympy.abc import z
%o A354408 def A354408(n,k):
%o A354408     k=gcd(n,k)
%o A354408     F=((1-sqrt(1+4*z))/2)**(2*(n//k))+((1+sqrt(1+4*z))/2)**(2*(n//k))
%o A354408     p=(F**k).series(z,0,n+1)
%o A354408     return sum((-1)**j*factorial(n-j)*p.coeff(z,j) for j in range(n+1)) # _Pontus von Brömssen_, Jun 02 2022
%Y A354408 Cf. A277256, A341439, A354409 (record values in rows).
%Y A354408 Cf. A000179 (column 1), A354152 (column 2).
%K A354408 nonn,tabl
%O A354408 2,4
%A A354408 _Peter Kagey_, May 25 2022