Counting Non-Consecutive Digit Rearrangements of 11223344

[Punkyc7]

Find the number of rearrangements of the string 11223344 that contain no two consecutive equal digits

So for the total rearrangements we have

\stackrel{8!}{2!2!2!2!}

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

\stackrel{7!}{2!2!2!}(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!, I am not sure of the sign though

So far I have

\stackrel{8!}{2!2!2!2!}-\stackrel{7!}{2!2!2!}(4)+.... 4!

 

[lanedance]

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
11223434
would get repeated twice, when it is only one arrangement, so you need to account for this

 

[lanedance]

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...

 

[Punkyc7]

Ok I think I got it

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

Does that seem right?

 

[lanedance]

can you explain your method (or the meaning of) for each of the terms?

 

[Punkyc7]

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