How many ways can you arrange 8 couples so that no one is next to their mate? Devilishly tricky...I was proceeding to look at how many choices we have for the first person in line (16), and then how many choices for the 2nd person in line (14), and then how many for the 3rd person in line (13)...but after the 3rd person, the number that can go in the 4th position will depend on whether or not you have already put a couple in 2 of the first 3 positions. and as you go on the number you can put in the nth position will depend on how many couples you have already put in the line through positions n-1.
 A: The best way to solve this problem is with the principle of inclusion exclusion (see also, Stanley's Enumerative Combinatorics 1).
The form I am going to use is as follows: for a set of properties $T$, let $f_\geq(T)$ be the number of elements that have at least the properties in $T$.  Then the principle of inclusion exclusion states that $$ f_=(T) = \sum\limits_{Y \subseteq T} (-1)^{\#(Y - T)} f_\geq(Y) $$
In our case, let $f_\geq(k)$ be the number of ways to arrange $8$ couples with at least $k$ of the couples sitting next to each other.  Then $f_=(0)$ is what we're looking for, and inclusion exclusion gives us $$ f_=(0)= \sum\limits_{k = 0}^8 (-1)^k f_\geq(k) $$
We thus only need to find $f_\geq (k)$.  For this, I assume that you mean arrange the couples in a line. 
Fix $k$, we have to choose which of the $8$ couples will be sitting next to their partners, so we have $\binom{8}{k}$.  We now have to order the $16$ people, but since we know that the $k$ couples must be next to each other, this is the same as ordering $16 - k$ people, i.e. $(16 - k)!$ ways.  Finally, we can switch the order of each couple, so we have to multiply by a factor of $2^k$; thus, we have $$ f_\geq(k)= \binom{8}{k}(16 - k)! 2^k .$$
Putting it all together, we have $$ f_=(0)= \sum\limits_{k = 0}^8 (-1)^k \binom{8}{k}(16 - k)! 2^k $$
