0
$\begingroup$

This question already has an answer here:

Consider the set of numbers 1,1,2,2,3,3,4,4.

How many permutations are there such that no two identical numbers are immediately adjacent?

$\endgroup$

marked as duplicate by Gerry Myerson, Grigory M, Najib Idrissi, Namaste homework Jul 17 '14 at 11:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ We just had exactly this problem yesterday. I'll see if I can find it. Here it is --- math.stackexchange.com/questions/868930/… $\endgroup$ – Gerry Myerson Jul 17 '14 at 9:46
  • $\begingroup$ I think this is slightly different, if we consider numbers like 12, 31 etc. We want to avoid having 12123434, as there are identical numbers immediately adjacent. I we are talking about one-digit numbers however, it is the same. $\endgroup$ – Martigan Jul 17 '14 at 9:50
  • $\begingroup$ @Martigan, you may be right --- but as OP writes "numbers" and then lists digits, I choose to interpret "numbers" as meaning "digits". $\endgroup$ – Gerry Myerson Jul 18 '14 at 6:59
1
$\begingroup$

There are $\frac{8!}{2!^4}$ permutations in total. $8$ symbols, in 4 pairs of 2 identical.

There are $\frac{4!}{1!3!}\frac{7!}{2!^3}$ ways at least 1 pair are coadjacent. (Choose the pair, then treat it as one symbol).

There are $\frac{4!}{2!2!}\frac{6!}{2!^2}$ ways at least 2 pair are coadjacent. (Choose the pairs, then treat each as one symbol).

There are $\frac{4!}{3!1!}\frac{5!}{2!}$ ways at least 2 pair are coadjacent. (Choose the pairs, then treat each as one symbol).

There are $4!$ ways all pairs are coadjacent.

Then use the Principle of Inclusion Exclusion (PIE):

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.