2
$\begingroup$

Help! I assigned my Statistics & Probability high school students a bonus problem that I can't solve!

The problem: I have a class of 16 students, that I randomly assign to 4 table groups of size 4 each. In that class, there are two Ben's, two Katie's and two Sam's. Order within a table group doesn't matter, but table number does.

A) What is the probability that a random seating chart will end in maximum confusion (each Ben/Katie/Sam assigned to the same table as the student with their same name)?

B) What is the probability that there will be minimum confusion (no student assigned to a group with the student of their same name)?

I have figured out: number(possible seating charts) $$= \binom {16} 4\cdot \binom {12} 4\cdot \binom 8 4\cdot \binom 4 4 = 63,063,000$$ n(seating charts with the two Ben's together)$$=4\cdot \binom 2 2\cdot \binom {14} 2\cdot \binom {12} 4\cdot \binom 8 4\cdot \binom 4 4= 12,612,600$$ (there are 4 tables they could sit at, "choose" the two of them, choose the remaining 2 people at the table, and then fill in the rest of the tables) I'm pretty sure this works out correctly, with 3/15 = 1/5 chance that the second Ben is assigned to one of the 3 remaining open seats at the same table as the first Ben.

Where I'm stuck: I could do the same process for Katie's and Sam's, but those 12 million double-Ben seating charts also include some double Katie and double Sam seating charts. So I would need to subtract those out (so I don't double-count them). But how many are there? More specifically, how many numbers will I need to subtract? The charts with BenBenKatieKatie at one table, and the charts with BenBen at one table and KatieKatie at a different table (which would be multiplied by 3 rather than 4, yes?), and the charts with BenBenSamSam (but some of those are also the BenBen + KatieKatie charts)...

I feel like there's got to be an easier way, but I don't see it.

And I'm at much more of a loss for part B. I can calculate the probability that Bens will be at different tables, but the double counting goes similarly bonkers in my head.

Thank you! Laura

$\endgroup$
1
$\begingroup$

You have correctly calculated the number of possible seating arrangements.

What is the probability that a random seating chart will result in maximum confusion (each Ben/Sam/Katie assigned to the same table as the other student with the same name)?

There are two possibilities:

  1. There is one pair each at three different tables.
  2. There are two pairs at one table and one pair at a second table.

Three different tables:

There are four ways to assign a table to the two Ben's, three ways to assign one of the remaining tables to the two Katie's, and two ways to assign one of the remaining tables to the two Sam's. This leaves ten students whose seats have not been assigned. There are $\binom{10}{2}$ ways to assign two of them to sit with the Ben's, $\binom{8}{2}$ ways to assign two of the remaining eight students to sit with the two Katie's, and $\binom{6}{2}$ ways to assign two of the remaining six students to sit with the two Sam's. The remaining four students must sit at the remaining table. $$4 \cdot 3 \cdot 2 \cdot \binom{10}{2}\binom{8}{2}\binom{6}{2}\binom{4}{4}$$

Two different tables:

There are four ways to choose the table which will receive two pairs. There are $\binom{3}{2}$ ways to choose two pairs to sit at that table. There are three ways to choose the table that will receive the remaining pair. That leaves ten students whose seats who have not been assigned. There are $\binom{10}{2}$ ways to choose the two students who will sit with the single pair. There are $\binom{8}{4}$ ways to choose which four students will sit at the lowest numbered remaining table. The remaining four students must be seated at the remaining table. $$4 \cdot \binom{3}{2} \cdot 3 \cdot \binom{10}{2} \binom{8}{4} \binom{4}{4}$$

Since these two cases are mutually disjoint, the probability of maximum confusion is $$\frac{4 \cdot 3 \cdot 2 \dbinom{10}{2}\dbinom{8}{2}\dbinom{6}{2}\dbinom{4}{4} + 4 \cdot \dbinom{3}{2} \cdot 3 \dbinom{10}{2}\dbinom{8}{4}\dbinom{4}{4}}{\dbinom{16}{4}\dbinom{12}{4}\dbinom{8}{4}\dbinom{4}{4}}$$

