The answer is $ 4^{2008} - \binom{3}{1} 3^{2008} + \binom{3}{2} 2^{2008} - \binom{3}{3} 1^{2008}$. This follows from an inclusion exclusion argument.

nicetry007 wrote: The answer is $ 4^{2008} - \binom{3}{1} 3^{2008} + \binom{3}{2} 2^{2008} - \binom{3}{3} 1^{2008}$. This follows from an inclusion exclusion argument. Can you explain more clearly?

Here's an intermediate question: How many ways are there to select $ 3$ non-intersecting subsets of $ \{1, \dots n\}$? The way to think about it is to instead think about, for each number, choosing whether that number is in set $ A$, set $ B$, set $ C$, or none of the sets. This gives you $ 4^n$. Now apply inclusion exclusion, with the conditions you're excluding as $ c_1 =$"Set $ A$ is empty", $ c_2 =$"Set $ B$ is empty" and $ c_3 =$"Set $ C$ is empty". Note that we're assuming here that the order of set $ A$ vs. set $ B$ vs. set $ C$ matters. If this is not the case, you have to divide by $ 6$ to account for this at the end.

$ \left(4^{2008}-C_3^1 3^{2008}+C_3^2 2^{2008}-C_3^3 1^{2008}\right)\div A_3^3$

Can't we just use stars and bars? Wouldn't it then just be 2007 c 2?

No, because you don't have to contain all of the elements of the set.