In how many ways can you choose between 5 places to visit, but two times each? Lets suppose you want to visit 5 places, A B C D E, you also want to go to each one two times.
For example: You visit $A$, after a day you visit $B$, after a day you visit $B$ again, then $C$ and so on. The thing is, you cannot visit $E$ two times in a row, you have to visit another place first.
My attempt:
I can initially choose between 5 places, and I got stuck from here. For the second place, I may have already visited $E$, or I may have not, and so on for the other cases. I did not find a general formula to calculate it.
I would appreacite any answers or hints so much.
 A: Let's count the number of permutations of $AABBCCDDEE$ that are invalid, i.e. some city appears twice in a row. Let $n$ be the number of cities (in this example 5) and $S_X$ be the set of strings in which city $X$ appears consecutively. Note $\bigcup_{X \in \{A, B, C, D, E\}} S_X$ is exactly the set of strings that are invalid.
By the principle of inclusion and exclusion
$$
|\bigcup_{X \in \{A, B, C, D, E\}} S_X |  = \sum_{J \subset \{A, B, C, D, E\}} (-1)^{|J| + 1} |\bigcap_{X \in J} S_X|.
$$
Note that if $J$ is a subset of $k$ cities, $\bigcap_{X \in J} S_X$ is the set of strings in which you fix $k$ of the cities to be next to each other and the remaining cities can be visited in any order. The size of this set is $(2n-k)!/2^{n-k}$ since you `glue' the two symbols for each of the $k$ cities together resulting in $2n-k$ symbols where $n-k$ of them are repeated twice. Since this value only depends on the size of the set of cities, we can rewrite the sum by grouping sets of size $k$ together:
$$
\sum_{k=1}^n (-1)^{k - 1}\binom{n}{k}\frac{(2n-k)!}{2^{n-k}}.
$$
There are then $(2n)!/2^n$ total permutations so the number of valid permutations is
$$
\frac{(2n)!}{2^n} - \sum_{k=1}^n (-1)^{k - 1}\binom{n}{k}\frac{(2n-k)!}{2^{n-k}},
$$
which simplifies to
$$
\sum_{k=0}^n (-1)^{k}\binom{n}{k}\frac{(2n-k)!}{2^{n-k}}
$$
A: A hint building on my comment. Suppose I want to find the number of permutations of $abba$. I have four symbols in my string, and there are two pairs of identical symbols I can use. In that case, I would simply have $\frac{4!}{2!2!} = \frac{24}{4} = 6$ permutations.
With the condition that the two $b$s appear consecutively, however, we can treat the $bb$ as a single symbol. So we have three symbols: two $a$s and one $bb$. Then, the number of ways to permute them is $\frac{3!}{2!1!} = \frac{6}{2} = 3$. So this is the number of ways to permute $abba$ where the $b$s are consecutive. You can use this general idea to count the total number of permutations and then subtract the number where the same destination appears consecutively.
