A277256 -id:A277256 - 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.

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

Peter Kagey, May 25 2022

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)

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

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

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

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

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

# 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

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

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.

Original entry on oeis.org

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

Peter Kagey, Feb 11 2021

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

			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

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

Cf. A000166, A000179, A277256, A354408.

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

A277257 Multi-table menage seating arrangements: T(n,k) for n,k >= 1 equals the number of ways to seat nk married couples at n round tables with 2k seats each, such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other.

Original entry on oeis.org

0, 8, 0, 96, 384, 12, 3456, 460800, 236160, 96, 168960, 3065610240, 125962905600, 764467200, 3120, 12211200, 51115799347200, 453840358706380800, 226918953109094400, 6383697868800, 115200, 1196052480, 1816224465420288000, 6896429934345052028928000

Offset: 1

Max Alekseyev, Oct 07 2016

Tables and seats are labeled. For unlabeled version, see A277265.

			Table T(n,k):
n=1: 0, 0, 12, 96, 3120, 115200, ...
n=2: 8, 384, 236160, 764467200, ...
n=3: 96, 460800, 125962905600, ...
n=4: 3456, 3065610240, 453840358706380800, ...
...

Cf. A059375 (row n=1), A277265.

T(n,k) = A277256(n,k) * 2^n * (n*k)!.

A277265 Multi-table menage seating arrangements: T(n,k) for n,k >= 1 equals the number of ways to seat nk married couples at n unlabeled round tables with 2k unlabeled seats each, such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other.

Original entry on oeis.org

0, 1, 0, 2, 12, 2, 9, 1200, 3280, 12, 44, 498960, 97193600, 5972400, 312, 265, 415981440, 14591060915200, 73866846715200, 31918489344, 9600, 1854, 615853022400, 7390721380256614400, 9022243072072662432000, 287350869074488547328, 393956489203200, 416880, 14833, 1477095102362880

Offset: 1

Max Alekseyev, Oct 07 2016

For labeled version, see A277257.

			Table T(n,k):
n=1: 0, 0, 2, 12, 312, 9600, ...
n=2: 1, 12, 3280, 5972400, ...
n=3: 2, 1200, 97193600, ...
n=4: 9, 498960, 14591060915200, ...
...

Cf. A094047 (row n=1), A000166 (column k=1), A277256, A277257.

T(n,k) = A277256(n,k) * (n*k)! / n! / k^n.

A354409 Maximum value in the n-th row of A354408.

Original entry on oeis.org

0, 1, 4, 13, 82, 579, 4752, 43390, 440192, 4890741, 59245120, 775596313, 10930514688, 164806652728, 2649865335040, 45226435601207, 817154768973824, 15574618910994665, 312426715251262464, 6577619798222863696, 145060238642780180480, 3343382818203784146955

Offset: 2

Peter Kagey, May 25 2022

nonn

The minimum value appears to be given by A000179.
The differences between this sequence and A000179 begin 0, 0, 2, 0, 2, 0, 14, 3, 400, 0, 28478, ...
Conjecture: a(n) = A000179(n) if and only if n is prime.

Pontus von Brömssen, Table of n, a(n) for n = 2..450

Cf. A000179, A032742, A277256, A354408.

Conjecture: a(n) = A354408(n, A032742(n)) for n != 6. - Pontus von Brömssen, May 31 2022

a(13)-a(23) from Pontus von Brömssen, May 31 2022

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A277257 Multi-table menage seating arrangements: T(n,k) for n,k >= 1 equals the number of ways to seat n*k married couples at n round tables with 2*k seats each, such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A277265 Multi-table menage seating arrangements: T(n,k) for n,k >= 1 equals the number of ways to seat n*k married couples at n unlabeled round tables with 2*k unlabeled seats each, such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A354409 Maximum value in the n-th row of A354408.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A277257 Multi-table menage seating arrangements: T(n,k) for n,k >= 1 equals the number of ways to seat nk married couples at n round tables with 2k seats each, such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other.

A277265 Multi-table menage seating arrangements: T(n,k) for n,k >= 1 equals the number of ways to seat nk married couples at n unlabeled round tables with 2k unlabeled seats each, such that (i) the gender of persons alternates around each table; and (ii) spouses do not sit next to each other.