2
$\begingroup$

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?

$\endgroup$

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.