Results 1 to 7 of 7

Math Help - permutation problem

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    4

    permutation problem

    I have seen the problem in this forum about 6 number 1,1,2,2,3,3 to be arranged in a line with no same adjacent numbers. The solution is 30. But what happens if there are 8 number 1,1,2,2,3,3,4,4? Are there any general rules and quick ways to solve? I have tried to 8!/(2!2!2!2!)- 4 pairs -3 pairs-2pairs - 1pair, but the computations are too cumbersome....any good ways to solve? please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by taimanby View Post
    I have seen the problem in this forum about 6 number 1,1,2,2,3,3 to be arranged in a line with no same adjacent numbers. The solution is 30.
    By use of inclusion/exclusion rule we count these by first counting the ones we don't want and substracting from the total.
    For N pairs we have: \sum\limits_{k = 0}^N {\left( { - 1} \right)^k {N \choose k} \frac{{\left( {2N - k}\right)!}}{{2^{N - k} }}}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    38
    I've been racking my brain over this one, would you please flesh out your result/solution a bit more?

    edit:
    Nevermind, I see it now. Thanks.
    Last edited by n0083; March 24th 2009 at 02:33 AM. Reason: i now understand
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    4
    thx for the enlightenment...many thanks...never think that problem can be categorised and solved so methodically..cheers
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    4
    on second thoughts the solution is not right:
    the formula can eb expanded when N =4 to:
    8!/2^4-4C1.6!/2^3+...
    the first term describes all possible combinations
    but the 4C1.6!/2^3 only takes in the first 2 positions being a pair, and all possible combinations of the remaining 6 places.
    similarly 3rd term only describes the first 4 places being 2 pairs, and all possible combinations of the remaining 4 places...
    this does not account for x pair pair xx..
    I think we have to work again.


    thx for your helpful input..

    rgds
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by taimanby View Post
    on second thoughts the solution is not right:
    the formula can eb expanded when N =4 to:
    8!/2^4-4C1.6!/2^3+...
    the first term describes all possible combinations
    but the 4C1.6!/2^3 only takes in the first 2 positions being a pair, and all possible combinations of the remaining 6 places.
    similarly 3rd term only describes the first 4 places being 2 pairs, and all possible combinations of the remaining 4 places...
    this does not account for x pair pair xx..
    I don't think that you understand this problem. It is a well known problem.
    Here is a chart of the first 10 values.
    Attached Thumbnails Attached Thumbnails permutation problem-pairs.gif  
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2009
    Posts
    4
    thx Plato,,,the numeric answer are correct..i will look into the expression carefully again...It must be my misunderstanding....thx for yuoe help again...


    ben
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation problem.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 11th 2010, 09:39 AM
  2. PERMUTATION problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 25th 2009, 08:10 PM
  3. permutation problem 1
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 26th 2009, 09:57 PM
  4. Permutation Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 13th 2008, 12:15 PM
  5. Did I do this right? A Permutation Problem.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 3rd 2007, 09:59 AM

Search Tags


/mathhelpforum @mathhelpforum