A counting donuts problem involving combinatorics A store carries three types of donuts: Strawberry, Chocolate and Glazed
Suppose you bought $4$ of each kind and in addition, you have the option to apply sprinkles on your donuts. How many ways are there to eat the donuts if you never eat two donuts in a row that both have sprinkles? 
The idea I have is to apply inclusion-exclusion, but I am not sure where to start or if inclusion-exclusion is the best route to take. Any hints would be great. 
 A: ShreevatsaR has already broken the problem into its component parts, and you’ve correctly solved the first part.
For the recurrence, let $u_n$ be the number of ways to apply sprinkles to a row of $n$ doughnuts so that no two adjacent doughnuts have sprinkles. This is the same as the number of $n$-bit binary strings (strings of zeroes and ones) in which no two ones are adjacent. Let’s calculate a few values by hand. Say that a binary string is good if it does not have two adjacent ones. The empty string is good and is the only string of length $0$, so $u_0=1$. Both strings of length $1$ are good, so $u_1=2$. Three of the four strings of length $2$ are good, $00,01$, and $10$, so $u_2=3$. The good strings of length $3$ are $000,001,010,100$, and $101$, so $u_3=5$. And the good strings of length $4$ are $0000,0001,0010,0100,1000,0101,1001$, and $1010$, so $u_4=8$. The sequence $1,2,3,5,8$ is probably familiar: it’s part of the Fibonacci sequence. If you want further verification, you can check that there are indeed $13$ good strings of length $5$. This suggests that the recurrence that we want is $u_n=u_{n-1}+u_{n-2}$, with initial values $u_0=1$ and $u_1=2$, so that $u_n=F_{n+2}$.
Take a closer look at the $8$ good strings of length $4$: is there any obvious way to split them into a group of $5$ and a group of $3$? I see one such way: $5$ of them end in $0$, and the other $3$ end in $1$. This observation leads naturally to the recurrence. Every good string of length $n$ that ends in $0$ can be obtained by tacking a $0$ onto the end of a good string of length $n-1$, and every good string of length $n-1$ can be extended to a good string of length $n$ by appending a $0$; that accounts for $u_{n-1}$ of the good strings of length $n$, and all of them that end in $0$. Assuming that $n\ge 2$, a good string of length $n$ that ends in $1$ must actually end in $01$, so it can be obtained from a good string of length $n-2$ by tacking on $01$. On the other hand, every good string of length $n-2$ can be extended to a good string of length $n$ by appending $01$, and that accounts for every good string of length $n$ that ends in $1$. There are therefore $u_{n-2}$ such strings and hence $u_{n-1}+u_{n-2}$ good strings of length $n$ altogether.
A: I'll put hints below; ask me if you need help with any step.
First, count the number of ways of ordering the $12$ donuts: which $4$ are strawberry, which $4$ are chocolate, and which $4$ are glazed. This is a straightforward counting problem.
Second, count the number of ways of sprinkling (or not sprinkling) $12$ donuts, such that no two consecutive ones are sprinkled. This could be solved with the inclusion-exclusion principle I guess, though the simpler way I see to solve is to write a recurrence for the number of such ways, and evaluate it at $12$. Anyway, count this somehow.
Finally, the answer is the product of the two numbers, as they are orthogonal: you can think of the eating-order choice as that of first ordering the twelve donuts, and then sprinkling them.
