Intereting Posts

Evaluate the integral: $\int_{0}^{1} \frac{\ln(x+1)}{x^2+1} \mathrm dx$
Weighted Poincare Inequality
Smallest example of a group that is not isomorphic to a cyclic group, a direct product of cyclic groups or a semi direct product of cyclic groups.
Isomorphic quotient groups $\frac{G}{H} \cong \frac{G}{K}$ imply $H \cong K$?
Uniform convexity of equivalent intersection norm
approximating a maximum function by a differentiable function
Definition of opposite category
How to show the Symmetric Group $S_4$ has no elements of order $6$.
Sum of squares of in-degrees vs out-degrees in a Tournament Graph
What restricts the number of cohomologies?
Are integers mod n a unique factorization domain?
pseudo-inverse to the operation of turning a metric space into a topological space
$\alpha$-derivative (concept)
When can you treat a limit like an equation?
Summation of a function 2

I’m stuck in the following math challenge. The situation is as follows:

When six couples organize some dinners, they take place at a rectangular table with six places on each sides. Since one should never sit in front of his or her partner, these places are numbered.

What is the number of dinners that can be organized if the 12 people should never sit on the same place as during a previous dinner?

I closely examined this problem for several times and I think it’s a variation with repitition, but I got stuck with the conditions described above.

- Combinations of 6 students among 20, at least one male
- $\sum_{k=0}^n (-1)^k \binom{n}{k}^2$ and $\sum_{k=0}^n k \binom{n}{k}^2$
- Calculate different sequence of scores in a Volleyball match
- Combinations problem involving a standard pack of $52$ playing cards and a $4$ sided die: Part 1
- Number of subsets of size $k$ whose pairwise intersection is of given size j
- Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

- How to find all possible combinations of a set of options?
- Minimum number of points chosen from an $N$ by $N$ grid to guarantee a rectangle?
- Prove the following relation:
- sum of all the numbers that can be formed using the digits 2,3,3,4,4,4..
- Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$
- Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015
- How many possibilities to arrange a rope of length $N$ between two points
- Why is it that if I count years from 2011 to 2014 as intervals I get 3 years, but if I count each year separately I get 4 years?
- In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
- Problem with concepts of circular permutation.

You can do this by inclusion-exclusion. It is just like the famous derangements problem, though the formula is more complicated, and there appears to be no direct relation between the outcomes.

For $0\leq k\leq n$ let us count the number of ways a specific subset of $k$ couples will be opposite each other (not caring about whether any other couples are). The women of those $k$ couples can choose their places in $2n(2n-2)\ldots(2n-2k+2)=2^kn^{\underline k}=2^k\binom nkk!$ ways, their partner then have no choice; there remain $(2n-2k)!$ permutations for the remaining $(n-k)$ people. Now one must also take into account that the subset of $k$ couples can be chosen in $\binom nk$ ways. Then inclusion-exclusion says we must sum all this with a sign $(-1)^k$ attached

$$

f(n)=\sum_{k=0}^n(-1)^k\binom nk2^k\binom nkk!(2n-2k)!

$$

This allows us to compute $f(6)=278\,323\,200$ rapidly.

The formula can be simplified. One can observe that $2^nn!$ divides $f(n)$, which is related to the fact that the centraliser in the group $S_{2n}$ of the involution that interchanges each pair of opposite places acts simply on the set of solutions. This factor $2^nn!$ divides each term of our sum, which we can make evident by extracting from $(2n-2k)!$ a factor $2^{n-k}(n-k)!$ (the product of the even factors) leaving a quotient $q(n)=\prod_{i=1}^n(2i-1)$ (sometimes written $(2n-1)!\!!$, but I won’t); the products $2^k2^{n-k}=2^n$ and $\binom nkk!(n-k)!=n!$ can then be extracted from the sum, giving

$$

f(n)=2^nn!\sum_{k=0}^n(-1)^k\binom nkq(n-k).

$$

The summation can now be recognised as the inverse binomial transform of the sequence $(q(n))_{n\in\Bbb N}=(1,1,3,15,105,495,10395, 135135, \ldots)$, which can be computed by repeatedly applying the forward difference operator to the sequence

$$

\matrix{

1&&1&&3&&15&&105&&945&&10395\\

&0&&2&&12&&90&&840&&9450&\\

&&2&&10&&78&&750&&8610&\\

&&& 8 && 68 &&672 &&7860\\

&&&&60&&604&&7188\\

&&&&&544&&6584\\

&&&&&&6040

}

$$

from which one can read off that $f(6)=2^6\times6!\times6040$, which is indeed the number I reported before. The sequence $\left(\frac{f(n)}{2^nn!}\right)_{n\in\Bbb N}=(1, 0, 2, 8, 60, 544, 6040, 79008,\ldots)$ is A053871.

