ML Interview Q Series: Solving Round Table Seating: Probability of No Adjacent Couples via Inclusion-Exclusion.
Browse all the Probability Interview Questions here.
Three couples attend a dinner. Each of the six people chooses randomly a seat at a round table. What is the probability that no couple sits together?
Short Compact solution
Consider labeling the seats as 1, 2, …, 6. There are 6! total ways to seat six people. Let Ai be the event that couple i sits together (i = 1, 2, 3). The desired probability is 1 - P(A1 ∪ A2 ∪ A3).
We compute:
P(A1) = 6 × 2! × 4! / 6!.
By symmetry, P(A2) and P(A3) are the same.
P(A1 A2) = 6 × 3 × 2! × 2! × 2! / 6!.
Similarly for P(A1 A3) and P(A2 A3).
P(A1 A2 A3) = 6 × 2 × 1 × 2! × 2! × 2! / 6!.
Using inclusion-exclusion gives P(A1 ∪ A2 ∪ A3) = 11/15. Therefore, the probability that no couple sits together is 1 - 11/15 = 4/15.
Comprehensive Explanation
Overview of the Problem
We have three couples, making six individuals total. They are to be seated around a round table with six labeled seats (labeled 1 through 6). We want the probability that none of the couples end up in adjacent seats. The total number of ways to seat six distinct people in six labeled seats is 6!.
Defining Events
For each couple i (where i = 1, 2, 3), define event Ai as:
Ai: “Couple i sits side-by-side.”
We aim to find the probability of the complement of the union of these events, namely the probability that none of the couples sit side-by-side:
Inclusion-Exclusion Principle
To handle the union A1 ∪ A2 ∪ A3, we apply the inclusion-exclusion formula:
$$ P(A_1 \cup A_2 \cup A_3)
= P(A_1) + P(A_2) + P(A_3)
[,P(A_1 \cap A_2) + P(A_1 \cap A_3) + P(A_2 \cap A_3),]
P(A_1 \cap A_2 \cap A_3) $$
We will compute each of these probabilities in turn, dividing by the total number of seatings, which is 6!.
Probability that a Specific Couple Sits Together
Take couple 1 as an example. We want P(A1):
Pick the seat of one member of couple 1. Since seats are labeled, there are 6 possibilities for which seat that person takes.
The other member of couple 1 must occupy either of the two seats adjacent to that seat, giving 2 possible choices.
The remaining 4 people can occupy the remaining 4 seats in 4! ways.
Hence the number of favorable permutations for couple 1 to sit together is 6 × 2 × 4!, and dividing by 6! gives the probability:
P(A1) = (6 × 2 × 4!) / 6!.
By symmetry, P(A2) and P(A3) have the same value.
Probability that Two Specific Couples Sit Together
Consider P(A1 ∩ A2): the probability that both couple 1 and couple 2 sit together. To count:
Suppose we place couple 1 first. We pick a seat for one member of couple 1 (6 ways). The second member of couple 1 can be seated in 2 adjacent seats (2 ways).
Next, couple 2 also must sit side-by-side. Depending on the arrangement of couple 1, there are fewer seats left, but effectively we can break it down systematically. The short solution snippet gives 6 × 3 × 2! × 2! × 2! as the count of favorable seatings (an approach is to consider each partial arrangement carefully and count how couple 2 can still sit together).
We then place the remaining two individuals in the remaining seats in 2! ways.
Dividing the favorable count by 6! yields P(A1 ∩ A2). By symmetry, the same pattern applies to P(A1 ∩ A3) and P(A2 ∩ A3).
Probability that All Three Couples Sit Together
For A1 ∩ A2 ∩ A3, each couple must occupy two adjacent seats. The exact count (as the short solution snippet notes) is 6 × 2 × 1 × 2! × 2! × 2!, because the first couple can pick seats in 6 × 2 ways, the next couple might then have a certain forced arrangement, etc. Divide by 6! to get P(A1 ∩ A2 ∩ A3).
Putting it All Together
Summing and subtracting appropriately via inclusion-exclusion yields:
P(A1 ∪ A2 ∪ A3) = 11/15.
Thus,
P(no couples together) = 1 - 11/15 = 4/15.
So the final probability is 4/15, which is approximately 26.67%.
Potential Follow-Up Questions
Why are we using 6! as the total number of arrangements instead of 5! for a round table?
In many round-table problems, we consider seatings equivalent up to rotation. However, in this problem’s statement (and in the short solution), the seats are considered labeled (seat #1, seat #2, etc.). Consequently, every distinct permutation of people around these labeled seats is counted as a separate arrangement, leading to 6! total possibilities.
If the problem had considered only seatings up to rotation as identical, we would use (6 - 1)!. But here, the text and the short solution clearly treat each seat as a distinct labeled spot.
Could we have approached this by direct enumeration (counting the ways to seat everyone so that no couple is adjacent) instead of using inclusion-exclusion?
Yes. One could try to count the number of ways to arrange six people directly without couples adjacent. However, inclusion-exclusion often is cleaner for these “no two adjacent” problems involving multiple pairs. A direct count can become cumbersome with many constraints, so inclusion-exclusion is typically the most straightforward.
How might the probabilities change if the couples were indistinguishable from each other?
If the couples were indistinguishable, we would define different events. We would count seatings in a different way, and that could reduce or complicate the sample space and event definitions. Typically, for identical couples, you must adjust your total permutations and the ways couples can sit together. The principle remains the same, but the combinatorial details change significantly.
Could we simplify the calculations using a combinatorial block argument for each event intersection?
Absolutely. A standard way to handle “couple sits together” is to treat each couple as a single block (with the couple’s internal permutations). For example, if couples 1 and 2 are both sitting together, we treat each couple as a block: then we effectively have four “entities” (couple 1 block, couple 2 block, plus two single individuals), multiply by internal permutations (2! for how each couple arranges themselves within a block), and also factor in seat positions. This is precisely what the snippet is doing in a more direct seat-count way.
If I want to simulate this in Python, how would I do it?
You can generate all permutations of six people and check adjacency:
import math
import itertools
def is_couple_adjacent(arrangement, couples):
n = len(arrangement)
for c in couples:
# c is a tuple representing the two people in that couple
# Check all indices in circular manner
for i in range(n):
if arrangement[i] in c and arrangement[(i+1) % n] in c:
return True
return False
people = [1, 2, 3, 4, 5, 6] # Suppose 1 & 2 form couple1, 3 & 4 form couple2, 5 & 6 form couple3
couples = [(1, 2), (3, 4), (5, 6)]
total_count = 0
no_couple_adj = 0
for perm in itertools.permutations(people):
total_count += 1
if not is_couple_adjacent(perm, couples):
no_couple_adj += 1
print("Probability (empirical):", no_couple_adj / total_count)
This brute-force approach would verify that the probability converges to 4/15.
How does this probability compare to similar “derangements” of pairs?
“No couple sits together” is analogous to the idea of a “derangement” but for adjacency constraints rather than matching positions. In classical derangements, we disallow each item from occupying its original position. Here, we disallow each couple from occupying adjacent positions. Both problems often rely on inclusion-exclusion and can have combinatorial subtleties.
All of these follow-up considerations help solidify why inclusion-exclusion is such a powerful and flexible tool, especially for “at least one” or “none” type probability questions in combinatorics and probability interviews.
Below are additional follow-up questions
What if one person decides not to sit at the table at all? How would this change the probability calculation for the remaining five seats?
A scenario like this introduces a new complexity: now there are effectively five people at the table (two couples and one single individual from the third couple), and one seat remains empty. The question becomes: “What is the probability that none of the two couples who are actually seated end up next to each other, given that there is a vacant seat and five total people?”
To break this down in detail:
The total number of ways to seat five people (from the two remaining couples plus the single person) around a table of six labeled seats is: choose which 5 seats out of 6 will be occupied (6 ways), and then permute the 5 people in those seats (5! ways). So the total sample space is 6 × 5! = 6 × 120 = 720.
We would define events for the remaining couples that they sit together. Now the adjacency concept must also consider the possibility that an empty seat is between two people, which might block that adjacency.
Pitfalls can arise if we forget that the empty seat might break up adjacency for a couple that otherwise would have been side-by-side. Failing to handle this subtlety can lead to an incorrect count of valid seatings.
In a real-world sense, maybe someone steps away for a phone call, or there’s simply a vacant seat. The problem’s combinatorial structure changes enough that we must carefully re-derive everything rather than just do a minor tweak.
This question demonstrates how adding even a single complication (an unoccupied seat) can cause a complete reevaluation of probabilities and how adjacency is defined.
How would the reasoning change if the table were rectangular with seating on each of the four sides, and corners allowed two possible adjacency directions?
A rectangular table with four sides and corners can create different adjacency patterns than a circular table:
Typically, each seat is adjacent to two seats. However, corner seats might have two distinct directions of adjacency (one along each edge). The exact arrangement depends on whether the table seats six people in some rectangular layout (like two people per longer side, one on each short side, etc.).
One must define carefully how “sitting together” is interpreted: do you consider only seats that share an edge as adjacent, or do you allow diagonal adjacency at corners? In real life, a corner seat might or might not be considered “together” with a person seated diagonally.
The core principle remains that we specify the adjacency rules, count the total possible ways individuals can occupy the seats, and then apply an inclusion-exclusion or other combinatorial arguments. But the adjacency rules differ from a simple circle.
A major pitfall is assuming the rectangular arrangement is just a minor variant of a circular table. The adjacency pattern changes, so the results and probabilities can be quite different.
How might the result generalize if we have n couples and 2n seats in a circle?
In a more generalized form with n couples around a 2n-seat round table, we want the probability that no couple ends up side-by-side. The approach can still use the same powerful inclusion-exclusion principle:
Define Ai as the event that couple i sits together.
Compute P(Ai) for each i using a block-seating argument (treating the couple as a single unit plus internal permutations).
Compute P(Ai ∩ Aj) for each pair of couples, and so forth.
However, as n grows, the number of terms in the inclusion-exclusion sum increases combinatorially (2n subsets of couples). This becomes unwieldy. Potential pitfalls:
One might try to do a direct formula for large n but forget to account for complicated overlaps (like multiple couples sitting together).
For large n, a common strategy is to use either approximations (e.g., Poisson approximations for rare events) or advanced combinatorial reasoning. Getting an exact closed-form expression can be very involved.
If the order of seats was not strictly around a circle but arranged in pairs facing each other, would that affect how adjacency is defined?
In some dining setups, seats might be paired off in a booth-style arrangement or in pairs facing each other. Then:
We must redefine adjacency: does “together” mean they share the same bench, or does it mean they are side-by-side on a bench, or does it include facing seats?
The total seat arrangements remain permutations of the people, but adjacency has to be precisely specified. For instance, if seats 1 and 2 are on one bench, 3 and 4 on another, 5 and 6 on a third, does “together” mean they share a bench or physically next to each other on the same bench?
A pitfall is that one might incorrectly assume the previous circular logic still applies. The geometry can drastically alter who can be next to whom. If “together” includes seats that are directly across a small table, the adjacency count changes.
Real-world analogy: think of airplane seats or booth seats at a restaurant. “Next to each other” might differ from the usual circular adjacency concept.
What if each couple must not only avoid sitting together but also avoid sitting directly across from each other (assuming a symmetrical round table with opposite seats)?
Sometimes “not together” might also mean you don’t want the couple to be directly across from each other in a circle of six. That changes the constraint:
Now an undesired scenario includes a couple being adjacent OR being opposite. On a table with six seats in a circle, seat 1 is opposite seat 4, seat 2 is opposite seat 5, and seat 3 is opposite seat 6. So we define event Bi for each couple i: “couple i is either adjacent or exactly opposite.”
Pitfalls arise if you overlook that the same arrangement can have both adjacency and opposite seat problems for different couples. This leads to an even more complex inclusion-exclusion scenario, because you have to combine adjacency sets and opposite-seat sets.
In real life, couples might not want to be in direct line of sight if they want privacy. This leads to a more elaborate combinatorial count that expands beyond the standard adjacency approach.
How do we handle the case where couples are allowed to be next to each other only if another constraint is satisfied, such as “they must be next to each other only if they are from the same department at work”?
This question introduces conditional adjacency constraints. Suppose each couple also belongs to a certain department, and we have a rule like: “Couples can only sit together if they share the same department.” That might sound contradictory, but one can imagine real-world constraints involving social or professional relationships:
We might end up defining events that are no longer simply “couple 1 is adjacent” but “couple 1 is adjacent AND they belong to the same department.”
The total sample space remains 6! for a labeled table with six seats, but events become narrower or broader depending on these extra constraints.
A major pitfall is mixing up the departmental grouping with the couple grouping. If departmental constraints overlap or conflict with adjacency constraints, the counting can get complicated.
In an interview context, this question tests whether you can adapt your combinatorial reasoning to more specialized constraints.
Could these seat-adjacency concepts be applied in a scheduling or roster assignment problem, where “sitting together” is analogous to “working together on the same shift”?
Yes, many scheduling or resource-allocation problems can be rephrased in terms of adjacency constraints. For instance, you might want to avoid having two employees from the same family on the same shift. Translating seat adjacency to shift assignment:
Instead of seat positions, we have shift slots labeled from 1 to 6.
“Adjacent seats” might become “consecutive shift slots” or “the same shift slot.”
A real pitfall is that shift scheduling might have carry-over adjacency (e.g., shift 1 is adjacent to shift 2, shift 2 to shift 3, etc.), but typically shift 1 is not adjacent to shift 6 in a linear schedule (unlike a circular table). This means the geometry changes from a circle to a line, altering how events are defined.
By adapting the same combinatorial approach, you can often handle adjacency constraints in rosters, though the details must align with how adjacency is defined in scheduling.
How might real-world randomness in arrival times or seat-selection preferences invalidate our assumption of each seating being equally likely?
In the standard problem, we assume each of the 6! seat permutations is equally likely. But in reality:
People might arrive at different times and occupy the “best seat” available. Preferences (like wanting to sit near the door or next to a friend) can bias the probability distribution.
Some couples might specifically try to avoid or ensure sitting together. That’s a direct violation of the uniform-random assumption.
A subtle pitfall is to apply uniform probabilities when the real process is far from uniform. If you use the 6! approach to approximate real life but people systematically choose seats in a biased way, your calculated probability of “no couples together” can be significantly off.
Interviewers may check whether you can critique the uniform assumption and propose ways to model more realistic seat choices (e.g., game theory or preference-based modeling).
How do you handle partial knowledge, for instance if we know two people’s seats but not the others? How does that affect the probability that no couple ends up adjacent?
If we have prior knowledge that two particular individuals (maybe from different couples) are already seated in seats 1 and 3, we have partial constraints on the arrangement:
We fix those two seats. Now the remaining four individuals (two couples) have only four seats left to occupy in 4! ways. But we must see how seats 1 and 3 might influence adjacency. Seat 2 or seat 4 could cause adjacency with seat 1 or 3.
We must re-check adjacency events under this partial assignment. Some events might be impossible (e.g., if one member of a couple is already placed, that might make it impossible for them to be next to their partner if the adjacent seats are known to be occupied by others).
The pitfall is to ignore that partial seat assignments can block or force certain adjacencies. If seat 2 is already taken by a non-partner, that might free the partner to sit somewhere else but could also cause unexpected adjacency with other couples.
In an interview, this tests conditional probability knowledge: “Given these partial conditions, what’s the updated probability that no couples sit together?” Using the same logic and combinatorial approach but restricted to the new sample space is crucial.
If the table allowed multiple people to share the same seat (theoretically, a large bench seat), how would adjacency be defined and how would it affect the count?
While unrealistic physically, conceptually you might imagine a bench that can seat multiple people side-by-side:
Adjacency might mean any two people on the same bench segment are considered next to each other. This breaks the standard “one seat per person” assumption.
The sample space is no longer permutations but combinations of how many people choose each bench segment, plus the order in which they arrange themselves on that bench.
A key pitfall: ignoring that a single “seat” could host multiple adjacency relationships if it’s a large bench. For example, if seats function like compartments where 2 or 3 people can fit, counting who is next to whom can be tricky.
While contrived, these complexities can appear in problems about “grouping constraints” or “distribution of people into buckets,” so it tests whether a candidate can generalize adjacency concepts beyond simple one-person-per-seat permutations.