What is the probability that a random seating chart will result in minimum confusion (no student assigned to a table with a student of the same name)?

For the numerator, subtract the number of seating arrangements in which at least one pair of students sit at the table. To do so, you will need to apply the Inclusion-Exclusion Principle.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Even though it doesn't matter which position within each table people sit at, we can include that information in our counting as long as we include it in the total number of arrangements too. Philosophically, the seats know which seat is which even if we don't care.

So there are 16 seats that can be sat in, and 16 people to sit in them. We could run through the people and each one chooses a seat, and then the next person chooses from the remaining seats etc. This argument gives 16! possible seating arrangements.

Now we need to count how many arrangements have the duplicated names together or apart.

First let's consider the number with the two Bens together: The first Ben can sit in any one of 16 places. And then the second Ben has to sit at the same table, so that's 3 places. So far this is 16*3 ways. The remaining 14 people can sit anywhere in 14! ways so we have a total of 16*3*14! arrangements with the two Bens together. This would be the same the number of arrangements with the two Sams together, and the number of arrangements with the two Katies together. This is a total of 3*16*3*14! ways to have at least one pair of duplicate names together.

However, I have counted more than once the arrangements with more than one pair of duplicated names together.

Let's consider the ways with at least two pairs of duplicated names.

We've already considered the ones with two Bens together. Now let's place the Sams. The first Sam can either go at the same table as the Bens, or at a different table.

If the first Sam is at the same table as the Bens, then there are two seats to sit in. And then the second Sam has to sit in the last seat at this table. So that's 2 ways. If the first Sam is at a different table as the Bens, then there are 12 seats to sit in. And then the second Sam has to sit in another seat at this same table, giving 3 choices.

In total we have 12*3 + 2 = 38 arrangements where the Sams sit together for each choice of where the Bens sit. There were 16*3 ways to seat the Bens together, so this is 16*3*38 ways to seat the Bens together and the Sams together. The remaining 12 people can be arranged in 12! ways, so we have in total 16*3*38 arrangements where the Bens and Sams are together.

This same counting would apply to sitting the Bens together and the Katies together, as well as the Sams together and the Katies together. So we have 3*16*3*38*12! arrangements. These were all double-counted when we counted the arrangements with at least one pair, so we'll need to take them off the previous total.

So now we have 3*16*3*14! - 3*16*3*38*12! ways to seat the students so that at least one pair of duplicate names are seated together. Except we've taken off any with all three pairs together more times than they should be. So we should add them back again.

There were 16*3 ways to place the two Bens together. If the two Sams were at the same table as the Bens, then there were 2 ways to do this. And then the first Katie has 12 choices, while the second Katie has 3 choices. This is 2*12*3 ways for each way of placing the Bens. If the two Sams were at a different table from the Bens, then there were 12*3 ways to do this. If the first Katie was at a table with Sams or Bens, there are 4 choices for a place to sit. Then the second Katie has one choice. On the other hand if the first Katie was at a table with no pair already there, then there are 8 choices for a place to sit, and 3 choices for the second Katie. So the Katies can be seated in 4*1 + 8*3=28 ways. Combining this with the Sams gives 12*3*28 ways for each way of placing the Bens. So in total we have 2*12*3 + 12*3*28 = 12*3*30 ways to place the Sams and Katies, giving 16*3*12*3*30 ways to place the Bens, the Sams and the Katies. After this, the remaining 10 people can be seated in 10! ways. So this gives 16*3*12*3*30*10! arrangements with the Bens, the Sams and the Katies together.

Hence the number of ways to seat people and have at least one pair of duplicated names together is 3*16*3*14! - 3*16*3*38*12! + 16*3*12*3*30*10!

Therefore the number of ways to seat people and have NO pairs of duplicated names together is 16! - 3*16*3*14! + 3*16*3*38*12! - 16*3*12*3*30*10!

Thus the probability of having no pairs of duplicated names is: (16! - 3*16*3*14! + 3*16*3*38*12! - 16*3*12*3*30*10!)/16! = 2584/5005

And the probability of having all pairs of duplicated names together is: 16*3*12*3*30*10!/16! = 9/1001

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.