Note that the sequence of derangement numbers (subfactorials) is similarly the inverse binomial transform of the sequence $(n!)_{n\in\Bbb N}$ of factorials.

Seat the 6 women on one side. This can be done in $6!$ ways. Now seat the men, this can be done in $D_6$ ways (here $D_n$ is the number of derangements). If you also consider the possibility of seating women at random on both sides of the table, another factor of $2^6$. In all:

$$6! \cdot D_6 \cdot 2^6$$

For simplicity, I shall assume man-woman couples, and discuss under two conditions:

(a) men-women must sit opposite to each other.

(b) men-women need not (but could) sit opposite to each other.

The only stipulation is that **couples** can’t sit opposite to each other.

Case (a) has been dealt with by vonbrand and I agree with the answer. It is case (b) that has been proving a bother.

There are 6 pairs of seats that are opposite each other. Suppose $k$ of them seat couples.

The seats for the $k$ couples can be chosen in $\binom6{k}$ ways,

and the couples can be placed in them in $_6P_k$ ways.

The remaining $(12-k)$ can be placed in $\frac{(12-k)!}{2^{(n-k)}}$ ways

Applying inclusion-exclusion, ways with no couples sitting opposite

$ = 12!/2^6$ – ways with at least one couple opposite + ways with at least 2 couples opposite – …

$$= \sum_{k=0}^6(-1)^k\cdot\binom{6}{k}\cdot \;_6P_k\frac{(12-k)!}{2^{(6-k)}} = 4,348,800$$

I have not permuted objects between the two sides. If you want to do that, multiply by $2^6$

I guess the questioner might have had the simpler problem in mind, but this one was more fun !

THIS ANSWER IS WRONG PER REBECCA’S COMMENT BELOW. Leaving it up for legacy reasons only.

NOTE: This answer assumes men and women must sit across from each other (just as long as they don’t sit across from their partners). If women can sit across from other women, this answer does not apply.

You can seat the 6 women in 12*11*10*9*8*7 or 665,280 ways.

In theory, the men can fill the remaining 6 chairs in 6! or 720 ways, but many of these ways would put a man across from his wife. Only 265 of these ways are “derangements” where no man sits across from his wife.

Thus, the total number of ways is 665,280*265 = 176,299,200 ways.

I interpreted “if the 12 people should never sit on the same place as during a previous dinner” as meaning: it’s ok if 10 people sit in the same place as a previous dinner, provided that all 12 people don’t occupy the exact same chairs as they did at a previous dinner.

The other interpretation is that one person may never occupy the same chair twice, in which case there could be at most 12 dinners.

**ANSWER DISCARDED, BEING RETAINED ONLY FOR REFERENCE**

*There is no rule forbidding any arrangement other than couples sitting opposite each other.*

Consider a row of 12 seats. Ways in which no couples sit **together** can be found using inclusion-exclusion, treating couples sitting together as “flippable **individuals**“, (i.e. single objects), hence

$12! – \binom61\cdot2^1\cdot11! + \binom62\cdot2^2\cdot10! – …..$

$$= \sum_{j=0}^6(-1)^j\cdot\binom{6}{j}\cdot 2^j\cdot(12-j)! = 168422400$$

Now let persons in odd numbered chairs remain,

and shift the rest opposite so that $1$ and $2,\;\;3$ and $4$ …. are opposite each other.

**Further explanation:**

It may be easier to understand, if we imagine the two numbered rows

$01-02-03-04-05-06$

$07-08-09-10-11-12$

to be interleaved into one row

$01-07-02-08-03-09-04-10-05-11-06-12$,

and simply count how many ways there are to seat the people so that no couple is together.

The answer obtained for such a count has been confirmed at OEIS

- PDF of $f(x)=1/\sin(x)$?
- For all $n>2$ there exists a prime number between $n$ and $ n!$
- Prove that if $\sum_{n=1}^\infty a_{2n}$ and $\sum_{n=1}^\infty a_{2n-1}$ converge then $\sum_{n=1}^\infty a_n$ converges.
- $\int_0^\infty ne^{-nx}\sin\left(\frac1{x}\right)\;dx\to ?$ as $n\to\infty$
- $\int_0^L \frac{\cos(2 \pi x /\ell)}{t^2+x^2} \,dx$
- Can a smooth function on the reals form a non-commutative semigroup?
- Let $(x_n)\downarrow 0$ and $\sum x_n\to s$. Then $(n\cdot x_n)\to 0$
- General Solution of a Differential Equation using Green's Function
- Bipartite graph. average degree. Euler circuit.
- Maximum a Posteriori (MAP) Estimator of Exponential Random Variable with Uniform Prior
- How to effectively and efficiently learn mathematics
- Difference between functional and function.
- Are intermediate rings of finitely generated ring extensions also finitely generated?
- writing $pq$ as a sum of squares for primes $p,q$
- How to show that $(W^\bot)^\bot=W$ (in a finite dimensional vector space)