- #1
- 4,807
- 32
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[itex]\geq[/itex]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 [itex]x_1+...x_r=n[/itex] is [itex]\binom{n-1}{r-1}[/itex], the number of ways to place the deputies (indistinguisably) around the american and the russian is thus [itex]\binom{9-1}{3-1}=\binom{8}{2}[/itex].
Taking into account all the possible permutation of the 7 deputy amongs them, we get [itex]\binom{8}{2}7![/itex]. 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
[tex]\binom{8}{2}7!2!^2[/tex]
At first I had doubt about my solution, but it looks pretty solid now. Looks good?
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[itex]\geq[/itex]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 [itex]x_1+...x_r=n[/itex] is [itex]\binom{n-1}{r-1}[/itex], the number of ways to place the deputies (indistinguisably) around the american and the russian is thus [itex]\binom{9-1}{3-1}=\binom{8}{2}[/itex].
Taking into account all the possible permutation of the 7 deputy amongs them, we get [itex]\binom{8}{2}7![/itex]. 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
[tex]\binom{8}{2}7!2!^2[/tex]
At first I had doubt about my solution, but it looks pretty solid now. Looks good?
Last edited: