1
$\begingroup$

Every natural number in the set {${1, 2, 3, ..., n}$} occurs exactly twice in an array. How many such permutations are there in which no two same numbers are neighbours?

I know the problem should be solved by using principle of inclusion and exclusion and I've determined the number of all elements and those in sets without intersections. But, when counting elements in, e.g. $A_1 \cap A_2$ (where $A_i$ contains $i$ as neighbours), I can obtain correct number, but I had to count them by "chasing" cases.

Solution to this problem is: $\sum_{k = 0}^n(-1)^k\frac{(2n-k)!}{2^{n-k}}$ What is "smart" way to count this, without checking for cases? Thank you in advance.

$\endgroup$
  • 2
    $\begingroup$ You have everything you need. $A_i$ is the set for which $(ii)$ is a single object so $|A_i|=(2n-1)!/2^{n-1}$ because there are $2n-1$ objects of which $n-1$ are pairs, hence the division by $2^{n-1}$. For $A_i\cap A_j$ treat $(ii)$ and $(jj)$ (for $i\ne j$) each as single objects, there are now $2n-2$ objects, $n-2$ pairs giving $|A_i\cap A_j|=(2n-2)!/2^{n-2}$ and so forth. Applying PIE gives the summation $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\frac{(2n-k)!}{2^{n-k}}$$ which is not quite what you have. $\endgroup$ – N. Shales Aug 23 '17 at 14:53
  • $\begingroup$ Just to clarify: where I wrote "$n-1$ are pairs" this means that the $2n-2$ remaining objects (excluding $(ii)$) are divided into $n-1$ pairs, each pair containing identical elements. $\endgroup$ – N. Shales Aug 23 '17 at 15:04
  • $\begingroup$ Yes, I forgot to multiply it by the number of k-subsets during summation. $\endgroup$ – Nemanja Beric Aug 23 '17 at 15:08
  • $\begingroup$ I understand it now. Thank you $\endgroup$ – Nemanja Beric Aug 23 '17 at 15:12
  • $\begingroup$ You're most welcome :) $\endgroup$ – N. Shales Aug 23 '17 at 15:26

Your Answer

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

Browse other questions tagged or ask your own question.