A094314 Triangle read by rows: T(n,k) = number of ways of seating n couples around a circular table so that exactly k married couples are adjacent (0 <= k <= n).

1, 0, 1, 0, 0, 2, 1, 0, 3, 2, 2, 8, 4, 8, 2, 13, 30, 40, 20, 15, 2, 80, 192, 210, 152, 60, 24, 2, 579, 1344, 1477, 994, 469, 140, 35, 2, 4738, 10800, 11672, 7888, 3660, 1232, 280, 48, 2, 43387, 97434, 104256, 70152, 32958, 11268, 2856, 504, 63, 2, 439792, 976000, 1036050, 695760, 328920, 115056, 30300, 6000, 840, 80, 2

Offset: 0

Author

N. J. A. Sloane, based on a suggestion from Anthony C Robin, Jun 02 2004

Keywords

• nonn
• tabl

Comments

The men and women alternate.

Examples

			Triangle begins:
     1;
     0,     1;
     0,     0,     2;
     1,     0,     3,    2;
     2,     8,     4,    8,    2;
    13,    30,    40,   20,   15,    2;
    80,   192,   210,  152,   60,   24,   2;
   579,  1344,  1477,  994,  469,  140,  35,  2;
  4738, 10800, 11672, 7888, 3660, 1232, 280, 48, 2;
  ...
		

References

• I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. See Table 1.
• Tolman, L. Kirk, "Extensions of derangements", Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Humboldt State University, Arcata, California, September 5-7, 1979. Vol. 26. Utilitas Mathematica Pub., 1980. See Table I.

Links

• Alois P. Heinz, Rows n = 0..140, flattened
• I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
• Anthony C. Robin, 90.72 Circular Wife Swapping, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.
• L. Takacs, On the probleme des menages, Discr. Math. 36 (3) (1981) 289-297, Table 1.

Crossrefs

Essentially a mirror image of A058087, which has much more information.

Diagonals give A000179, A000425, A000033, A000159, A000181, etc.

Programs

Mathematica

T[n_, k_]:= If[n<2, (1+(-1)^(n-k))/2, Sum[(-1)^j*(2*n*(n-k-j)!/(2*n-k-j))* Binomial[k+j, k]*Binomial[2*n-k-j, k+j], {j, 0, n-k}]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, May 15 2021 *)

Sage

def A094314(n,k): return (1+(-1)^(n+k))/2 if (n<2) else sum( (-1)^j*(2*n*factorial(n-k-j)/(2*n-k-j))*binomial(k+j, k)*binomial(2*n-k-j, k+j) for j in (0..n-k) )
flatten([[A094314(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 15 2021

Formula

Sum_{k=0..n} T(n,k) = n!.

T(n, k) = Sum_{j=0..n-k} (-1)^j*(2*n*(n-k-j)!/(2*n-k-j))*binomial(k+j, k) * binomial(2*n-k-j, k+j) for n > 1, T(0, 0) = T(1, 1) = 1, and T(1, 0) = 0. - G. C. Greubel, May 15 2021