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
Examples
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 ...
Links
- Brian Moehring, Counting permutations pi in S_n such that pi(i) != i and pi(i) - k != i mod n, Mathematics Stack Exchange.
Crossrefs
Programs
-
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
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
Comments