Number of possible routes through n countries and 2n cities, with restrictions Someone  is  planning  a  round-the-world  trip  that  involves  visiting  $2n$
cities, with two cities from each of $n$ different countries. He can choose a city to start and end the journey in, with the other $2n-1$ cities being visited exactly once.  However, he has the restriction that the two cities from each country should not be visited consecutively. How many different trips are possible? 
I have used the inclusion exclusion principle and reached that the desired number should be: 
$$(2n)!-2n\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}2^k \binom{2n-2-(k-1)}{k-1}(k-1)! (2n-2k)!$$
But I am having trouble of finding some closed formula for the sum. I was thinking of using the formula for the product of exponential generating functions, but I have trouble with the large binomial coefficient.
 A: Your edited version is correct but unnecessarily complicated. Consider the cities arranged in a circle. You want no two adjacent cities to be in the same country, and you want to distinguish one city as the start and end of the journey. There are $\binom nk$ ways to choose $k$ countries for which the constraint is violated, $2^k$ ways to choose the order within those $k$ pairs, $\frac{(2n-k)!}{2n-k}=(2n-k-1)!$ ways to arrange the $2n-k$ objects ($k$ pairs and $2(n-k)$ unpaired cities) in a circle without distinguishing a starting point, and $2n$ ways to distinguish a starting point, for a total of
$$
2n\sum_{k=0}^n(-1)^k\binom nk2^k(2n-k-1)!\;.
$$
This is the same as your result, since your two factorials in the end cancel the denominator of the binomial coefficient and the term $(2n)!$ is the $k=0$ term.
This is ${}_1F_1(-n;1-2n;-2)$, where ${}_1F_1$ is Kummer's confluent hypergeometric function. Wolfram|Alpha provides an alternative representation in terms of modified Bessel functions:
$$
{}_1F_1(-n;1-2n;-2)=\frac1{2^{n+\frac12}\mathrm e}\Gamma\left(\frac12-n\right)\left(I_{\frac12(-2n+1)}(1)+I_{\frac12(-2n-1)}(1)\right)\;.
$$
Anyway, the argument that Henry linked to still applies, so for $n\to\infty$ the count is asymptotic to
$$\frac{(2n)!}{\mathrm e}\;.$$
A: Apart from being a count, rather than a probability, this is essentially the same as Showing probability no husband next to wife converges to $e^{-1}$ so you can rewrite your expression as $$\displaystyle\sum_{i=0}^n (-2)^i {n \choose i}(2n-i)!$$ which will be close to $$(2n)!\,e^{-1}$$
