

A267060


a(n) = number of different ways to seat a set of n married malefemale 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.


2



0, 0, 0, 0, 24, 240, 22320, 1330560, 112210560, 11183235840, 1340192044800, 189443216793600, 31267307962598400, 5964702729085900800, 1303453560329957836800, 323680816052170536960000, 90679832709074132299776000, 28473630606612014817337344000
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 (n1)! 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 inclusionexclusion and theory of rook polynomial Vl, we obtain that a_{n} = (n1)!*F_{n}, F_{n} = sum(1)^{k}*r_{k}(B3)*(nk)! where r_{k}(B3) is the number of ways of putting k nontaking 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 threeply 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 Precursiveness, Discrete Mathematics, 63 (23)(1987): 117129.
Bruno Codenotti, Giovanni Resta, On the permanent of certain circulant matrices, in Algebraic Combinatorics and Computer Science. 513532. 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): 376381.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291321.
Giovanni Sburlati, On the values of permanents of (0,1) circulant matrices with three ones per row, Linear Algebra and its Applications. 408 (2005) 284297.
Vladimir Shevelev, Peter J.C. Moses, The menage problem with a fixed couple, arXiv:1101.5321 [math.CO], 20112015.
L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979): 189201.
Vijay V. Vazirani, Milhalis Yannakakis, Pfaffian orientations, 01 permanents, and even cycles in directed graphs, Discrete Applied Mathematics, 25(1989): 179190.
M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468480.


FORMULA

a(n) = (n1)! * 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) = (n1)!*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] (* JeanFranç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



