6
$\begingroup$

There are 30 people sitting around a round table, and those 30 people all arrived to the event in 10 groups of 3. How many different ways can those people sit around the table if no-one is allowed to sit next to anyone else who arrived with them (ie was with them in a triplet, so for each person there are two other people they are not allowed to be seated next to).

Hope that explanation makes sense!

I am really stumped with this question, completely lost and no idea where to start. My train of thought was as follows, however: If you seat the first person down, then there are 29 people yet to be seated. Additionally, there are 2 people you can't sit in the next seat, adjacent to the first person you sat. So there are 27 people who can be seated in the second seat. Then in the third, there are 28 people remaining, as two have been seated. Again, two people can't sit there, for there are 26 people who can sit in the third chair.

Now, if my thinking is even correct up to this point, things start to get particularly foggy in my mind. So 27 people remain, and a maximum of two people may not be able to sit in the seat next to the third person. So it seems reasonable to suggest that 25 people can sit there. But if one of those two people has already sat earlier, then actually there are actually 26 of the remaining 27 who are allowed to sit in this seat. It is here that I am finding myself at a complete loss.

It occurred to me that I could calculate the total possible number of seating arrangements without conditions, and then subtract the arrangements where the given condition is broken....but that would be a lot of different illegitimate conditions to calculate.

Any help would be much appreciated. I have a few questions other like this to wrangle with afterwards aswell, so I don't mind if you help, just give hints, or solve the entire thing.

$\endgroup$
  • $\begingroup$ Could be a relevant question(perhaps):You have $7$ couples of husband and wives and you need to seat them in a row. In how many ways can this be done if nobody seats next to their partner?Hint-use PIE. Not sure if the same idea would be useful though. $\endgroup$ – rah4927 Oct 13 '15 at 14:40
2
$\begingroup$

You can do this via inclusion-exclusion, but I don't see how to find a closed form. Let's generalize from $10$ to $n$ groups of $3$. There are $3n$ conditions, one for each of the three pairs in each of the $n$ groups. To form all possible conjunctions of conditions, we can select $k$ groups in which $2$ conditions are fulfilled and $l$ groups in which $1$ condition is fulfilled. For each of the $k$ groups, there are $3$ ways to select the $2$ out of $3$ conditions, and for each of the $l$ groups, there are $3$ ways to select the $1$ out of $3$ conditions; in both cases there are $2$ orders for the group member fulfilling the conditions. Given the fulfilled conditions, there remain $(3n-2k-l-1)!$ possible orders of the $3n-2k-l$ blocks of people, where subtracting $1$ accounts for the cyclical symmetry. If you want to count cyclically equivalent configurations as distinct, you need to multiply the entire result by $3n$. Thus, inclusion-exclusion yields as the number of configuration that don't fulfill any of the conditions (and thus fulfill the given restrictions):

$$ \sum_{k=0}^{10}\sum_{l=0}^{10-k}(-1)^l6^k6^l\binom n{k,l,n-k-l}(3n-2k-l-1)!\;. $$

I don't see how to get a closed form for this. For $n=10$, we can evaluate the double sum, e.g. in Sage; the result is $1038433851912064897405414932480$.

$\endgroup$
  • $\begingroup$ Agree with the number, but I believe you're missing a factor of $(-1)^{2k+l}$, plus or minus.. $\endgroup$ – Tad Oct 14 '15 at 3:17
  • $\begingroup$ @Tad: I was, thanks, I corrected it. Of course $(-1)^{2k}=1$, so we only need $(-1)^l$. $\endgroup$ – joriki Oct 14 '15 at 5:16

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.