A group of 2n individuals consisting of n couples, are randomly arranged at a round table. You are required to find an upper bound for the probability that none of the couples are seated next to each other.
Solution:
This is a combinatorial problem. Let's denote the total number of ways to arrange 2n individuals around a round table as T, and the number of ways to arrange them such that no couples are seated next to each other as S. The probability that none of the couples are seated next to each other is then given by $P = \displaystyle\frac{S}{T}.$
-
Total arrangements (T): Since the table is round, we can fix one person and arrange the remaining 2n-1 people. This can be done in (2n-1)! ways.
-
Arrangements with no couples together (S): This is a bit trickier. We can think of each couple as a single entity first. So we have n entities to arrange, which can be done in (n-1)! ways (again, because the table is round). Now, within each couple, we have 2 people that can be arranged in 2! ways. Since we have n couples, the total number of arrangements is $(n-1)! \times (2!)^n$.
So, the probability $P =\displaystyle\frac{S}{T} = \frac{[(n-1)! * (2!)^n]}{(2n-1)!.}$
This is the exact probability, but author asked for an upper bound. An upper bound for this probability can be obtained by using the fact that $(n-1)! \leq n!$ and $(2n-1)! \geq (n!)^2$ for $n \geq 1.$ So, we have:
$P \leq \displaystyle\frac{[(n!)\times(2!)^n]}{(n!)^2} =\displaystyle\frac{(2^n)}{n!}.$
This is an upper bound for the probability that none of the couples are seated next to each other. Please note that this is a very loose upper bound, and the actual probability will be much less than this.
Is this answer correct?
Assuming in the above exercise, that n is large, how can we approximate the probability that exactly k of the couples are seated next to each other?
Inclusion-exclusion theorem is used in the following case:
Consider n independent trials in which each trial results in one of the outcomes $1,\dots, k$ with respective probabilities $p_i,\dots, p_k.$ Suppose we are interested in the probability that each of the k outcomes occurs at least once in the n trials. If we let $A_i$ denote the event that outcome i does not occur in any of the trials, then the desired probability is $1 -P((\bigcup_{i=1}^k A_i)$ and it can be obtained by using the inclusion-exclusion theorem:
$$p(\bigcup_{i=1}^k A_i) = \displaystyle\sum_i P(A_i) -\displaystyle\sum_i\sum_{j<i} P(A_i,A_j) + \dots + (-1)^{k+1}P(A_i,\dots,A_k) $$
where
$$P(A_i) = (1-p_i)^n$$
$$P(A_i,A_j)= (1- p_i -p_j)^n j < i$$
$$P(A_i,A_j,A_r) =(1-p_i -p_j -p_r)^n , r<j <i $$
and so on. The difficulty with this approach, however, is that its computation requires the calculation of $2^k -1$ terms.
Now, in our question, I don't think we should use this inclusion-exclusion theorem.
Best Answer
What you have computed as $S= (n-1)!(2!)^n$ represents # of arrangements with couples just considered apart pair by pair without regard to their relative positions when all are seated, which means some pairs may be seated together
For $k$ couples together, $\;\;S_k=\binom{n}{k}2^k(2n−1−k)!$
[ Couples to be together are chosen, glued together and flippable. The rest are free to be permuted in the remaining part on an unnumbered circle ]
And the probability of no couples together can be computed using inclusion-exclusion as
$$Pr = \frac{1}{(2n-1)!}\;\sum_{0}^n \left[(-1)^k\cdot\binom{n}{k}\cdot 2^k\cdot (2n-1-k)!\right]$$
PS
This is the upper bound for a given $n$, because it is the probability that all couples are apart, and you can't have a probability higher than that
PPS
If instead, you want to know the highest value Pr might reach as you increase $n$, I suspect it might be $e^{-1}$, as gleaned from the table below:
$n\quad\quad\; Pr$
$04\quad\quad 0.2954...$
$10\quad\quad 0.3395...$
$20\quad\quad 0.3539...$
$40\quad\quad 0.3609...$
$99\quad\quad 0.3651...$ with $e^{-1} =0.3678...$