A094047 -id:A094047 - cp's OEIS frontend

A260321 Erroneous version of A094047.

-1, 0, 2, 12, 312, 9600, 410800, 23879520, 1749363840, 159591720960

Offset: 1

dead

H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]

A000179 Ménage numbers: a(0) = 1, a(1) = -1, and for n >= 2, a(n) = number of permutations s of [0, ..., n-1] such that s(i) != i and s(i) != i+1 (mod n) for all i.

1, -1, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123

Offset: 0

N. J. A. Sloane

According to rook theory, John Riordan considered a(1) to be -1. - Vladimir Shevelev, Apr 02 2010
This is also the value that the formulas of Touchard and of Wyman and Moser give and is compatible with many recurrences. - William P. Orrick, Aug 31 2020
Or, for n >= 3, the number of 3 X n Latin rectangles the second row of which is full cycle with a fixed order of its elements, e.g., the cycle (x_2,x_3,...,x_n,x_1) with x_1 < x_2 < ... < x_n. - Vladimir Shevelev, Mar 22 2010
Muir (p. 112) gives essentially this recurrence (although without specifying any initial conditions). Compare A186638. - N. J. A. Sloane, Feb 24 2011
Sequence discovered by Touchard in 1934. - L. Edson Jeffery, Nov 13 2013
Although these are also known as Touchard numbers, the problem was formulated by Lucas in 1891, who gave the recurrence formula shown below. See Cerasoli et al., 1988. - Stanislav Sykora, Mar 14 2014
An equivalent problem was formulated by Tait; solutions to Tait's problem were given by Muir (1878) and Cayley (1878). - William P. Orrick, Aug 31 2020
From Vladimir Shevelev, Jun 25 2015: (Start)
According to the ménage problem, 2*n!*a(n) is the number of ways of seating n married couples at 2*n chairs around a circular table, men and women in alternate positions, so that no husband is next to his wife.
It is known [Riordan, ch. 7] that a(n) is the number of arrangements of n non-attacking rooks on the positions of the 1's in an n X n (0,1)-matrix A_n with 0's in positions (i,i), i = 1,...,n, (i,i+1), i = 1,...,n-1, and (n,1). This statement could be written as a(n) = per(A_n). For example, A_5 has the form
    001*11
    1*0011
    11001*                        (1)
    11*100
    0111*0,
where 5 non-attacking rooks are denoted by {1*}.
We can indicate a one-to-one correspondence between arrangements of n non-attacking rooks on the 1's of a matrix A_n and arrangements of n married couples around a circular table by the rules of the ménage problem, after the ladies w_1, w_2, ..., w_n have taken the chairs numbered
    2*n, 2, 4, ..., 2*n-2         (2)
respectively. Suppose we consider an arrangement of rooks: (1,j_1), (2,j_2), ..., (n,j_n). Then the men m_1, m_2, ..., m_n took chairs with numbers
    2*j_i - 3 (mod 2*n),          (3)
where the residues are chosen from the interval[1,2*n]. Indeed {j_i} is a permutation of 1,...,n. So {2*j_i-3}(mod 2*n) is a permutation of odd positive integers <= 2*n-1. Besides, the distance between m_i and w_i cannot be 1. Indeed, the equality |2*(j_i-i)-1| = 1 (mod 2*n) is possible if and only if either j_i=i or j_i=i+1 (mod n) that correspond to positions of 0's in matrix A_n.
For example, in the case of positions of {1*} in(1) we have j_1=3, j_2=1, j_3=5, j_4=2, j_5=4. So, by(2) and (3) the chairs 1,2,...,10 are taken by m_4, w_2, m_1, w_3, m_5, w_4, m_3, w_5, m_2, w_1, respectively. (End)
The first 20 terms of this sequence were calculated in 1891 by E. Lucas (see [Lucas, p. 495]). - Peter J. C. Moses, Jun 26 2015
From Ira M. Gessel, Nov 27 2018: (Start)
If we invert the formula
  Sum_{ n>=0 } u_n z^n = ((1-z)/(1+z)) F(z/(1+z)^2)
that Don Knuth mentions (see link) (i.e., set x=z/(1+z)^2 and solve for z in terms of x), we get a formula for F(z) = Sum_{n >= 0} n! z^n as a sum with all positive coefficients of (almost) powers of the Catalan number generating function.
The exact formula is (5) of the Yiting Li article.
This article also gives a combinatorial proof of this formula (though it is not as simple as one might want). (End)

			a(2) = 0; nothing works. a(3) = 1; (201) works. a(4) = 2; (2301), (3012) work. a(5) = 13; (20413), (23401), (24013), (24103), (30412), (30421), (34012), (34021), (34102), (40123), (43012), (43021), (43102) work.

W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th Ed. Dover, p. 50.
M. Cerasoli, F. Eugeni and M. Protasi, Elementi di Matematica Discreta, Nicola Zanichelli Editore, Bologna 1988, Chapter 3, p. 78.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n).
Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta Math. 12, (1946). 113-124. See u_n.
E. Lucas, Théorie des nombres, Paris, 1891, pp. 491-495.
P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 1, p 256.
T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112. - N. J. A. Sloane, Feb 24 2011
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
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. - Vladimir Shevelev, Mar 22 2010
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.
J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 108-119.
J. H. van Lint, Combinatorial Theory Seminar, Eindhoven University of Technology, Springer Lecture Notes in Mathematics, Vol. 382, 1974. See page 10.

Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..100 from T. D. Noe)
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.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135.
Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the ménage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.
A. Cayley, On a problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 338-342.
A. Cayley, On a problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 338-342.
A. Cayley, On Mr Muir's discussion of Professor Tait's problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 388-391.
A. Cayley, On Mr Muir's discussion of Professor Tait's problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 388-391.
J. Dutka, On the Probleme des Menages, Mathem. Conversat. (2001) 277-287, reprinted from Math. Intell. 8 (1986) 18-25
A. de Gennaro, How many latin rectangles are there?, arXiv:0711.0527 [math.CO] (2007), see p. 2.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 372
Nick Hobson, Python program for this sequence.
Peter Kagey, Ranking and Unranking Restricted Permutations, arXiv:2210.17021 [math.CO], 2022.
Irving Kaplansky, Solution of the "Problème des ménages", Bull. Amer. Math. Soc. 49, (1943). 784-785.
Irving Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
S. M. Kerawala, Asymptotic solution of the "Probleme des menages, Bull. Calcutta Math. Soc., 39 (1947), 82-84. [Annotated scanned copy]
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 221.
D. E. Knuth, Comments on A000179, Nov 25 2018 - Nov 27 2018.
D. E. Knuth, Donald Knuth's 24th Annual Christmas Lecture: Dancing Links, Stanfordonline, Video published on YouTube, Dec 12, 2018.
A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen..., Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp.
Yiting Li, Ménage Numbers and Ménage Permutations, J. Int. Seq. 18 (2015) 15.6.8
E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.
T. Muir, On Professor Tait's problem of arrangement, Proceedings of the Royal Society of Edinburgh 9 (1878) 382-387.
T. Muir, On Professor Tait's problem of arrangement, Proceedings of the Royal Society of Edinburgh 9 (1878) 382-387.
Vladimir Shevelev and Peter J. C. Moses, The ménage problem with a known mathematician, arXiv:1101.5321 [math.CO], 2011, 2015.
Vladimir Shevelev and Peter J. C. Moses, Alice and Bob go to dinner: A variation on menage, INTEGERS, Vol. 16 (2016), #A72.
R. J. Stones, S. Lin, X. Liu and G. Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1.
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]
J. Touchard, Théorie des substitutions. Sur un problème de permutations, C. R. Acad. Sci. Paris 198 (1934), 631-633.
Eric Weisstein's World of Mathematics, Married Couples Problem.
Eric Weisstein's World of Mathematics, Rooks Problem.
Wikipedia, Menage problem.
M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.
D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Diagonal of A058087. Also a diagonal of A008305.
Cf. A000904, A059375, A102761, A000186, A094047, A067998, A033999, A258664, A258665, A258666, A258667, A258673, A259212, A213234, A000023.
A000179, A102761, and A335700 are all essentially the same sequence but with different conventions for the initial terms a(0) and a(1). - N. J. A. Sloane, Aug 06 2020

import Data.List (zipWith5)
a000179 n = a000179_list !! n
a000179_list = 1 : -1 : 0 : 1 : zipWith5
   (\v w x y z -> (x * y + (v + 2) * z - w) `div` v) [2..] (cycle [4,-4])
   (drop 4 a067998_list) (drop 3 a000179_list) (drop 2 a000179_list)
-- Reinhard Zumkeller, Aug 26 2013

