Results 1 to 7 of 7

Math Help - Number of combinations

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Number of combinations

    In how many ways can (1,2,3,4) be arranged so that at least one of the numbers is in the correct position?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    Posts
    205
    Thanks
    1
    Presumably, one of the numbers being in the correct position means 1 is first or 2 is second, so on. So there are four ways this could be. In each of them, there are 3! ways to rearrange the remaining digits. The total number of possibilities is the sum of the number of possibilities in each of the four cases.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Quote Originally Posted by ragnar View Post
    Presumably, one of the numbers being in the correct position means 1 is first or 2 is second, so on. So there are four ways this could be. In each of them, there are 3! ways to rearrange the remaining digits. The total number of possibilities is the sum of the number of possibilities in each of the four cases.
    So answer is 4x3! ? (This is obviously wrong.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    Posts
    205
    Thanks
    1
    Oh crappers, in each of the four we get duplicate situations.

    So a new approach. The total possibilities without the constraint is 4!. The total number of ways where all the numbers are out of their respective place are 3*2*1, and these are precisely the scenarios we wish to exclude, so the answer is 4! - 3! = (4-1)3! = 18. I think this is right.
    Last edited by ragnar; February 26th 2011 at 09:07 PM. Reason: Ridiculously stupid mental math
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Quote Originally Posted by ragnar View Post
    Oh crappers, in each of the four we get duplicate situations.

    So a new approach. The total possibilities without the constraint is 4!. The total number of ways where all the numbers are out of their respective place are 3*2*1, and these are precisely the scenarios we wish to exclude, so the answer is 4! - 3! = (4-1)3! = 18. I think this is right.
    Actually, the answer is 15:
    (1, 2, 3 ,4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4 ,2), (1, 4, 3, 2)
    (1, 4, 2, 3), (3, 2, 1, 4), (3, 2, 4, 1), (4, 2, 3, 1), (4, 2, 1, 3),
    (2, 1, 3, 4), (2, 4, 3, 1), (4, 1, 3, 2), (3, 1, 2, 4), (2, 3, 1, 4).

    However, I am looking for a combinatorial way of solving this problem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    Posts
    205
    Thanks
    1
    I should probably shut up, but I have an answer, so maybe someone can verify me. It comes out with 15, but it's not the most combinatoric.

    How many ways can all four be in the correct position? 1

    How many ways can exactly three be? 0

    How many ways can exactly two be? 6
    (Argument: 1,2,_,_ has only one possibility. The number of such situations is like number of distinguishable permutations, where places filled in are not distinguishable and places not filled in are indistinguishable, so the total number is 4!/2!2! = 6.)

    How many ways can exactly 1 be? 8
    (Argument: 1,_,_,_ has two possibilities. The second position must be filled in with 3 or 4, and thereafter the remaining choices are fixed. There are 4 such situations, thus 2*4 = 8.)

    1+0+6+8 = 15

    I doubt a more combinatoric argument can be given, but my gut has obviously been wrong a lot tonight.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    You may find the following web page informative:

    Derangements and the Inclusion-Exclusion Principle
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of combinations.
    Posted in the Statistics Forum
    Replies: 5
    Last Post: July 27th 2011, 05:31 PM
  2. number of combinations possible
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 25th 2009, 08:28 AM
  3. number of possible combinations...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 6th 2009, 07:17 AM
  4. Number of Combinations
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: August 21st 2008, 01:33 AM
  5. Number combinations ...
    Posted in the Statistics Forum
    Replies: 4
    Last Post: March 27th 2008, 10:00 AM

Search Tags


/mathhelpforum @mathhelpforum