Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Rearrangement of 11223344

  1. Aug 29, 2011 #1
    Find the number of rearrangements of the string 11223344 that contain no two consecutive equal digits

    So for the total rearrangements we have


    I was thinking I would count the total number of rearrangements that have the same digit next to each other

    So I started with the total number of rearrangements and sub tract the number of rearrangements that share the same number with the first number selected

    [itex]\stackrel{7!}{2!2!2!}[/itex](4) I multiplied by four because there are 4 numbers. From here I am confused, do you assume that you have had 2 digits in a row or do you assume you could have any rearrangement of the 6 digits?

    Im thinking the last term would be 4!, im not sure of the sign though

    So far I have

    [itex]\stackrel{8!}{2!2!2!2!}[/itex]-[itex]\stackrel{7!}{2!2!2!}[/itex](4)+............. 4!
    Last edited: Aug 29, 2011
  2. jcsd
  3. Aug 30, 2011 #2


    User Avatar
    Homework Helper

    yeah the problem will be accounting for like terms with double and greater repetitions, and over counting of these.

    For example if you just counted the number of a single repetition
    would get repeated twice, when it is only one arrangement, so you need to account for this
  4. Aug 30, 2011 #3


    User Avatar
    Homework Helper

    so there's probably a number of ways to do it and its not always obvious which is best until you get into it, but to get started:

    counting the number of arrangements with repetitions:

    first consider a single set repeated digits
    - choose from 4 numbers
    - now choose a position in the string = 7
    - now the account for how the other 6 digits can be arranged

    But any cases that have 2,3 or 4 sets of repeated digits, will have been over-counted. I would try and calculate these explicitly and subtract...
    Last edited: Aug 30, 2011
  5. Aug 30, 2011 #4
    Ok I think I got it

    [itex]\stackrel{8!}{2!2!2!2!}[/itex]-[itex]\stackrel{7!}{2!2!2!}[/itex](4C1)+ [itex]\stackrel{6!}{2!2!}[/itex](4C2)-[itex]\stackrel{5!}{2!}[/itex](4C3)+4!(4C4)

    Does that seem right?
  6. Aug 30, 2011 #5


    User Avatar
    Homework Helper

    can you explain your method (or the meaning of) for each of the terms?
  7. Aug 31, 2011 #6
    The first term is the number of rearrangements of the string

    the second term is once we select the first number we have 7 left over and we can choose for 1 of the 4 numbers

    the third term is when we have 6 letters in the string ( i.e. 223344) when we choose two numbers of those next to each other we have and of the four numbers we can choose 2 different ways.

    the fourth term the number of string when there are 5 rearrangements when we choose 3 of the four numbers

    the last one is the number of ways the string keeps all of the numbers together
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook