Putting objects in a line.

Question

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.

Answer 1

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.

Answer 2

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:

1. have $x$ balls, $y$ red cubes, and $z$ blue cubes,
2. have no three cubes consecutively,
3. have no three balls consecutively,
4. have no two red cubes next to one another,
5. have no two blue cubes next to one another, and
6. 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.