# 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.

• Do you want all four properties simultaneously? Or are these four separate questions? Jul 14, 2014 at 2:18
• Simultaneous :) Jul 14, 2014 at 2:18
• There are 15 objects, distinguishable only as to shape (ball or cube) or (within the cubes) as to color? And by arranging them in a line you mean to give a sequence of appearance from left to right (the reverse of which might well constitute a distinct arrangement)? Jul 14, 2014 at 2:21
• Yes, that's what I was going for @hardmath Jul 14, 2014 at 2:22

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.

• Thank you for your answer and many ways of solving this problem! Jul 14, 2014 at 17:28
• You are welcome.
– gar
Jul 14, 2014 at 17:48
• Why is the state $I$ necessary in the adjacency matrix? Without it, the characteristic equation holds the same aside from a factor of $x$. What is $I$ any way? No object?
– Hans
Jul 3, 2015 at 23:21
• Yeah, it works without $I$ too. As you guessed it, I took it as an initial state -- no object.
– gar
Jul 4, 2015 at 3:19

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.

• Wow, I'll have to think about this. There are some very interesting ideas I haven't seen before :) I'll pick the green check though, I have confidence in your structured craziness @Rebecca ! Jul 14, 2014 at 3:32