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 ?

  • $\begingroup$ Do not confuse the phrases probability with number of outcomes. $\endgroup$ – JMoravitz Dec 21 '16 at 4:03
  • $\begingroup$ @JMoravitz ohh. My Bad. $\endgroup$ – Jon Garrick Dec 21 '16 at 4:05
  • $\begingroup$ @JMoravitz Thanks for the edit. Am I right here ? $\endgroup$ – Jon Garrick Dec 21 '16 at 4:07
  • 1
    $\begingroup$ Well, the denominator is now correct, and if you have applied PIE correctly, so should the numerator be. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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