Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Combinatorics problem

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

    Post Combinatorics problem

    Hello Members,
    If n balls are placed at random into n cells, How to find the probability that exact one cell remains empty?
    Answer:-
    n balls can be placed into n cells in $n^n$ ways.How to proceed further?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Combinatorics problem

    Quote Originally Posted by Vinod View Post
    Hello Members,
    If n balls are placed at random into n cells, How to find the probability that exact one cell remains empty?
    Answer:-
    n balls can be placed into n cells in $n^n$ ways.How to proceed further?
    Are both the balls and the cells distinguishable? If they are, then you are correct that there are $n^n$ ways to place the $n$ balls into $n$ cells. Out of the $n$ cells, choose one to be empty. Of the remaining $n-1$ cells, choose one of them to have two balls. Then the probability is $\dfrac{n(n-1)}{n^n}$. Chances are, the balls are not distinguishable but the cells are. In that case, there are $\dbinom{2n-1}{n}$ ways to place $n$ indistinguishable balls into $n$ distinguishable cells. There are $\dbinom{n-1}{1}$ ways to place $n$ indistinguishable balls into $n-1$ distinguishable cells so that every cell has at least one ball. Therefore, the probability is $\dfrac{n-1}{\dbinom{2n-1}{n}}$. There are also the possibilities that the balls are distinguishable but the cells are not and that the neither the balls nor the cells are distinguishable.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Combinatorics problem

    Hello,
    Answer provided by the author of the book is $\binom{n}{2}n!n^{-n}$.I think Your answer seems to be different.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Combinatorics problem

    My answer was incorrect. Let's try again. Suppose $n=1$. Then there is a zero percent chance that exactly one cell will be empty and a 100% chance that every cell will have one ball (one ball, one cell, there is only one way to place the balls). So, assume $n>1$. As I mentioned above, we choose an empty cell and we choose a cell to have two balls. There are $n(n-1)$ ways of choosing that. Then, we choose two of the balls to be the two balls in the cell that has two balls. There are $\dbinom{n}{2}$ ways of choosing that. This leaves $n-2$ cells and $n-2$ balls. So, basically, we order the remaining $n-2$ balls and place them into the remaining $n-2$ cells in order. That is $(n-2)!$. Since each step was independent of the previous, we apply the product rule. Thus, we have:

    $n(n-1)\dbinom{n}{2}(n-2)!$ ways to place $n$ distinguishable balls in $n$ distinguishable cells with exactly one cell remaining empty. That is equal to $n!\dbinom{n}{2}$, just as the book has. My mistake. I went too quickly through the problem. Sorry about that.
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,652
    Thanks
    310

    Re: Combinatorics problem

    Quote Originally Posted by Vinod View Post
    Answer provided by the author of the book is $\binom{n}{2}n!n^{-n}$
    Correct...confirmed by simulation...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 6th 2017, 11:42 AM
  2. Combinatorics Problem
    Posted in the Statistics Forum
    Replies: 8
    Last Post: Jul 14th 2012, 05:15 AM
  3. problem in combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 21st 2011, 08:23 AM
  4. Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 1st 2010, 05:22 PM
  5. Combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Aug 14th 2009, 10:48 AM

/mathhelpforum @mathhelpforum