How many ways to visit $6$ cities twice?

A person wishes to visit $6$ cities, each exactly twice, and never visiting the same city twice in a row. In how many ways can this be done ?

I tried by inclusion exclusion.

But Having a problem in finding the total number of outcomes ?

I guess total number of outcomes can be found by using multinomial coefficients like $(12!)/(2!)(2!)(2!)(2!)(2!)(2!)$.

Am i proceeding correct ?

• Do not confuse the phrases probability with number of outcomes. – JMoravitz Dec 21 '16 at 4:03
• @JMoravitz ohh. My Bad. – Jon Garrick Dec 21 '16 at 4:05
• @JMoravitz Thanks for the edit. Am I right here ? – Jon Garrick Dec 21 '16 at 4:07
• Well, the denominator is now correct, and if you have applied PIE correctly, so should the numerator be. – true blue anil Dec 21 '16 at 4:15

Proceeding via inclusion-exclusion: There are $2^{n-6}(12-n)!$ arrangements in which $n$ particular cities are visited twice in a row, so there are $$2^{-6}\sum_{n=0}^6(-2)^n\binom6n(12-n)!=2631600$$ arrangements in which no city is visited twice in a row.