Arranging Deputies on a Bench with Restrictions

[quasar987]

Ten deputies must be aligned on a bench. How many ways of doing that is there, provided that the russian deputy and the american deputy do not want to be placed side to side, and that the english and french ones want to be side to side.

Since the english and the french deputies want to be side to side, let's consider them as 1 deputy for the time being (more preceisely, for the portion of the solution that treats the deputies as indistinguishable from one another).

Let's denote x1 the number of deputy placed on the russian's left, x_2 the number of deputy placed in btw them and x3 the number of deputy to the american's right. x1 and x3 can be zero but x2 must be at least 1. Of course x1+x2+x3 must be 7. The number of non-negative integer solutions to x1+x2+x3=7 under the constraint x2$\geq$1, is the same as the number of positive integer solution to (x1-1)+x2+(x3-1)=7 <==> x1+x2+x3=9 Based on the fact that the number of positive integer solutions to $x_1+...x_r=n$ is $\binom{n-1}{r-1}$, the number of ways to place the deputies (indistinguisably) around the american and the russian is thus $\binom{9-1}{3-1}=\binom{8}{2}$.

Taking into account all the possible permutation of the 7 deputy amongs them, we get $\binom{8}{2}7!$. Taking into account the possible permutation of the russian and the american, we throw a 2! into the mix. And finally, in order to take under consideration the possible permutations of the ensligh and french deputy we throw one last 2! into the mix and the glorious final answer is

$$\binom{8}{2}7!2!^2$$ At first I had doubt about my solution, but it looks pretty solid now. Looks good?

 

[shmoe]

That looks fine. Another appraoch would be to count all permutations not caring where the russian and american are, then subtract the number where they are side by side.

 

[0rthodontist]

Looks good, though that "number of positive solutions" formula threw me (the formula which I find easier to remember is for the number of non-negative solutions). There is a simpler way to do it:

1. Place everybody but the Russian. 8! * 2
2. Place the Russian. 7 * 8! * 2

 

[quasar987]

Wow neat!

shmoe, I tought about using that method at first, but could not see what an expression for the number where they are side by side would be.

 

[shmoe]

shmoe, I tought about using that method at first, but could not see what an expression for the number where they are side by side would be.

I'm sure you can... you were able to deal with the English and French deputies getting cozy, the Russian and American are no different.