|
%I #55 Oct 08 2017 08:52:51
%S 0,0,0,0,24,240,22320,1330560,112210560,11183235840,1340192044800,
%T 189443216793600,31267307962598400,5964702729085900800,
%U 1303453560329957836800,323680816052170536960000,90679832709074132299776000,28473630606612014817337344000
%N 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.
%C We assume that the chairs are uniform and indistinguishable.
%C 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.
%C 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}.
%C 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).
%D G. Polya, Aufgabe 424, Arch. Math. Phys. (3) 20 (1913) 271.
%D John Riordan. The enumeration of permutations with three-ply staircase restrictions.
%H Alois P. Heinz, <a href="/A267060/b267060.txt">Table of n, a(n) for n = 1..253</a>
%H E. Rodney Canfield and Nicholas C. Wormald, <a href="http://dx.doi.org/10.1016/0012-365X(87)90002-1">Menage numbers, bijections and P-recursiveness</a>, Discrete Mathematics, 63 (2--3)(1987): 117--129.
%H Bruno Codenotti, Giovanni Resta, <a href="http://dx.doi.org/10.1007/978-88-470-2107-5_22">On the permanent of certain circulant matrices</a>, in Algebraic Combinatorics and Computer Science. 513-532. 2001.
%H Feng Jishe, <a href="/A267060/a267060_3.jpg">Illustration</a>
%H Yiting Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Li2/li51.html">Ménage Numbers and Ménage Permutations</a>, Journal of Integer Sequences, Vol. 18 (2015), #15.6.8.
%H M. Marcus and H. Mint, <a href="http://projecteuclid.org/euclid.ijm/1255630882">On the relation between the determinant and the permanent</a>, Illinois J. Math. 5 (1961): 376-381.
%H N. Metropolis, M. L. Stein, P. R. Stein, <a href="http://dx.doi.org/10.1016/S0021-9800(69)80058-X">Permanents of cyclic (0,1) matrices</a>, J. Combin. Theory, 7 (1969), 291-321.
%H Giovanni Sburlati, <a href="http://dx.doi.org/10.1016/j.laa.2005.06.007">On the values of permanents of (0,1) circulant matrices with three ones per row</a>, Linear Algebra and its Applications. 408 (2005) 284--297.
%H Vladimir Shevelev, Peter J.C. Moses, <a href="http://arxiv.org/abs/1101.5321">The menage problem with a fixed couple</a>, arXiv:1101.5321 [math.CO], 2011-2015.
%H L. G. Valiant, <a href="http://dx.doi.org/10.1016/0304-3975(79)90044-6">The complexity of computing the permanent</a>, Theoret. Comput. Sci. 8 (1979): 189-201.
%H Vijay V. Vazirani, Milhalis Yannakakis, <a href="http://dx.doi.org/10.1016/0166-218X(89)90053-X">Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs</a>, Discrete Applied Mathematics, 25(1989): 179-190.
%H M. Wyman and L. Moser, <a href="http://dx.doi.org/10.4153/CJM-1958-045-6">On the problème des ménages</a>, Canad. J. Math., 10 (1958), 468-480.
%F a(n) = (n-1)! * A004307(n). - _Andrew Howroyd_, Sep 19 2017
%e For d=1, the sequence a_{n} is the classical menage sequence A094047.
%e 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,...
%e 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).
%t b[n_, n0_] := Permanent[Table[If[(0 <= j - i && j - i < n - n0) || j - i < -n0, 1, 0], {i, 1, n}, {j, 1, n}]];
%t A004307[n_] := b[n, 4];
%t a[n_] := (n - 1)!*A004307[n];
%t Array[a, 18] (* _Jean-François Alcover_, Oct 08 2017 *)
%Y Cf. A004307, A094047, A184965.
%K nonn
%O 1,5
%A _Feng Jishe_, Jan 09 2016
%E a(12)-a(18) from _Andrew Howroyd_, Sep 19 2017
|
