A137729 -id:A137729 - cp's OEIS frontend

A094047 Number of seating arrangements of n couples around a round table (up to rotations) so that each person sits between two people of the opposite sex and no couple is seated together.

0, 0, 2, 12, 312, 9600, 416880, 23879520, 1749363840, 159591720960, 17747520940800, 2363738855385600, 371511874881100800, 68045361697964851200, 14367543450324474009600, 3464541314885011705344000, 946263209467217020194816000, 290616691739323132839591936000

Offset: 1

Matthijs Coster, Apr 29 2004

nonn

Also, the number of Hamiltonian directed circuits in the crown graph of order n.

Or the number of those 3 X n Latin rectangles (cf. A000186) the second row of which is a full cycle. - Vladimir Shevelev, Mar 22 2010

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.

Seiichi Manyama, Table of n, a(n) for n = 1..253
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12, arXiv:1510.07926, [math.CO], 2015-2016.
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Cf. A059375 (rotations are counted as different).

Cf. A000179, A000186, A114939, A137729, A306496.

A094047 := proc(n)
    if n < 3 then
        0;
    else
        (-1)^n*2*(n-1)!+n!*add( (-1)^j*(n-j-1)!*binomial(2*n-j-1,j),j=0..n-1) ;
    end if;
end proc: # R. J. Mathar, Nov 02 2015

Join[{0},Table[(-1)^n 2(n-1)!+n!Sum[(-1)^j (n-j-1)!Binomial[2n-j-1,j],{j,0,n-1}],{n,2,20}]] (* Harvey P. Dale, Mar 07 2012 *)

For n>1, a(n) = (-1)^n * 2 * (n-1)! + n! * Sum_{j=0..n-1} (-1)^j * (n-j-1)! * binomial(2*n-j-1,j). - Max Alekseyev, Feb 10 2008
a(n) = A059375(n) / (2*n) = A000179(n) * (n-1)!.
Conjecture: a(n) +(-n^2+2*n-3)*a(n-1) -(n-2)*(n^2-3*n+5)*a(n-2) -3*(n-2)*(n-3)*a(n-3) +(n-2)*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Nov 02 2015
Conjecture: (-n+2)*a(n) +(n-1)*(n^2-3*n+3)*a(n-1) +(n-2)*(n-1)*(n^2-3*n+3)*a(n-2) +(n-2)*(n-3)*(n-1)^2*a(n-3)=0. - R. J. Mathar, Nov 02 2015
a(n) = (n-1) * (n * (a(n-1) + a(n-2)) - 4 * (-1)^n * (n-3)!) for n > 3. - Seiichi Manyama, Jan 18 2020
a(n) = 2 * A306496(n). - Alois P. Heinz, Jun 19 2022

Better definition from Joel B. Lewis, Jun 30 2007

Formula and further terms from Max Alekseyev, Feb 10 2008

A208183 Number of distinct k-colored necklaces with n beads per color; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 6, 16, 4, 1, 1, 1, 24, 318, 188, 10, 1, 1, 1, 120, 11352, 30804, 2896, 26, 1, 1, 1, 720, 623760, 11211216, 3941598, 50452, 80, 1, 1, 1, 5040, 48648960, 7623616080, 15277017432, 586637256, 953056, 246, 1, 1

Offset: 0

Alois P. Heinz, Feb 24 2012

From Vaclav Kotesovec, Aug 23 2015: (Start)
Column k > 1 is asymptotic to k^(k*n-1/2) / ((2*Pi)^((k-1)/2) * n^((k+1)/2)).
Row r > 0 is asymptotic to (r*n)! / (r*n*(r!)^n). (End)

			A(1,4) =  6: {0123, 0132, 0213, 0231, 0312, 0321}.
A(3,2) =  4: {000111, 001011, 010011, 010101}.
A(4,2) = 10: {00001111, 00010111, 00100111, 01000111, 00011011, 00110011, 00101011, 01010011, 01001011, 01010101}.
Square array A(n,k) begins:
  1, 1,  1,     1,         1,              1, ...
  1, 1,  1,     2,         6,             24, ...
  1, 1,  2,    16,       318,          11352, ...
  1, 1,  4,   188,     30804,       11211216, ...
  1, 1, 10,  2896,   3941598,    15277017432, ...
  1, 1, 26, 50452, 586637256, 24934429725024, ...

Alois P. Heinz, Antidiagonals n = 0..35, flattened

Rows n=0-8 give: A000012, A104150, A137729, A208184, A208185, A208186, A208187, A208188, A208189.
Columns k=0+1, 2-8 give: A000012, A003239, A118644, A207816, A208190, A208191, A208192, A208193.
Main diagonal gives A252765.
Cf. A000010, A000142.

