Ok, so I've got a set of elements, some are duplicates but each are considered unique as far as set-making goes. I need to find how many permutations exist that do not put two of the duplicates next to each other, (for example, if the set were $\{blue, blue, green, red\}$ then I would like to know how many permutations exist that do not put the two blues adjacent to one another).

Now the trickier parts: there can be any number of duplicates of any element, so this would have to account for sets such as: $\{blue, blue, blue, red, red\}$ and $\{blue, blue, blue, blue\}$ and $\{blue, blue, green, green, green, red, red\}$. The goal is to find how many permutations there are where no two similar elements are adjacent.

This is as far as I have gotten: given an example set of $\{blue, blue, blue, red, red\}$, the number of permutations where a given element $blue$ is adjacent to another $blue$ is given by the equation $(N - 1)!\frac{blues!}{(blues - 2)!}$ and the intersection of the set of permutations where $blue$ is adjacent to $blue$ and the set of permutations where $red$ is adjacent to $red$ is: $(N - 2)\frac{blues!}{(blues - 2)!}\frac{reds!}{(reds - 2)!}$ and generalizing that out to read: the intersection of $i$ sets of permutations that have adjacent colors is: $$(N-i)!\prod_{x=0}^i\frac{colors_x!}{(colors_x - 2)!}$$

Using that generalization and the inclusion-exclusion principle, I have come to an equation $$nonadjacent = N! + \sum_{i=0}^{a} (-1)^{i}(N-i)!\prod_{x=0}^{i}\frac{colors_{x}!}{(colors_{x}-2)!}$$ where $a$ equals the number of different colors that have two or more duplicates.

This equation works perfectly as long as no individual color has more than two duplicated elements. What am I missing to make this equation work properly?


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.