Different approach to a seating permutation problem.

combinatoricspermutations

How many ways can $24$ students be sat such that $10$ particular students never sit next to each other?

The key to solving this is to see first that the $14$ other students can be rearranged within themselves in $14!$ ways. Then, there are $15$ other "slots" (or spaces) where the $10$ in particular can sit, allowing $^{15}P_{10}$ rearrangements in total. Henceforth, the total number of permutations are $14!\ ^{15}P_{10} \approx 9.5 \times 10^{20}$.

But I was wondering if I could approach it the other way. $10$ students can be rearranged without restrictions in $10!$ ways. The $9$ slots in-between could be filled with $14$ students in $^{14}P_{9}$ ways. Now that I've placed $19$ students while the criterion of placing those $10$ in particular separately is fulfilled, I can place the remaining $5$ students wherever I please. Seeing as that there are $20$ "slots" where they could be placed, and that the number of slots increase by $1$ every time I place a student, I should be able to rearrange them in $20\times21\times22\times23\times24=24!/19!= {}^{24}P_{5}$ ways. Henceforth, the total number of allowable permutations should be $10! \times {}^{14}P_{9} \times {}^{24}P_{5} \approx 1.345 \times 10^{22}$ too, but it isn't.

In fact, it is larger than the actual number of permutations. Why? Where did I go wrong?

Best Answer

The problem with your second working is that it leads to duplicates. To understand it, when you have chosen $9$ students of $14$ and arranged them in between $10$ students who cannot sit together, say there is a student A who is in the group of $9$. Now you are left with group of $5$ students. Say there is a student B in this group of $5$. Now you seat B in one of the twenty available slots.
But you also have arrangements where B is chosen to be in the first group of $9$ and A is in the second group of $5$. Now when you try and seat A as part of second group, it leads to duplicate arrangements.

If you want to seat $10$ students first and then seat $14$ students, here is one way to count arrangements -

First use stars and bars to count number of possible arrangements of seats. There are $11$ slots available after seating $10$ students. $9$ slots in between cannot be empty and that leaves only $5$ seats that must go to one of the $11$ slots. That can be done in $\displaystyle {15 \choose 5}$ ways.

Now that we have $14$ seats, all is left is to seat the students, which can be done in $14!$ ways.

So total number of permissible arrangements = $\displaystyle 10! \cdot {15 \choose 5} \cdot 14!$