A114939 -id:A114939 - cp's OEIS frontend

A114938 Number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal.

1, 0, 2, 30, 864, 39480, 2631600, 241133760, 29083420800, 4467125013120, 851371260364800, 197158144895712000, 54528028997584665600, 17752366094818747392000, 6720318485119046923315200, 2927066537906697348594432000, 1453437879238150456164433920000

Offset: 0

Hugo Pfoertner, Jan 08 2006

a(n) is also the number of (0,1)-matrices A=(a_ij) of size n X 2n such that each row has exactly two 1's and each column has exactly one 1 and with the restriction that no 1 stands on the line from a_11 to a_22. - Shanzhen Gao, Feb 24 2010
a(n) is the number of permutations of the multiset {1,1,2,2,...,n,n} with no fixed points. - Alexander Burstein, May 16 2020
Also the number of 2-uniform ordered set partitions of {1...2n} containing no two successive vertices in the same block. - Gus Wiseman, Jul 04 2020

			a(2) = 2 because there are two permutations of {1,1,2,2} avoiding equal consecutive terms: 1212 and 2121.

R. P. Stanley, Enumerative Combinatorics Volume I, Cambridge University Press, 1997. Chapter 2, Sieve Methods, Example 2.2.3, page 68.

Seiichi Manyama, Table of n, a(n) for n = 0..238 (terms 1..100 from Andrew Woods)
H. Eriksson and A. Martin, Enumeration of Carlitz multipermutations, arXiv:1702.04177 [math.CO], 2017.

Cf. A114939 = preferred seating arrangements of n couples.
Cf. A007060 = arrangements of n couples with no adjacent spouses; A007060(n) = 2^n * A114938(n) (this sequence).
Cf. A104548, A193638.
Cf. A278990 = number of loopless linear chord diagrams with n chords.
Cf. A000806 = Bessel polynomial y_n(-1).
The version for multisets with prescribed multiplicities is A335125.
The version for prime indices is A335452.
Anti-run compositions are counted by A003242.
Anti-run compositions are ranked by A333489.
Inseparable partitions are counted by A325535.
Inseparable partitions are ranked by A335448.
Separable partitions are counted by A325534.
Separable partitions are ranked by A335433.
Cf. A007716, A128695, A292884, A335126, A335434, A335451.
Other sequences involving the multiset {1,1,2,2,...,n,n}: A001147, A007717, A020555, A094574, A316972.
Row n=2 of A322093.

[1] cat [n le 2 select 2*(n-1) else n*(2*n-1)*Self(n-1) + (n-1)*n*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Aug 10 2015

Table[Sum[Binomial[n,i](2n-i)!/2^(n-i) (-1)^i,{i,0,n}],{n,0,20}]  (* Geoffrey Critzer, Jan 02 2013, and adapted to the extension by Stefano Spezia, Nov 15 2018 *)
Table[Length[Select[Permutations[Join[Range[n],Range[n]]],!MatchQ[#,{_,x_,x_,_}]&]],{n,0,5}] (* Gus Wiseman, Jul 04 2020 *)
A114938[n_] := ((2 n)! Hypergeometric1F1[-n, -2 n, -2]) / 2^n;
Array[A114938, 17, 0]  (* Peter Luschny, Sep 04 2025 *)

A114938(n)=sum(k=0, n, binomial(n, k)*(-1)^(n-k)*(n+k)!/2^k);
vector(20, n, A114938(n-1)) \\ Michel Marcus, Aug 10 2015

def A114938(n): return (-1)^n*sum(binomial(n,k)*factorial(n+k)//(-2)^k for k in range(n+1))
[A114938(n) for n in range(31)] # G. C. Greubel, Sep 26 2023

a(n) = Sum_{k=0..n} ((binomial(n, k)*(-1)^(n-k)*(n+k)!)/2^k).
a(n) = (-1)^n * n! * A000806(n), n>0. - Vladeta Jovovic, Nov 19 2009
a(n) = n*(2*n-1)*a(n-1) + (n-1)*n*a(n-2). - Vaclav Kotesovec, Aug 07 2013
a(n) ~ 2^(n+1)*n^(2*n)*sqrt(Pi*n)/exp(2*n+1). - Vaclav Kotesovec, Aug 07 2013
a(n) = n! * A278990(n). - Alexander Burstein, May 16 2020
From G. C. Greubel, Sep 26 2023: (Start)
a(n) = (-1)^n * (i/e)*sqrt(2/Pi) * n! * BesselK(n+1/2, -1).
a(n) = [n! * (1/x) * p_{n+1}(x)]|A104548%20for%20p">{x= -1} (See A104548 for p{n}(x)).
E.g.f.: sqrt(Pi/(2*x)) * exp(-(1+x)^2/(2*x)) * erfi((1+x)/sqrt(2*x)).
Sum_{n >= 0} a(n)*x^n/(n!)^2 = exp(sqrt(1-2*x))/sqrt(1-2*x).
Sum_{n >= 0} a(n)*x^n/(n!*(n+1)!) = ( 1 - exp(-1 + sqrt(1-2*x)) )/x. (End)
a(n) = ((2*n)!/2^n) * hypergeom([-n], [-2*n], -2]) = A007060(n) / 2^n. - Peter Luschny, Sep 04 2025

a(0)=1 prepended by Seiichi Manyama, Nov 15 2018

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.

Original entry on oeis.org

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

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.

A141221 Number of ways for each of 2n (labeled) people in a circle to look at either a neighbor or the diametrally opposite person, such that no eye contact occurs.

Original entry on oeis.org

0, 30, 156, 826, 4406, 23562, 126104, 675074, 3614142, 19349430, 103593804, 554625898, 2969386478, 15897666066, 85113810056, 455687062274, 2439682811478, 13061709929934, 69930511268508, 374397872321626

Offset: 1

Max Alekseyev, Jun 14 2008

nonn

			a(1)=0 because two people always make eye contact when they look at each other.
a(2)=30 because 4 people can look at each other in 30 distinct ways without making eye contact.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Max A. Alekseyev and Gérard P. Michon, Making Walks Count: From Silent Circles to Hamiltonian Cycles, arXiv:1602.01396 [math.CO], 2016.
Art of Problem Solving Forum, How many distinct ways that silence will occur?
G. P. Michon, Brocoum's Screaming Circles.
G. P. Michon, Silent circles enumerated by Max Alekseyev.
G. P. Michon, A screaming game for short-sighted people.
Index entries for linear recurrences with constant coefficients, signature (8,-16,10,-1).

Cf. A094047, A114939.

Cf. A141384, A141385.

I:=[30, 156, 826, 4406]; [0] cat [n le 4 select I[n] else 8*Self(n-1) -16*Self(n-2) +10*Self(n-3) -Self(n-4): n in [1..30]]; // G. C. Greubel, Mar 31 2021

Join[{0}, LinearRecurrence[{8, -16, 10, -1}, {30, 156, 826, 4406}, 20]] (* Jean-François Alcover, Dec 14 2018 *)

def A141221_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( 2*x^2*(15 -42*x +29*x^2 -3*x^3)/((1-x)*(1-7*x+9*x^2-x^3)) ).list()
a=A141221_list(30)
print(a[1:]) # G. C. Greubel, Mar 31 2021

a(n) = 8*a(n-1) - 16*a(n-2) + 10*a(n-3) - a(n-4), for n > 1.
O.g.f.: 2*x^2*(15 -42*x +29*x^2 -3*x^3)/((1-x)*(1-7*x+9*x^2-x^3)). - R. J. Mathar, Jun 16 2008
a(n) = -7*[n=1] + (A141385(n) - 1). - G. C. Greubel, Mar 31 2021

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

cp's OEIS Frontend

A114938 Number of permutations of the multiset {1,1,2,2,...,n,n} with no two consecutive terms equal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

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

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

A141221 Number of ways for each of 2n (labeled) people in a circle to look at either a neighbor or the diametrally opposite person, such that no eye contact occurs.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

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