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
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
KEYWORD
nonn
AUTHOR
Feng Jishe, Jan 09 2016
EXTENSIONS
a(12)-a(18) from Andrew Howroyd, Sep 19 2017
STATUS
approved