Putting objects in a line. I'm working on a project outside of school, and I've run into a bit a problem.  I thought, maybe there are some problem solvers on the internet who would enjoy this.
I have 8 balls, 3 red cubes, and 4 blue cubes.  
How many ways can I arrange these items in a line so that:


*

*I never have three cubes consecutively

*I never have three balls consecutively

*I never have two red cubes next to one another

*I never have two blue cubes next to one another


If it's really hard or if it doesn't seem like an interesting problem, no worries.  Basically, I want to understand exactly what these restrictions limit me to.
If I come up with anything myself, I'll post it.
 A: Here's one more to supplement Rebecca's answer:
We may use a directed graph for such problems, and for our problem, the adjacency matrix of such graph is:
\begin{align*}
 \begin{array}{|l|rrrrrr|}\hline
 & \mathrm{I} & \mathrm{R} & \mathrm{B} & \mathrm{C} & \mathrm{BR} & \mathrm{CC} \\ \hline
\mathrm{I} & 0 & r & b & c & 0 & 0 \\
\mathrm{R} & 0 & 0 & 0 & c & b & 0 \\
\mathrm{B} & 0 & 0 & 0 & c & r & 0 \\
\mathrm{C} & 0 & r & b & 0 & 0 & c \\
\mathrm{BR} & 0 & 0 & 0 & c & 0 & 0 \\
\mathrm{CC} & 0 & r & b & 0 & 0 & 0 \\ \hline
\end{array}
\end{align*}
where R indicates red cubes, B indicates blue cubes and C is for balls.
Since there are 15 objects, we compute
\begin{align*}
  \left(\begin{array}{rrrrrr}
0 & r & b & c & 0 & 0 \\
0 & 0 & 0 & c & b & 0 \\
0 & 0 & 0 & c & r & 0 \\
0 & r & b & 0 & 0 & c \\
0 & 0 & 0 & c & 0 & 0 \\
0 & r & b & 0 & 0 & 0
\end{array}\right)^{15}
\end{align*}
and take the sum of the first row, and we see that $[c^8b^4r^3]=\boxed{11394}$ 
It's also possible to get the following multivariate generating function:
\begin{align*}
  G(r,b,c) &= \frac{\left(1+c+c^2\right)\left(1+b+r+2br\right)}{1-c\left(1+c\right)\left(b+r+2br\right)}
\end{align*}
Update
If we compute the characteristic polynomial of the matrix, we can see how the recurrence relation is structured:
\begin{align*}
  x^6  -(bc + cr)x^4 - (bc^2 + 2bcr + c^2r)x^3 - 2bc^2rx^2 = 0
\end{align*}
and the required recurrence is:
\begin{align*}
  f_{b,c,r} &= f_{b-1,c-1,r}+f_{b,c-1,r-1}+f_{b-1,c-2,r}+f_{b,c-2,r-1}+2 \left(f_{b-1,c-1,r-1}+f_{b-1,c-2,r-1}\right)
\end{align*}
and set the boundary conditions like $f_{0,0,0}=1, f_{1,0,0}=f_{0,1,0}=f_{0,0,1}=1$ etc.
We find that $f_{4,8,3}=11394$
With some perseverance, I think it's also possible to get a summation from the generating function.
A: Here's a sketch of an approach.  For $\newcommand{\b}{\bigcirc}\newcommand{\rs}{\color{red}{\square}}\newcommand{\bs}{\color{blue}{\square}}a,b \in \{\b,\rs,\bs\}$, let $f_{ab}(x,y,z)$ be the number of sequences of length $x+y+z$ that:


*

*have $x$ balls, $y$ red cubes, and $z$ blue cubes,

*have no three cubes consecutively,

*have no three balls consecutively,

*have no two red cubes next to one another,

*have no two blue cubes next to one another, and

*end in $ab$.


We want to find $\sum_{a,b  \in \{\b,\rs,\bs\}}f_{ab}(8,3,4)$.
If a sequence ends in $cd$ then we can append $ab$ to it according to the placement of $1$s in the following table:
$$
\begin{array}{r|cccccccc}
  & cd=\b\b & \b\rs & \b\bs & \rs\b & \rs\bs & \bs\b & \bs\rs \\
\hline
ab=\b\b & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\
\b\rs   & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
\b\bs   & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
\rs\b   & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\
\rs\bs  & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
\bs\b   & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\
\bs\rs  & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
\end{array}
$$
Each row of the above table gives a recurrence formula, e.g. the row $\rs\b$ gives:  $$f_{\rs\b}(x+1,y+1,z)=f_{\b\b}(x,y,z)+f_{\b\bs}(x,y,z)+f_{\rs\b}(x,y,z)+f_{\bs\b}(x,y,z).$$
We compute the boundary conditions, i.e.,
$$f_{\b\b}(2,0,0)=f_{\b\rs}(1,1,0)=f_{\b\bs}(1,0,1)=f_{\rs\b}(1,1,0)=f_{\rs\bs}(0,1,1)=f_{\bs\b}(1,0,1)=f_{\bs\rs}(0,1,1)=1$$
and
\begin{align*}
f_{\b\b}(3,0,0)=f_{\b\b}(2,1,0)=f_{\b\b}(2,0,1)=1, \\
f_{\b\rs}(2,1,0)=f_{\b\rs}(1,2,0)=f_{\b\rs}(1,1,1)=1,
\end{align*}
and so on.
Using these recurrences and boundary conditions, we can find each $f_{ab}(8,3,4)$ and sum them to give the number of sequences.
