A094047 -id:A094047 - cp's OEIS frontend

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.

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.

A137801 Number of arrangements of 2n couples into n cars such that each car contains 2 men and 2 women but no couple (cars are labeled).

Original entry on oeis.org

0, 6, 900, 748440, 1559930400, 6928346502000, 58160619655538400, 845986566719614320000, 19957466912796971445888000, 724891264860942581350908960000, 38873628093261330554954970801600000

Offset: 1

Max Alekseyev, Feb 10 2008

nonn

Proof of the formula (in Russian).

Cf. A094047, A137802.

{ a(n) = n! * sum(i=0,n, (-1)^i * sum(j=0,n-i, (2*n)! * (2*n-i-2*j)! / (n-i-j)! / i! / j! / 2^(2*n-2*i-j) ) ) }

a(n) = n! * A137802(n) = n! * SUM[i+j<=n] (-1)^i * (2n)! * (2n-i-2j)! / (n-i-j)! / i! / j! / 2^(2n-2i-j)

a(n) = A000459(n) * (2n)! / 2^n = A000316(n) * (2n)! / 4^n [From Max Alekseyev, Nov 03 2008]

A137802 Number of arrangements of 2n couples into n cars such that each car contains 2 men and 2 women but no couple (cars are unlabeled).

Original entry on oeis.org

0, 3, 150, 31185, 12999420, 9622703475, 11539805487210, 20981809690466625, 54997428661808232600, 199760599884519009411075, 973866344327734952575230750, 6207575427404936259602204502225

Offset: 1

Max Alekseyev, Feb 10 2008

nonn

Cf. A094047, A137801.

{ a(n) = sum(i=0,n, (-1)^i * sum(j=0,n-i, (2*n)! * (2*n-i-2*j)! / (n-i-j)! / i! / j! / 2^(2*n-2*i-j) ) ) }

a(n) = A137801(n) / n! = SUM[i+j<=n] (-1)^i * (2n)! * (2n-i-2j)! / (n-i-j)! / i! / j! / 2^(2n-2i-j)

A174563 Number of 3 X n Latin rectangles such that every element of the second row has the same cyclic order (see comment).

Original entry on oeis.org

1, 14, 133, 3300, 93889, 3391086, 148674191, 7796637196, 480640583751, 34370030511334, 2818294139246649, 262403744798653716, 27506121212584723373, 3222018028986227724702, 418998630100386520363619, 60138044879434564251209580, 9477043948863636836099726259, 1632099068624734991723488992214

Offset: 3

Vladimir Shevelev, Mar 22 2010

nonn

We say that an element alpha_i of a permutation alpha of {1,2,...,n} has cyclic order k if it belongs to a cycle of length k of alpha. If every cycle of alpha has length k, then k|n.

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr. Mat. [Journal published by the Academy of Sciences of Russia], 4 (1992), 91-110.
V. S. Shevelev, Modern enumeration theory of permutations with restricted positions, Diskr. Mat., 1993, 5, no.1, 3-35 (Russian) [English translation in Discrete Math. and Appl., 1993, 3:3, 229-263 (pp. 255-257)].

Cf. A000179, A000186, A000296, A094047, A174556, A174560, A174561.

Let G_n = A000296(n) = n! * Sum_{2*k_2+...+n*k_n=n, k_i>=0} Product_{i=2,...,n} (k_i!*i!^k_i)^(-1). Then a(n) = Sum_{k=0,...,floor(n/2)} binomial(n,k) * G_k * G_(n-k) * u_(n-2*k), where u(n) = A000179(n). - Vladimir Shevelev, Mar 30 2016

More terms from William P. Orrick, Jul 25 2020

A234618 Numbers of undirected cycles in the n-crown graph.

Original entry on oeis.org

1, 28, 586, 16676, 674171, 36729512, 2591431284, 229610080632, 24945009633237, 3259554588092452, 504229440385599358, 91120169013941688700, 19019291896651737256463, 4540685283391286195445008, 1229402290052883559000280168, 374675876836087520170128786864

Offset: 3

Eric W. Weisstein, Dec 28 2013

nonn

Andrew Howroyd, Table of n, a(n) for n = 3..50
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A070910, A094047, A137886.