with(numtheory):
A:= (n, k)-> `if`(n=0 or k=0, 1,
              add(phi(n/d) *(k*d)!/(d!^k *k*n), d=divisors(n))):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[n_, k_] :=  If[n == 0 || k == 0, 1, Sum[EulerPhi[n/d]*(k*d)!/(d!^k*k*n), {d, Divisors[n]}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

A(n,k) = Sum_{d|n} phi(n/d)*(k*d)!/(d!^k*k*n) if n,k>0; A(n,k) = 1 else.

A(n,k) = Sum_{i=1..n} (k*gcd(n,i))!/(gcd(n,i)!^k*k*n) = Sum_{i=1..n} (k*n/gcd(n,i))!/((n/gcd(n,i))!^k*k*n)*phi(gcd(n,i))/phi(n/gcd(n,i)) for n,k >= 1, where phi = A000010. - Richard L. Ollerton, May 19 2021

A137730 Number of circular permutations of the multiset {1,1,2,2,...,n,n} (up to rotations) with odd distances between equal elements.

Original entry on oeis.org

1, 1, 7, 72, 1452, 43200, 1814760, 101606400, 7315680960, 658409472000, 72425043734400, 9560105533440000, 1491376463456140800, 271430516305428480000, 57000408424183569945600, 13680098021793595392000000, 3720986661927868408018944000, 1138621918549924531666944000000

Offset: 1

Max Alekseyev, Feb 09 2008

nonn

Cf. A114938, A137729, A137737, A137749.

a[1]=1;a[n_]:=Sum[Abs[(n-1)!-n!*StirlingS1[n-1,j]],{j,0,n-1}]/2;Flatten[Table[a[n],{n,1,18}]] (* Detlef Meya, Apr 10 2024 *)

For even n, a(n) = n!^2 / (2n). For odd n, a(n) = (n!^2 + n!) / (2n).

a(1) = 1; For n > 1: a(n) = Sum_{j=0..n-1} (abs((n - 1)! - n!*Stirling1(n - 1, j)))/2. - Detlef Meya, Apr 10 2024

A137737 Number of circular permutations of the multiset {1,1,2,2,...,n,n} (up to rotations) with even distances between equal elements.

Original entry on oeis.org

0, 1, 0, 30, 0, 13560, 0, 27785520, 0, 162030637440, 0, 2156625389318400, 0, 56857271240920550400, 0, 2686506065987036477184000, 0, 211180868835057744408834048000, 0, 26072812428113877344085395644416000, 0

Offset: 1

Max Alekseyev, Feb 09 2008

nonn

Cf. A114938, A137729, A137730, A137749

For odd n, a(n) = 0. For even n, a(n) = (n!^3 / (n/2)!^2 / 2^n + n!) / (2n).

a(2n) = A137749(n)

A137749 Number of circular permutations of the multiset {1,1,2,2,...,2n,2n} (up to rotations) with even distances between equal elements.

Original entry on oeis.org

1, 30, 13560, 27785520, 162030637440, 2156625389318400, 56857271240920550400, 2686506065987036477184000, 211180868835057744408834048000, 26072812428113877344085395644416000, 4829206317935252350431489703482654720000

Offset: 1

Max Alekseyev, Feb 09 2008

nonn

Cf. A114938, A137729, A137730, A137737

a(n) = ((2n)!^3 / n!^2 / 2^(2n) + (2n)!) / (4n).

a(n) = A137737(2n)

A114939 Number of essentially different seating arrangements for n couples around a circular table with 2n seats avoiding spouses being neighbors and avoiding clusters of 3 persons with equal gender.

Original entry on oeis.org

0, 1, 7, 216, 10956, 803400, 83003040, 11579823360, 2080493573760, 469031859192960, 129727461014726400, 43176116371928601600, 17025803126147196057600, 7850538273249476117913600

Offset: 1

Hugo Pfoertner, Jan 08 2006

Arrangements that differ only by rotation or reflection are excluded by the following conditions: Seat number 1 is assigned to person (a). Person (a)'s spouse (A) can only take seats with numbers <=(n+1). If (A) gets seat n+1 (i.e. sits exactly opposite to her/his spouse) then person (B) can only take seats with numbers <= n.

			a(2)=1 because the only valid arrangement is aBAb.
a(3)=7 because the only valid arrangements under the given conditions are: abAcBC, aBAcbC, aBcAbC, aBcACb, acAbCB, acBAbC, aCAbcB.

M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12; arXiv:1510.07926 [math.CO], 2015-2016.

Cf. A114938, A137729, A137730, A137737, A137749, A258338.

a[1] = 0;
a[n_] := (n-1)!/4 Sum[(-1)^j(n-j)! SeriesCoefficient[ SeriesCoefficient[Tr[ MatrixPower[{{0, 1, 0, y^2, 0, 0}, {z y^2, 0, 1, 0, y^2, 0}, {z y^2, 0, 0, 0, y^2, 0}, {0, 1, 0, 0, 0, z}, {0, 1, 0, y^2, 0, z}, {0, 0, 1, 0, y^2, 0}}, 2n]], {y, 0, 2n}] , {z, 0, j}], {j, 0, n}];
Array[a, 14] (* Jean-François Alcover, Dec 03 2018, from PARI *)

{ a(n) = if(n<=1, 0, (-1)^n*(n-1)!*2^(n-1) + n! * polcoeff( polcoeff( [0, 2*y*z^3 + z^2, -3*y*z^5 - 4*z^4 + ((-2*y^2 - 1)/y)*z^3, 6*y*z^7 + (4*y^2 + 11)*z^6 + ((8*y^2 + 4)/y)*z^5 + 3*z^4] * sum(j=0,n-1, j! * [0, 0, 0, -z^6 + z^4; 1, 0, 0, ((y^2 + 1)/y)*z^5 - 2*z^4 + ((-y^2 - 1)/y)*z^3; 0, 1, 0, ((2*y^2 + 2)/y)*z^3 + z^2; 0, 0, 1, -2*z^2]^(n+j) ) * [1,0,0,0]~, 2*n,z), 0,y) / 2 ); }

See Alekseyev (2016) and the PARI code for the formula.

a(n) = A258338(n) / (4*n).

a(4)-a(7) corrected, formula and further term provided by Max Alekseyev, Feb 15 2008

A258338 Ternary ménage problem: number of seating arrangements for n opposite-sex couples around a circular table such that no spouses and no triples of the same sex seat next to each other. Seats are labeled.

Original entry on oeis.org

0, 8, 84, 3456, 219120, 19281600, 2324085120, 370554347520, 74897768655360, 18761274367718400, 5708008284647961600, 2072453585852572876800, 885341762559654194995200, 439630143301970662603161600, 251099117378080818090596352000, 163464570058143774978660630528000

Offset: 1

Max Alekseyev, May 27 2015

nonn

Conjecture: (a(n)/n!^2)^(1/n) ~ (3+sqrt(5))/2. - Vaclav Kotesovec, May 29 2015

Max Alekseyev, Table of n, a(n) for n = 1..100
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12; arXiv:1510.07926 [math.CO], 2015-2016.

Cf. A114939 (counts up to rotations and reflections)

Cf. A059375, A094047, A000179, A114938, A137729, A137730, A137737, A137749.

a[1] = 0;
a[n_] := n! Sum[(-1)^j (n-j)! SeriesCoefficient[ SeriesCoefficient[ Tr[ MatrixPower[{{0, 1, 0, y^2, 0, 0}, {z y^2, 0, 1, 0, y^2, 0}, {z y^2, 0, 0, 0, y^2, 0}, {0, 1, 0, 0, 0, z}, {0, 1, 0, y^2, 0, z}, {0, 0, 1, 0, y^2, 0}}, 2n]], {y, 0, 2n}], {z, 0, j}], {j, 0, n}];
Array[a, 16] (* Jean-François Alcover, Dec 03 2018, from 1st PARI program *)

{ a(n) = if(n<2, 0, n! * sum(j=0,n, (-1)^j * (n-j)! *polcoeff( polcoeff( trace([0, 1, 0, y^2, 0, 0; z*y^2, 0, 1, 0, y^2, 0; z*y^2, 0, 0, 0, y^2, 0; 0, 1, 0, 0, 0, z; 0, 1, 0, y^2, 0, z; 0, 0, 1, 0, y^2, 0]^(2*n)), 2*n,y) ,j,z)) ); }

{ a(n) = if(n<2, 0, n! *  polcoeff( serlaplace( polcoeff( trace([-y, z*y, z, 0, z*y, -y; -y, (z - 1)*y, 0, (z - 1)*y^2, z*y, -y; 0, (z - 1)*y, 0, (z - 1)*y^2, 0, -y; -y, 0, z - 1, 0, (z - 1)*y, 0; -y, z*y, z - 1, 0, (z - 1)*y, -y; -y, z*y, 0, z*y^2, z*y, -y]^n), n, y) )/(1-z) + O(z^(n+1)), n, z) ) }

a(n) = A114939(n) * 4 * n.

A275801 Number of alternating permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 0, 1, 4, 53, 936, 25325, 933980, 45504649, 2824517520, 217690037497, 20394614883316, 2282650939846781, 300814135522967736, 46103574973075123877, 8130996533576437261772, 1635028654501420083152785, 371853339350614571322913824, 94969025880924845123887493233

Offset: 0

Max Alekseyev, Aug 09 2016

nonn

Number of permutations (p(1),...,p(2n)) of {1,1,2,2,...,n,n} satisfying p(1) < p(2) > p(3) < ... < p(2n).

a(n) <= A005799(n) <= A275829(n).

Max Alekseyev, Table of n, a(n) for n = 0..70
Wikipedia, Alternating permutation.
hkju et al., Number of updown sequences of 1,1,2,2,...,n,n, Mathoverflow, 2016.

Column k=2 of A275784.

Cf. A000111, A001250, A000459, A004075, A005799, A114938, A137729, A137730, A137737, A137749, A275829.

A275829 Number of weakly alternating permutations of the multiset {1,1,2,2,...,n,n}.

Original entry on oeis.org

1, 1, 2, 12, 140, 2564, 68728, 2539632, 123686800, 7677924688, 591741636128, 55438330474944, 6204888219697856, 817697605612952384, 125322509904814743424, 22102340129003429880576, 4444468680409243484516608, 1010802175212828388101900544, 258152577318424951261637001728

Offset: 0

Max Alekseyev, Aug 11 2016

nonn

Number of permutations (p(1),...,p(2n)) of {1,1,2,2,...,n,n} satisfying p(1) <= p(2) >= p(3) <= p(4) >= p(5) <= ... <= p(2n).

a(n) >= A005799(n) >= A275801(n).

Max Alekseyev, Table of n, a(n) for n = 0..70

Cf. A000111, A001250, A000459, A004075, A005799, A114938, A137729, A137730, A137737, A137749, A275801.

A207816 Number of distinct necklaces with n red, n green, n blue and n white beads.

Original entry on oeis.org

1, 6, 318, 30804, 3941598, 586637256, 96197661156, 16875655269948, 3111284141045598, 595909785174057204, 117634021777132574568, 23797087019979071174580, 4912693780461352534397604, 1031629572413246016139181544, 219809927417367534490107035244, 47426945434432859336092700072304

Offset: 0

Thotsaporn Thanatipanonda, Feb 20 2012

nonn

			For n=1, a(1)=6 since for four beads necklaces with each bead from each of the four colors say (R,G,B,W), we can arrange as following, [R,G,B,W], [R,G,W,B], [R,B,G,W], [R,B,W,G], [R,W,G,B] and [R,W,B,G].

Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A003239, A118644, A137729.

Column k=4 of A208183. - Alois P. Heinz, Feb 24 2012

with(combinat): with(numtheory):
# This formula comes from Polya Counting Theorem:
# Z(C_n) = add(phi(d)*(a_d)^(n/d), d in divisors(n))/n;
PolyaBrace:= proc(S) option remember; local n, s, d;
               n:= add(s, s=S);
               add(phi(d) *PolyaCoeff(d, S), d=divisors(n))/n
             end:
# Find coeff of prod(a[i]^s[i], i=1..n) of a_d^(n/d) (symmetric function)
PolyaCoeff:= proc(d, S) option remember; local n, pow, s;
               n:= add(s, s=S);
               pow:= n/d;
               if {seq(s mod d, s = S)} = {0}
                  then multinomial(pow, seq(s/d, s = S))
                  else 0
               fi:
             end:
a:= n-> `if`(n=0, 1, PolyaBrace([n$4])):
seq(a(n), n=0..20);

a[n_] := DivisorSum[n, EulerPhi[n/#] (4#)!/(#!^4 * 4n)&]; a[0]=1;
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 24 2017, after Alois P. Heinz *)

a(n) = Sum_{d|n} phi(n/d)*(4*d)!/(d!^4*4*n) if n>0 and a(0) = 1. - Alois P. Heinz, Feb 24 2012

a(n) ~ 2^(8*n-5/2) / (Pi^(3/2) * n^(5/2)). - Vaclav Kotesovec, Aug 23 2015

cp's OEIS Frontend

A094047 Number of seating arrangements of n couples around a round table (up to rotations) so that each person sits between two people of the opposite sex and no couple is seated together.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A208183 Number of distinct k-colored necklaces with n beads per color; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A137730 Number of circular permutations of the multiset {1,1,2,2,...,n,n} (up to rotations) with odd distances between equal elements.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A137737 Number of circular permutations of the multiset {1,1,2,2,...,n,n} (up to rotations) with even distances between equal elements.

Views

Author

Keywords

Crossrefs

Formula

A137749 Number of circular permutations of the multiset {1,1,2,2,...,2n,2n} (up to rotations) with even distances between equal elements.

Views

Author

Keywords

Crossrefs

Formula

A114939 Number of essentially different seating arrangements for n couples around a circular table with 2n seats avoiding spouses being neighbors and avoiding clusters of 3 persons with equal gender.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A258338 Ternary ménage problem: number of seating arrangements for n opposite-sex couples around a circular table such that no spouses and no triples of the same sex seat next to each other. Seats are labeled.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A275801 Number of alternating permutations of the multiset {1,1,2,2,...,n,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A275829 Number of weakly alternating permutations of the multiset {1,1,2,2,...,n,n}.

Views