Results 1 to 4 of 4

Math Help - Combinatory problem

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    3

    Question Combinatory problem

    Suppose there are N balls labeled 1, 2, 3, ... , N, and N boxes also labeled 1, 2, 3, ..., N.
    If you put one ball inside of each box, how many combinations are possible so that there are no match of the ball label and box label (ball 1 is not in box 1, ball 2 is not in box 2, and so on)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,676
    Thanks
    608
    Hello, lcmarincek!

    Is this a homework problem?

    If so, several questions arise:

    . . First of all, who assigned it?
    . . What course are you in?
    . . What is your mathematical background?

    . . How "good" is your teacher?
    . . Would he/she recognize the right answer if shown it?

    This is a complex problem with a highly elusive solution.
    I'd prefer not to explain it ... if it goes pffft! over your heads.


    Suppose there are N balls labeled 1, 2, 3, ... , N
    and N boxes also labeled 1, 2, 3, ..., N.
    If you put one ball inside of each box, how many combinations are possible
    so that there are no match of the ball label and box label?
    Such an arrangement is called a "derangement of N objects."

    I'll let someone else explain it.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by lcmarincek View Post
    Suppose there are N balls labeled 1, 2, 3, ... , N, and N boxes also labeled 1, 2, 3, ..., N.
    If you put one ball inside of each box, how many combinations are possible so that there are no match of the ball label and box label (ball 1 is not in box 1, ball 2 is not in box 2, and so on)?
    Do a web search for derangements.
    Derangement -- from Wolfram MathWorld
    If N>3, then you will find that the answer is approxminately \frac{N!}{e}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2008
    Posts
    3
    Quote Originally Posted by Soroban View Post
    Hello, lcmarincek!

    Is this a homework problem?

    If so, several questions arise:

    . . First of all, who assigned it?
    . . What course are you in?
    . . What is your mathematical background?

    . . How "good" is your teacher?
    . . Would he/she recognize the right answer if shown it?

    This is a complex problem with a highly elusive solution.
    I'd prefer not to explain it ... if it goes pffft! over your heads.

    Such an arrangement is called a "derangement of N objects."

    I'll let someone else explain it.
    This isnīt actually a homework problem. Itīs part of a problem I was trying to solve (just for fun).
    At first glance it didnīt seem so complex. I started working on it, but I couldnīt find a trivial solution (neither a complex one...), but I still thought it had a not so advanced solution. Thatīs why I posted it on high school section.
    But you mentioned the key to this problem: derangement. As far as I could see, itīs not a high school level problem.
    Iīll focus my search on derrangement.
    Thanks for the clue.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatory optimization problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 2nd 2010, 12:54 PM
  2. combinatory question
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 14th 2009, 08:13 AM
  3. Combinatory Counting help
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 14th 2009, 09:07 AM

Search Tags


/mathhelpforum @mathhelpforum