# Eight digit number is formed using all the digits: $1,1,2,2,3,3,4,5$

Eight digit number is formed using all the digits: $1,1,2,2,3,3,4,5$. Find

1. Total numbers in which no two identical digits appear together.

2. Exactly two pair of identical digits occur together.

For first part, I thought of finding number of ways such that all three numbers are always together and then subtract it from total numbers that can be formed $(\frac{8!}{2! 2! 2!})$ but it didn't work. How should I proceed?

One way is to use Inclusion/Exclusion. You attempted a form of it, but something more elaborate is needed.

You know that there are $\frac{8!}{2!2!2!}$ possible sequences if we have no restriction.

Now let us count the number that have the two $1$'s together. Tie them together, and think of them as a superletter. Now we have $7$ "letters." These can be arranged in $\frac{7!}{2!2!}$ ways. We get the same count for the $2$'s together, and for the $3$'s together. So our first estimate for the required number is $\frac{8!}{2!2!2!}-3\cdot \frac{7!}{2!2!}$.

But we have subtracted too much, for we have subtracted one too many times the patterns that have two $1$'s and two $2$'s together, as well as the ones in which we have two $2$'s and two $3$'s together, and so on. There are $\frac{6!}{2!}$ of each of these, so our next estimate is $\frac{8!}{2!2!2!}-3\cdot \frac{7!}{2!2!}+3\cdot \frac{6!}{2!}$.

But we have added back too much, for we have added back one too many times the $5!$ sequences in which the $1$'s are together, and the $2$'s, and the $3$'s. Our final count is $\frac{8!}{2!2!2!}-3\cdot \frac{7!}{2!2!}+3\cdot \frac{6!}{2!}-5!$.

There are $3$ pairs and $2$ singles.

For the first part, the simplest way is to use inclusion-exclusion, viz.

All ways - ways with at least $1$ pair together + at least $2$ pairs together - all $3$ pairs together

= $\dfrac{8!}{2!2!2!} - \dbinom31\dfrac{7!}{2!2!} + \dbinom32\dfrac{6!}{2!} - 5! = 2220$

For the second part, there are conflicting posts, this will hopefully subtract from confusion !

There are $\dbinom32 =3$ choices for the two pairs to be together.

Supposing these to be the $1's$ and $2's$, one arrangement excluding the $3's$ would be

$\uparrow{\Large 1}\uparrow{\Large 2}\uparrow 4\uparrow 5\uparrow$, and the $3's$ can be inserted at the uparrows in $\binom52$ ways

Thus number of such arrangements $\dbinom32\times 4!\times\dbinom52 = 720$

• I'm pretty sure that your answer to the second part is wrong. I don't understand your description so I cannot explain why, but using a simple inclusion/exclusion I get a different result. – barak manos Mar 27 '16 at 9:40
• @barakmanos This answer is correct. true blue anil permuted four objects (a double $1$, a double $2$, the $4$, and the $5$), which can be done in $4!$ ways. Since the two $3$'s cannot be consecutive, he then inserted the two $3$'s in the five gaps (indicated by the uparrows). This can be done in $\binom{5}{2}$ ways. An analogous argument applies to having a double $1$ and a double $3$ with the $2$'s separated and to having a double $2$ and a double $3$ with the $1$'s separated. The factor of $\binom{3}{2}$ counts the number of ways of choosing two of the three double letters. – N. F. Taussig Mar 27 '16 at 9:52

André Nicolas pretty much hit it spot on with part 1, so I'll answer part 2.

There are 3C2 ways to choose which 2 pairs of numbers get to occur together. We'll just take 1 and 2 for example. Group the two 1's and two 2's together as a block.

11 | 22 | 3 | 3 | 4 | 5

There would be 6!/2! ways to arrange these. However, within these arrangements, there were some that also had the two 3's together. We want ONLY the two 2's and two 1's together, not the two 3's.

11 | 22 | 33 | 4 | 5

Thus we must subtract out 5!.

Thus our final number comes out to (3C2) * (6!/2! - 5!) = 720 arrangements

The number of combinations in which the ones are next to each other is ${{7!}\over {2!2!}}=1260$

This would also be the number of combinations in which the twos are next to each other, and the number in which the threes are next to each other.

The number of combinations in which the ones and twos are next to each other would be ${{6!}\over {2!}}=360$

This would also be the number of combinations in which the ones and threes are next to each other, and the number in which the twos and threes are next to each other.

The number of combinations in which the ones, twos, and threes are next to each other would be $5!=120$

The number of combinations with at least one identical pair is 3*1260-3*360+120=2820.

The number of total combinations is 5040 as you calculated, so the number of combinations with no identical pairs next to each other is 2220.

The number of combinations where exactly two pair of identical digits occur together is 3*360-3*120=720.