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.

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

Offset: 1

Author

Feng Jishe, Jan 09 2016

Keywords

• nonn

Comments

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

Examples

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

References

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

Links

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

Crossrefs

Cf. A004307, A094047, A184965.

Programs

Mathematica

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

Formula

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

Extensions

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