# Thread: Combinatorics problem number 2

1. ## Combinatorics problem number 2

If n men,among whom are A and B stand in a row,what is the probability that there will be exactly r men between A and B? If they stand in a ring instead of in a row, how to show that the probability is independent of r and hence $\frac{1}{n-1}.$ [ In the circular arrangement ,consider only the arc leading from A and B in a positive direction]

2. ## Re: Combinatorics problem number 2

In the line, consider pairs of positions that are exactly $r+1$ apart. For example, $(1,r+2)$ has exactly $r$ people between them. This is also true for $(2,r+3),(3,r+4), \ldots , (n-r-1,n)$ So, if $r>n-2$, then the answer is zero. Otherwise, there are $n-r-1$ different pairs of positions that yield exactly $r$ people between them. Choose a pair of positions. Now, you have two men, so choose a man to go into the leftmost position (the other one will go into the other position. Finally, fill the remaining positions.

$(n-r-1)2!(n-2)!$

The total number of arrangements is $n!$

So, the probability is $\dfrac{(n-r-1)2!(n-2)!}{n!} = \dfrac{2(n-r-1)}{n(n-1)}$

What have you tried for the second part?

3. ## Re: Combinatorics problem number 2

Originally Posted by SlipEternal
In the line, consider pairs of positions that are exactly $r+1$ apart. For example, $(1,r+2)$ has exactly $r$ people between them. This is also true for $(2,r+3),(3,r+4), \ldots , (n-r-1,n)$ So, if $r>n-2$, then the answer is zero. Otherwise, there are $n-r-1$ different pairs of positions that yield exactly $r$ people between them. Choose a pair of positions. Now, you have two men, so choose a man to go into the leftmost position (the other one will go into the other position. Finally, fill the remaining positions. $(n-r-1)2!(n-2)!$
I don't see that if A is at position 1 and B is at position r+2, why there are not r+1 people between them. I may be missing your point?

I think in blocks. there are $2(r!)$ ways to arrange $A~\&~B$ with $r$ people between them. That is one block.
Now we have $[n-(r+2)]+1=n-r-1$ blocks to rearrange.
Thus there are $2(r!)[(n-r-1)!]$ ways to arrange n people so that $A~\&~B$ have $r$ people between them.

4. ## Re: Combinatorics problem number 2

Originally Posted by Plato
I don't see that if A is at position 1 and B is at position r+2, why there are not r+1 people between them. I may be missing your point?
Let's renumber the positions. We have position 0 and position r+1. Between them are positions 1 through r. That is r positions between positions 0 and r+1. If we add one to each position, that is position 1 and position r+2. Another way to look at it, if there are two men and r men between them, that is a total of r+2 men. So, we would need positions 1 through r+2.

Originally Posted by Plato
I think in blocks. there are $2(r!)$ ways to arrange $A~\&~B$ with $r$ people between them. That is one block.
Now we have $[n-(r+2)]+1=n-r-1$ blocks to rearrange.
Thus there are $2(r!)[(n-r-1)!]$ ways to arrange n people so that $A~\&~B$ have $r$ people between them.
So, you are only arranging the r men between A and B, and you are not arranging any of the other men in the line? You have arranged r+2 of the n men.

5. ## Re: Combinatorics problem number 2

Originally Posted by SlipEternal
So, you are only arranging the r men between A and B, and you are not arranging any of the other men in the line? You have arranged r+2 of the n men.
No They are cared for.

Select the $r$ people: $\dbinom{n-2}{r}=\dfrac{(n-2)!}{r!(n-2-r)!}$
Group one such selection in a line with $A$ at one end and $B$ at the other. That that can be done in $2(r!)$ ways.
The other $n-r-2$ people along with the block above can be arranged in $(n-r-1)!$ ways.
So $\dfrac{(n-2)!}{r!(n-2-r)!}\times 2(r!)\times (n-r-1)!$ is the total.
Recap: pick the between people, rearrange into a block, rearrange others including the block.

6. ## Re: Combinatorics problem number 2

Originally Posted by Plato
No They are cared for.
My way gives the exact same answer. We just have different methods of solving the same problem.

7. ## Re: Combinatorics problem number 2

For the circular arrangement section of the problem, fix A. Now, if $n<r+2$, the answer is a 0% probability, because it will be impossible for A and B to have at least $r$ people between them. Otherwise, there is exactly one position available. Now, there are $n-2$ positions left to fill and $(n-2)!$ ways to fill them. Since there is $(n-1)!$ different circle permutations, this gives a probability of $\dfrac{(n-2)!}{(n-1)!} = \dfrac{1}{n-1}$.