A000179:= n ->add ((-1)^k*(2*n)*binomial(2*n-k,k)*(n-k)!/(2*n-k), k=0..n); # for n >= 1
U:= proc(n) local k; add( (2*n/(2*n-k))*binomial(2*n-k,k)*(n-k)!*(x-1)^k, k=0..n); end; W := proc(r,s) coeff( U(r),x,s ); end; A000179 := n->W(n,0); # valid for n >= 1

a[n_] := 2*n*Sum[(-1)^k*Binomial[2*n - k, k]*(n - k)!/(2*n - k), {k, 0, n}]; a[0] = 1; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Dec 05 2012, from 2nd formula *)

\\ 3 programs adapted to a(1) = -1 by Hugo Pfoertner, Aug 31 2020

{a(n) = my(A); if( n, A = vector(n,i,i-2); for(k=4, n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); A[n], 1)};/* Michael Somos, Jan 22 2008 */

a(n)=if(n>1, round(2*n*exp(-2)*besselk(n, 2)), 1-2*n) \\ Charles R Greathouse IV, Nov 03 2014

{a(n) = my(A); if( n, A = vector(n,i,i-2); for(k=5, n, A[k] = k * A[k-1] + 2 * A[k-2] + (4-k) * A[k-3] - A[k-4]); A[n], 1)} /* Michael Somos, May 02 2018 */

from math import comb, factorial
def A000179(n): return 1 if n == 0 else sum((-2*n if k & 1 else 2*n)*comb(m:=2*n-k,k)*factorial(n-k)//m for k in range(n+1)) # Chai Wah Wu, May 27 2022

a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4*(-1)^n)/(n-2) for n >= 3.
a(n) = A059375(n)/(2*n!) for n >= 2.
a(n) = Sum_{k=0..n} (-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k) for n >= 1. - Touchard (1934)
G.f.: ((1-x)/(1+x))*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 26 2007
a(2^k+2) == 0 (mod 2^k); for k >= 2, a(2^k) == 2(mod 2^k). - Vladimir Shevelev, Jan 14 2011
a(n) = round( 2*n*exp(-2)*BesselK(n,2) ) for n > 1. - Mark van Hoeij, Oct 25 2011
a(n) ~ (n/e)^n * sqrt(2*Pi*n)/e^2. - Charles R Greathouse IV, Jan 21 2016
0 = a(n)*(-a(n+2) +a(n+4)) +a(n+1)*(+a(n+1) +a(n+2) -3*a(n+3) -5*a(n+4) +a(n+5)) +a(n+2)*(+2*a(n+2) +3*a(n+3) -3*a(n+4)) +a(n+3)*(+2*a(n+3) +a(n+4) -a(n+5)) +a(n+4)*(+a(n+4)), for all n>1. If a(-2..1) = (0, -1, 2, -1) then also true for those values of n. - Michael Somos, Apr 29 2018
D-finite with recurrence: 0 = a(n) +n*a(n+1) -2*a(n+2) +(-n-4)*a(n+3) +a(n+4), for all n in Z where a(n) = a(-n) for all n in Z and a(0) = 2, a(1) = -1. - Michael Somos, May 02 2018
a(n) = Sum_{k=0..n} A213234(n,k) * A000023(n-2*k) = Sum_{k=0..n} (-1)^k * n/(n-k) * binomial(n-k, k) * (n-2*k)! Sum_{j=0..n-2*k} (-2)^j/j! for n >= 1. [Wyman and Moser (1958)]. - William P. Orrick, Jun 25 2020
a(k+4*p) - 2*a(k+2*p) + a(k) is divisible by p, for any k > 0 and any prime p. - Mark van Hoeij, Jan 11 2022

More terms from James Sellers, May 02 2000
Additional comments from David W. Wilson, Feb 18 2003
a(1) changed to -1 at the suggestion of Don Knuth. - N. J. A. Sloane, Nov 26 2018

A059375 Number of seating arrangements for the ménage problem.

Original entry on oeis.org

1, 0, 0, 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, 3191834419200, 390445460697600, 56729732529254400, 9659308746908620800, 1905270127543015833600, 431026303509734220288000, 110865322076320374571008000, 32172949121885378686623744000

Offset: 0

N. J. A. Sloane, Jan 28 2001

nonn

The "probleme des menages" asks for the number of gender-alternating seating arrangements for n couples around a circular table with the condition that no two spouses are seated adjacently. - Paul C. Kainen and Michael Somos, Mar 11 2011

			a(3) = 12 because there is a unique seating arrangement up to circular and clockwise / counterclockwise symmetry. - _Paul C. Kainen_ and _Michael Somos_, Mar 11 2011

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 184, mu*(n).
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 32. equation (2.3).

Seiichi Manyama, Table of n, a(n) for n = 0..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
V. Baltic, On the number of certain types of strongly restricted permutations, Appl. An. Disc. Math. 4 (2010), 119-135. doi:10.2298/AADM1000008B
K. P. Bogart and P. G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
A. Guterman, Pólya permanent problem: 100 years after, 2014.
Vladimir Shevelev, Peter J. C. Moses, The ménage problem with a known mathematician, arXiv:1101.5321 [math.CO], 2011, 2015.
Wikipedia, Menage Problem

Cf. A000179, A258338, A258664, A258665, A258666, A258667, A258673, A259212.

a[0] = 1; a[1] = 0; a[n_] := 4n n! Sum[(-1)^k Binomial[2n-k, k] (n-k)! / (2n-k), {k, 0, n}]; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Jun 19 2017, from 1st formula *)

{a(n) = local(A); if( n<3, n==0, A = vector(n); A[3] = 1; for(k=4, n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); 2 * n! * A[n])} /* Michael Somos, Mar 11 2011 */

a(n) = A000179(n) * 2 * n!.

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

A174556 Number of 3 X n Latin rectangles whose second row contains two cycles.

Original entry on oeis.org

12, 240, 10480, 535080, 34634544

Offset: 4

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.

Cf. A000186, A094047.

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.

A137886 Number of (directed) Hamiltonian paths in the n-crown graph.

Original entry on oeis.org

12, 144, 3840, 138240, 6804000, 436504320, 35417088000, 3546005299200, 429451518988800, 61883150757120000, 10463789706751180800, 2051763183437532364800, 461802751261297205760000, 118254166096501129863168000

Offset: 3

Eric W. Weisstein, Feb 20 2008

nonn

The reference to A094047 arises in the formula because that sequence is also the number of directed Hamiltonian cycles in the n-crown graph. (Each cycle can be broken in 2n ways to give a path.) - Andrew Howroyd, Feb 21 2016

Also, the number of ways of seating n married couples at 2*n chairs arranged side-by-side in a straight line, men and women in alternate positions, so that no husband is next to his wife. - Andrew Howroyd, Sep 19 2017

Seiichi Manyama, Table of n, a(n) for n = 3..253 (terms 3..50 from Andrew Howroyd)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path

Cf. A000271, A059375, A094047, A259212, A270174.

Table[2 n! Sum[(-1)^(n - k) k! Binomial[n + k, 2 k], {k, 0, n}], {n, 3, 20}] (* Eric W. Weisstein, Sep 20 2017 *)
Table[2 (-1)^n n! HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 3, 20}] (* Eric W. Weisstein, Sep 20 2017 *)

/* needs the routine nhp() from the Alekseyev link */
{ A137886(n) = nhp( matrix(2*n,2*n,i,j, if(min(i,j)<=n && max(i,j)>n && abs(j-i)!=n, 1, 0)) ) }

For n>3, a(n) = 2*n*A094047(n) + n*a(n-1) = A059375(n) + n*a(n-1). - Andrew Howroyd, Feb 21 2016
a(n) ~ 4*Pi*n^(2*n+1) / exp(2*n+2). - Vaclav Kotesovec, Feb 25 2016
a(n) = (n-1)*n*a(n-1) + (n-1)^2*n*a(n-2) + (n-2)*(n-1)*n*a(n-3). - Vaclav Kotesovec, Feb 25 2016
a(n) = 2*n! * A000271(n). - Andrew Howroyd, Sep 19 2017

More terms from Max Alekseyev, Feb 13 2009
a(14) from Eric W. Weisstein, Jan 15 2014
a(15)-a(16) from Andrew Howroyd, Feb 21 2016

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

A174560 Number of 3 X n Latin rectangles whose second row has cycles of even length only.

Original entry on oeis.org

0, 24, 0, 18000, 0, 52254720

Offset: 3

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.

Cf. A000186, A094047, A174556.

A174561 Number of 3 X n Latin rectangles whose second row contains two cycles with the same order of its elements, e.g., the cycle (x_2, x_3, ..., x_k, x_1) with x_1 < x_2 < ... < x_k.

Original entry on oeis.org

12, 120, 2020, 32410, 563948

Offset: 4

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.

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

A267060 a(n) = number of different ways to seat a set of n married male-female couples at a round table so that men and women alternate and every man is separated by at least d = 2 men from his wife.

Original entry on oeis.org

0, 0, 0, 0, 24, 240, 22320, 1330560, 112210560, 11183235840, 1340192044800, 189443216793600, 31267307962598400, 5964702729085900800, 1303453560329957836800, 323680816052170536960000, 90679832709074132299776000, 28473630606612014817337344000

Offset: 1

Feng Jishe, Jan 09 2016

nonn

We assume that the chairs are uniform and indistinguishable.
First we arrange the females in alternating seats by circular permutation, there are (n-1)! ways. Secondly, we evaluate the number F_{n}, ways of arranging males in the remaining seats as mentioned in the definition above.
By the principle of inclusion-exclusion and theory of rook polynomial Vl, we obtain that a_{n} = (n-1)!*F_{n}, F_{n} = sum(-1)^{k}*r_{k}(B3)*(n-k)! where r_{k}(B3) is the number of ways of putting k non-taking rooks on positions 1's of B3, and the rook polynomials are R_{B3}(x) = sum r_{k}(B3)*x^{k}.
Also F_{n} = per(B3), here per(B3) denotes the permanent of matrix (board) B3, but it is very difficult problem to evaluate the value, per(B3).

			For d=1, the sequence a_{n} is the classical menage sequence A094047.
For d=2 (the current sequence), the F(n)s are 0, 0, 0, 0, 1, 2, 31, 264, 2783, 30818, 369321, ... which is A004307(n) then the sequence a_{n} is 0, 0, 0, 0, 24, 240, 22320, 1330560, 112210560, 11183235840, 1340192044800,...
For d=3, the F(n)s are 0, 0, 0, 0, 0, 0, 1, 2, 78, 888, 13909, ... which is A184965, and a(n) = (n-1)!*A184965(n).

G. Polya, Aufgabe 424, Arch. Math. Phys. (3) 20 (1913) 271.
John Riordan. The enumeration of permutations with three-ply staircase restrictions.

Alois P. Heinz, Table of n, a(n) for n = 1..253
E. Rodney Canfield and Nicholas C. Wormald, Menage numbers, bijections and P-recursiveness, Discrete Mathematics, 63 (2--3)(1987): 117--129.
Bruno Codenotti, Giovanni Resta, On the permanent of certain circulant matrices, in Algebraic Combinatorics and Computer Science. 513-532. 2001.
Feng Jishe, Illustration
Yiting Li, Ménage Numbers and Ménage Permutations, Journal of Integer Sequences, Vol. 18 (2015), #15.6.8.
M. Marcus and H. Mint, On the relation between the determinant and the permanent, Illinois J. Math. 5 (1961): 376-381.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
Giovanni Sburlati, On the values of permanents of (0,1) circulant matrices with three ones per row, Linear Algebra and its Applications. 408 (2005) 284--297.
Vladimir Shevelev, Peter J.C. Moses, The menage problem with a fixed couple, arXiv:1101.5321 [math.CO], 2011-2015.
L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979): 189-201.
Vijay V. Vazirani, Milhalis Yannakakis, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Discrete Applied Mathematics, 25(1989): 179-190.
M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.

Cf. A004307, A094047, A184965.

b[n_, n0_] := Permanent[Table[If[(0 <= j - i && j - i < n - n0) || j - i < -n0, 1, 0], {i, 1, n}, {j, 1, n}]];
A004307[n_] := b[n, 4];
a[n_] := (n - 1)!*A004307[n];
Array[a, 18] (* Jean-François Alcover, Oct 08 2017 *)

a(n) = (n-1)! * A004307(n). - Andrew Howroyd, Sep 19 2017

a(12)-a(18) from Andrew Howroyd, Sep 19 2017

cp's OEIS Frontend

A260321 Erroneous version of A094047.

Views

Author

Keywords

Links

A000179 Ménage numbers: a(0) = 1, a(1) = -1, and for n >= 2, a(n) = number of permutations s of [0, ..., n-1] such that s(i) != i and s(i) != i+1 (mod n) for all i.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A059375 Number of seating arrangements for the ménage problem.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A174556 Number of 3 X n Latin rectangles whose second row contains two cycles.

Views

Author

Keywords

Links

Crossrefs

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

A137886 Number of (directed) Hamiltonian paths in the n-crown graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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