Results 1 to 7 of 7
Like Tree4Thanks
  • 1 Post By SlipEternal
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By SlipEternal

Thread: Combinatorics problem number 2

  1. #1
    Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),India
    Posts
    203
    Thanks
    3

    Question 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]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,019
    Thanks
    1154

    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?
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,502
    Thanks
    2731
    Awards
    1

    Re: Combinatorics problem number 2

    Quote Originally Posted by SlipEternal View Post
    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.
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,019
    Thanks
    1154

    Re: Combinatorics problem number 2

    Quote Originally Posted by Plato View Post
    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.

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,502
    Thanks
    2731
    Awards
    1

    Re: Combinatorics problem number 2

    Quote Originally Posted by SlipEternal View Post
    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.
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,019
    Thanks
    1154

    Re: Combinatorics problem number 2

    Quote Originally Posted by Plato View Post
    No They are cared for.
    My way gives the exact same answer. We just have different methods of solving the same problem.
    Last edited by SlipEternal; Jun 14th 2017 at 11:25 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,019
    Thanks
    1154

    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}$.
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Average number, combinatorics
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 30th 2012, 03:17 AM
  2. Combinatorics using the number of conjugate subgroups
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Aug 23rd 2010, 11:14 PM
  3. Help with combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 25th 2009, 09:21 AM
  4. Find the number of intersection points?(Combinatorics)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 30th 2009, 06:43 AM
  5. Combinatorics and number theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 27th 2008, 06:27 AM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum