1
$\begingroup$

The following problem:

Ten diplomatic delegates are seated in a row. There are two specific seating requirements: 1) France and Britain are sat next to each other, and 2) the U.S. and Russia are sat at least one seat away from one another. How many seating arrangements are there?

Is in the section for multinomial coefficients in my book. I'm not sure how to use the multinomial coefficient to solve this. Actually, I don't know how to solve this, period.

An approach I've tried and failed:

There are actually nine seats, if we treat Britain and France as one seat with two permutations.

$$2\times\ldots$$

Decide whether the U.S. is a side seat (seat numbers 1 or 9) or not.

$$2\times2\times\ldots$$

Consider two cases, one where the U.S. is a side seat, one where it's not. Assign to either one of the two side seats, or to one of the seven middle seats.

$$2\times2\times(2\times\ldots+7!\times\ldots)$$

Assign Russia to either one of the seven seats remaining, or one of the six seats remaining.

$$2\times2\times(2\times7\times\ldots+7\times6\ldots)$$

Now two of the nine seats have been taken. Assign Britain and France to one of the 7 remaining seats:

$$2\times2\times(2\times7\times7\times\ldots+7\times6\times7\times\ldots)$$

Six seats remain. Assign remaining countries.

$$2\times2\times(2\times7\times7\times6!+7\times6\times7\times6!)$$

The problem with doing the above approach is that the resulting number is off by a magnitude of like, $10^8$. It's obscenely large.

Can I have some help? Where did I screw up?

Edit

So, for some reason I added factorials to combinations that did not need any... I'm still off by a whole magnitude, though, so my original problem still stands.

Edit 2

Okay, so actually I get the correct answer if I follow the steps above, I just need to divide by a factor of 2, since I don't need to multiply by 2 to count the end seat scenario... I'm already doing that by addition.

I still have a question, though:

How do I solve this with multinomial coefficients?

$\endgroup$
  • 1
    $\begingroup$ We don't need to break up into end and not end, though that will work. Leave Russia/US out for now. That leaves $7$, with France/Britain temporarily counting as $1$. That leaves $8$ "gaps" for Russia/US. Choose $2$, $\binom{8}{2}$ ways. Multiply by $2$. That leaves $7$ objects to be permuted, and then we multiply again by $2$ because we can switch the order of France and Britain. I don't understand the repeated multiplications by factorials. $\endgroup$ – André Nicolas Jan 28 '15 at 20:54
  • $\begingroup$ @AndréNicolas Doesn't that only account for the possibility that the U.S. and Russia are exactly one seat away from one another? I'm looking for at least, not exactly, or probably I'm missing something. $\endgroup$ – ok_ Jan 28 '15 at 21:01
  • 1
    $\begingroup$ When we choose $2$ gaps from the $8$ (including endgaps) this allows Russia, US to be far apart. But you could count the ways to choose the seats for these (without deciding who sits in which) your way. You should get $28$. $\endgroup$ – André Nicolas Jan 28 '15 at 21:08
  • $\begingroup$ @AndréNicolas That makes sense, thanks. Your solution is less annoying to compute than the one I tried. $\endgroup$ – ok_ Jan 28 '15 at 21:28
  • $\begingroup$ Ultimately they are very similar, the only real difference is the counting of seats on which we will put a reserved for Russia or US sign. $\endgroup$ – André Nicolas Jan 28 '15 at 21:39
2
$\begingroup$

There are a variety of approaches that will use normal binomial coefficients, but obviously with the special requirements there is "some assembly required".

Firstly I would follow your lead and regard France & Britain (FAB) as a composite "single seat" with $2!$ options. Leaving $9$ "seats" to be assigned.

US and Russia we'll leave until later - although taking cases as you did can be a good approach also. So otherwise we can have the remaining 7 countries (including FAB) arranged in $7!$ ways.

Now US and Russia need to be slotted into this ordering. They can successively pick $2$ of the $8$ spaces (including end-spaces) between the existing seats. So $8 \times 7=56$ options.

Final roll-up then: $$2!\cdot 7!\cdot 56 = 2 \times 5040 \times 56 = 564480$$


Things would get a little more complicated if the requirement were to have US and Russia with two intervening delegates, not least because we would then have to "unwrap" FAB again.

$\endgroup$
  • 1
    $\begingroup$ The correct answer is $564\,480$. So you neglected a multiplication by $2$ somewhere. $\endgroup$ – ok_ Jan 29 '15 at 3:27
  • $\begingroup$ @side thanks, it was the ordering of US & Russia. $\endgroup$ – Joffan Jan 29 '15 at 15:15
1
$\begingroup$

Another approach: first ignore the US/Russia restriction and just count the number of seatings where France and Britain are adjacent. Your trick of "glue them together and consider them as a seat with 2 permutations" works here. Say you get $X$ seatings this way.

This includes some seatings you don't want: it includes seatings where the US and Russia are adjacent. If you could count the number of seatings where France/Britain are adjacent and also US/Russia are adjacent -- say there are $Y$ such seatings -- then you should be able to subtract off these "bad seatings" and get the ones you actually want. And, you already know a trick for dealing with restrictions of the form "A and B must be adjacent".

(Edit: oops, missed the bit about wanting to use multinomial coefficients. Oh well.)

$\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.