# Permutation problem - How many permutations are there such that no two numbers are immediately adjecent? [duplicate]

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?

## marked as duplicate by Gerry Myerson, Grigory M, Najib Idrissi, Namaste homework StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jul 17 '14 at 11:10

• We just had exactly this problem yesterday. I'll see if I can find it. Here it is --- math.stackexchange.com/questions/868930/… – Gerry Myerson Jul 17 '14 at 9:46
• 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. – Martigan Jul 17 '14 at 9:50
• @Martigan, you may be right --- but as OP writes "numbers" and then lists digits, I choose to interpret "numbers" as meaning "digits". – Gerry Myerson Jul 18 '14 at 6:59

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):