a[n_] := Sum[Binomial[n, k]*((-1)^k*(k - 1)! + Sum[Sum[(-1)^i*i!*(k - i)!*(k - i - 1)!*Binomial[k, k - j]*Binomial[n - k, j]*Binomial[k - j, i]*Binomial[2*k - i - 1, i]/2, {i, 0, k - 1}], {j, 0, k}]), {k, 2, n}];
Table[a[n], {n, 3, 18}] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)
RecurrenceTable[{(n - 3) (180 n^5 - 3462 n^4 + 25685 n^3 - 91106 n^2 + 152414 n - 93847) a[n] == (360 n^8 - 8904 n^7 + 93172 n^6 - 538135 n^5 + 1875502 n^4 - 4041070 n^3 + 5268157 n^2 - 3817934 n + 1189124) a[n - 1] - (n - 1) (180 n^9 - 5262 n^8 + 67445 n^7 - 497202 n^6 + 2321291 n^5 - 7107149 n^4 + 14233985 n^3 - 17904305 n^2 + 12741400 n - 3858611) a[n - 2] - (n - 2) (n - 1) (180 n^9 - 5442 n^8 + 71807 n^7 - 543239 n^6 + 2598146 n^5 - 8144697 n^4 + 16705322 n^3 - 21515171 n^2 + 15619923 n - 4754598) a[n - 3] + 2 (n - 3) (n - 2) (n - 1) (540 n^7 - 12585 n^6 + 122039 n^5 - 636205 n^4 + 1920840 n^3 - 3360924 n^2 + 3186108 n - 1302080) a[n - 4] + 2 (n - 4) (n - 3) (n - 2) (n - 1) (540 n^7 - 13806 n^6 + 145494 n^5 - 814365 n^4 + 2591726 n^3 - 4628556 n^2 + 4207415 n - 1449736) a[n - 5] - (n - 5) (n - 4) (n - 3) (n - 2) (n - 1) (1440 n^6 - 28956 n^5 + 230284 n^4 - 915485 n^3 + 1878786 n^2 - 1811640 n + 577483) a[n - 6] + 3 (n - 6) (n - 5) (n - 4) (n - 3) (n - 2) (n - 1) (180 n^5 - 2562 n^4 + 13637 n^3 - 33023 n^2 + 34309 n - 10136) a[n - 7], a[3] == 1, a[4] == 28, a[5] == 586, a[6] == 16676, a[7] == 674171, a[8] == 36729512, a[9] == 2591431284}, a, {n, 3, 20}] (* Eric W. Weisstein, Oct 02 2017 *)

a(n) = Sum_{k=2..n} binomial(n,k) * ( (-1)^k*(k-1)! + Sum_{j=0..k} Sum_{i=0..k-1} (-1)^i*i!*(k-i)!*(k-i-1)!*binomial(k,k-j)*binomial(n-k,j)*binomial(k-j,i)*binomial(2*k-i-1,i)/2 ). - Andrew Howroyd, Feb 24 2016
Recurrence: (n-3)*(180*n^5 - 3462*n^4 + 25685*n^3 - 91106*n^2 + 152414*n - 93847)*a(n) = (360*n^8 - 8904*n^7 + 93172*n^6 - 538135*n^5 + 1875502*n^4 - 4041070*n^3 + 5268157*n^2 - 3817934*n + 1189124)*a(n-1) - (n-1)*(180*n^9 - 5262*n^8 + 67445*n^7 - 497202*n^6 + 2321291*n^5 - 7107149*n^4 + 14233985*n^3 - 17904305*n^2 + 12741400*n - 3858611)*a(n-2) - (n-2)*(n-1)*(180*n^9 - 5442*n^8 + 71807*n^7 - 543239*n^6 + 2598146*n^5 - 8144697*n^4 + 16705322*n^3 - 21515171*n^2 + 15619923*n - 4754598)*a(n-3) + 2*(n-3)*(n-2)*(n-1)*(540*n^7 - 12585*n^6 + 122039*n^5 - 636205*n^4 + 1920840*n^3 - 3360924*n^2 + 3186108*n - 1302080)*a(n-4) + 2*(n-4)*(n-3)*(n-2)*(n-1)*(540*n^7 - 13806*n^6 + 145494*n^5 - 814365*n^4 + 2591726*n^3 - 4628556*n^2 + 4207415*n - 1449736)*a(n-5) - (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(1440*n^6 - 28956*n^5 + 230284*n^4 - 915485*n^3 + 1878786*n^2 - 1811640*n + 577483)*a(n-6) + 3*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(180*n^5 - 2562*n^4 + 13637*n^3 - 33023*n^2 + 34309*n - 10136)*a(n-7). - Vaclav Kotesovec, Feb 25 2016
a(n) ~ Pi * BesselI(0,2) * n^(2*n) / exp(2*n+2). - Vaclav Kotesovec, Feb 25 2016

a(13) from Eric W. Weisstein, Jan 08 2014
a(14) from Eric W. Weisstein, Apr 09 2014
a(15)-a(16) from Andrew Howroyd, Feb 24 2016

A264801 Number of essentially different seating arrangements for 2n couples around a circular table with 4n seats such that no spouses are neighbors, the neighbors of each person have opposite gender and no person's neighbors belong to the same couple.

Original entry on oeis.org

0, 6, 2400, 6375600, 45927907200, 713518388352000, 21216194909362252800, 1105729617210350356224000, 94398452626533646953922560000, 12514511465855205467497303154688000, 2467490887755897725667792936979169280000, 698323914872709997998407130752506728284160000

Offset: 1

Hugo Pfoertner, Nov 25 2015

nonn

This might be called the "maximum diversity" menage problem. Arrangements that differ only by rotation or reflection are excluded by the following conditions: Seat number 1 is assigned to person A. Seat number 2 can only be taken by a person of the same gender as A. The second condition forces an mmffmmff... pattern.

			a(1)=0 because with 2 couples it is impossible to satisfy all three conditions.
a(2)=6 because only the following arrangements are possible with 4 couples: ABdaCDbc, ABcaDCbd, ACdaBDcb, ACbaDBcd, ADcaBCdb, ADbaCBdc. This corresponds to the (2*2-1)! possibilities for persons B, C and D to choose a seat. After the positions of A, B, C and D are fixed, only A000183(2*2)=1 possibility remains to arrange their spouses a, b, c  and d.

Cf. A000183, A007060, A094047, A114939, A258338.

a000183(N)={my(a0=[0,0,0,1,2,20],a=vector(N),
f(x)=fibonacci(x-1)+fibonacci(x+1)+2;);
if(N<7,a=a0[1..N],for(k=1,6,a[k]=a0[k]);
for(n=7,N,a[n] = (-1)^n*(4*n+f(n)) +
 (n/(n-1))*((n+1)*a[n-1] + 2*(-1)^n*f(n-1))
  - ((2*n)/(n-2))*((n-3)*a[n-2] + (-1)^n*f(n-2))
  + (n/(n-3))*((n-5)*a[n-3] + 2*(-1)^(n-1)*f(n-3))
  + (n/(n-4))*(a[n-4] + (-1)^(n-1)*f(n-4))));a};
a264901(limit)={my(a183=a000183(2*limit)); for(n=1,limit,print1((2*n-1)!*a183[2*n],", "))};
a264901(12) \\ Hugo Pfoertner, Sep 05 2020

a(n) = (2*n-1)! * A000183(2*n).

A306496 Number of (undirected) Hamiltonian cycles in the n-crown graph.

Original entry on oeis.org

0, 0, 1, 6, 156, 4800, 208440, 11939760, 874681920, 79795860480, 8873760470400, 1181869427692800, 185755937440550400, 34022680848982425600, 7183771725162237004800, 1732270657442505852672000, 473131604733608510097408000, 145308345869661566419795968000

Offset: 1

Eric W. Weisstein, May 06 2019

nonn

Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Cf. A094047.

a(n) = A094047(n)/2.

A176901 Number of 3 X n semireduced Latin rectangles, that is, having exactly n fixed points in the first two rows.

Original entry on oeis.org

4, 72, 1584, 70720, 3948480, 284570496, 25574768128, 2808243910656, 369925183388160, 57585548812887040, 10458478438093154304, 2191805683821733404672, 525011528578874444283904, 142540766765931981615759360, 43542026550306796238178877440, 14867182204795857282384287236096, 5640920219495105293649671985430528

Offset: 3

Vladimir Shevelev, Apr 28 2010

nonn

A Latin rectangle is called reduced if its first row is [1,2,...,n] (the number of 3 X n reduced Latin rectangles is given in A000186). Therefore a Latin rectangle having exactly n fixed points in the first two rows may be called "semireduced". Thus if A1(i), A2(i), i=1,...,n, are the first two rows, then, for every i, either A1(i)=i or A2(i)=i.

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr. Mat.(J. of the Akademy of Sciences of Russia) 4(1992), 91-110.
V. S. Shevelev, Modern enumeration theory of permutations with restricted positions, Diskr. Mat., 1993, 5, no.1, 3-35 (Russian).
V. S. Shevelev, Modern enumeration theory of permutations with restricted positions, English translation, Discrete Math. and Appl., 1993, 3:3, 229-263 (pp. 255-257).

Cf. A174563, A000179, A000186, A087981, A094047, A174556, A174560, A174561.

Let F_n = A087981(n) = n! * Sum_{2*k_2+...+n*k_n=n, k_i>=0} Product_{i=2..n} 2^k_i/(k_i!*i^k_i). Then a(n) = Sum_{k=0..floor(n/2)} binomial(n,k) * F_k * F_(n-k) * u_(n-2*k), where u(n) = A000179(n). - Vladimir Shevelev, Mar 30 2016

More terms from William P. Orrick, Jul 25 2020

cp's OEIS Frontend

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

A137801 Number of arrangements of 2n couples into n cars such that each car contains 2 men and 2 women but no couple (cars are labeled).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A137802 Number of arrangements of 2n couples into n cars such that each car contains 2 men and 2 women but no couple (cars are unlabeled).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A174563 Number of 3 X n Latin rectangles such that every element of the second row has the same cyclic order (see comment).

Views

Author

Keywords

Comments

References

Crossrefs

Formula

Extensions

A234618 Numbers of undirected cycles in the n-crown graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A264801 Number of essentially different seating arrangements for 2n couples around a circular table with 4n seats such that no spouses are neighbors, the neighbors of each person have opposite gender and no person's neighbors belong to the same couple.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A306496 Number of (undirected) Hamiltonian cycles in the n-crown graph.

Views

Author

Keywords

Links

Crossrefs

Formula

A176901 Number of 3 X n semireduced Latin rectangles, that is, having exactly n fixed points in the first two rows.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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.