Results 1 to 6 of 6

Math Help - Combinatorics

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    Combinatorics

    How many ways are there to put 9 distinguishable objects into 5 distinguishable slots such that two particular objects (from the same 9 distinguishable objects) are placed next to each other among the 5 slots?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by posix_memalign View Post
    How many ways are there to put 9 distinguishable objects into 5 distinguishable slots such that two particular objects (from the same 9 distinguishable objects) are placed next to each other among the 5 slots?
    I will call the objects a1,a2,...,a9.
    Let us say that you want a1 and a2 to be in adjacent slots.
    Can you calculate the number C of all possibilities how to divide 7 objects a3,...,a9 into the 5 slots?

    Now, if a3,...,a9 are divided, you have to put a1 and a2 into two adjacent slots. So the actual result is
    C*N
    where N denotes the number of possibilities how to put a1 and a2 into adjacent slots.

    I'd like to show you that N=8.
    One way to see this: If you place a1 into the first or into the 5th slot, you have only one possibility where to put a2. (This gives you possibilities.)
    If you put a1 into one of the remaining slots, you have always two possibilities for a2. (This gives you 3*2=6 possibilities).
    So there are altogether 8 of them.

    Another way:
    If a1 and a2 are supposed to be adjacent, then they are placed in one of these two orders:
    a1,a2 or a2,a1
    Of course you have only four possibilities where to put the left one.
    So you have 2*4=8 possibilities.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by kompik View Post
    I will call the objects a1,a2,...,a9.
    Let us say that you want a1 and a2 to be in adjacent slots.
    Can you calculate the number C of all possibilities how to divide 7 objects a3,...,a9 into the 5 slots?

    Now, if a3,...,a9 are divided, you have to put a1 and a2 into two adjacent slots. So the actual result is
    C*N
    where N denotes the number of possibilities how to put a1 and a2 into adjacent slots.

    I'd like to show you that N=8.
    One way to see this: If you place a1 into the first or into the 5th slot, you have only one possibility where to put a2. (This gives you possibilities.)
    If you put a1 into one of the remaining slots, you have always two possibilities for a2. (This gives you 3*2=6 possibilities).
    So there are altogether 8 of them.

    Another way:
    If a1 and a2 are supposed to be adjacent, then they are placed in one of these two orders:
    a1,a2 or a2,a1
    Of course you have only four possibilities where to put the left one.
    So you have 2*4=8 possibilities.
    Thanks, I see why N is 8 and I can calculate the number C of all possibilities how to divide 7 objects a_3 , ... , a_9 into 5 slots.
    But when I did this I found that the number of slots must be 3 after the two objects that must be immediately adjacent have already been placed into the slots.

    If there are a total of 5 slots, two adjacent objects are placed into 2 of the 5 slots, then there would only be 3 slots remaining for the possible permutations of the 7 remaining objects?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    Thanks, I see why N is 8 and I can calculate the number C of all possibilities how to divide 7 objects a_3 , ... , a_9 into 5 slots.
    But when I did this I found that the number of slots must be 3 after the two objects that must be immediately adjacent have already been placed into the slots. If there are a total of 5 slots, two adjacent objects are placed into 2 of the 5 slots, then there would only be 3 slots remaining for the possible permutations of the 7 remaining objects?
    I found the question so vague that I did not bother with it.
    Now you reply confirms my judgment.
    You see to read the question as if the two ‘special’ objects must be alone in adjacent cells. That is not implicit in the statement.
    I read it as the selected objects are in adjacent cell that can be done in 8 ways.
    Then the other seven can be put into anyone of the five cells: 5^7 ways.

    How do you read it?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by Plato View Post
    I found the question so vague that I did not bother with it.
    Now you reply confirms my judgment.
    You see to read the question as if the two ‘special’ objects must be alone in adjacent cells. That is not implicit in the statement.
    I read it as the selected objects are in adjacent cell that can be done in 8 ways.
    Then the other seven can be put into anyone of the five cells: 5^7 ways.

    How do you read it?
    Forgive me if there was too much ambiguity in the stated problem, I'll try to revise the problem as follows:

    There are a total of 9 objects of which 2 are special.
    There are a total of 5 slots, each slot has the capacity of 1 object.

    Each object including the two special objects are distinguishable.
    Each slot is distinguishable, i.e. numbered.

    When the two special objects are placed in two of the slots then there are only three slots left for additional objects; these two special objects must always be part of the selection.

    How many permutations are there in total for these objects?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    There are a total of 9 objects of which 2 are special. There are a total of 5 slots, each slot has the capacity of 1 object. Each object including the two special objects are distinguishable.
    Each slot is distinguishable, i.e. numbered.
    When the two special objects are placed in two of the slots then there are only three slots left for additional objects; these two special objects must always be part of the selection. How many permutations are there in total for these objects?
    That is a completely different question from the OP.
    The answer is 8\cdot \left(^7\mathcal{P}_3\right)=8\cdot\frac{7!}{4!}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 06:03 AM

Search Tags


/mathhelpforum @mathhelpforum