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,5

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

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.

Formula

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

Example

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

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

Crossrefs

Cf. A004307, A094047, A184965.

Sequence in context: A151720 A052652 A052732 * A086603 A304835 A281076

Adjacent sequences: A267057 A267058 A267059 * A267061 A267062 A267063

Keyword

nonn

Author

Feng Jishe, Jan 09 2016

Extensions

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

Status

approved