cp's OEIS Frontend

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.

%I A267060 #55 Oct 08 2017 08:52:51
%S A267060 0,0,0,0,24,240,22320,1330560,112210560,11183235840,1340192044800,
%T A267060 189443216793600,31267307962598400,5964702729085900800,
%U A267060 1303453560329957836800,323680816052170536960000,90679832709074132299776000,28473630606612014817337344000
%N 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.
%C A267060 We assume that the chairs are uniform and indistinguishable.
%C A267060 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 A267060 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 A267060 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 A267060 G. Polya, Aufgabe 424, Arch. Math. Phys. (3) 20 (1913) 271.
%D A267060 John Riordan. The enumeration of permutations with three-ply staircase restrictions.
%H A267060 Alois P. Heinz, <a href="/A267060/b267060.txt">Table of n, a(n) for n = 1..253</a>
%H A267060 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 A267060 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 A267060 Feng Jishe, <a href="/A267060/a267060_3.jpg">Illustration</a>
%H A267060 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 A267060 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 A267060 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 A267060 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 A267060 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 A267060 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 A267060 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 A267060 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 A267060 a(n) = (n-1)! * A004307(n). - _Andrew Howroyd_, Sep 19 2017
%e A267060 For d=1, the sequence a_{n} is the classical menage sequence A094047.
%e A267060 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 A267060 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 A267060 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 A267060 A004307[n_] := b[n, 4];
%t A267060 a[n_] := (n - 1)!*A004307[n];
%t A267060 Array[a, 18] (* _Jean-François Alcover_, Oct 08 2017 *)
%Y A267060 Cf. A004307, A094047, A184965.
%K A267060 nonn
%O A267060 1,5
%A A267060 _Feng Jishe_, Jan 09 2016
%E A267060 a(12)-a(18) from _Andrew Howroyd_, Sep 19 2017