6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want all four properties simultaneously? Or are these four separate questions? $\endgroup$ – Rebecca J. Stones Jul 14 '14 at 2:18
  • $\begingroup$ Simultaneous :) $\endgroup$ – Open Season Jul 14 '14 at 2:18
  • 1
    $\begingroup$ 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)? $\endgroup$ – hardmath Jul 14 '14 at 2:21
  • $\begingroup$ Yes, that's what I was going for @hardmath $\endgroup$ – Open Season Jul 14 '14 at 2:22
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer and many ways of solving this problem! $\endgroup$ – Open Season Jul 14 '14 at 17:28
  • $\begingroup$ You are welcome. $\endgroup$ – gar Jul 14 '14 at 17:48
  • $\begingroup$ 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? $\endgroup$ – Hans Jul 3 '15 at 23:21
  • $\begingroup$ Yeah, it works without $I$ too. As you guessed it, I took it as an initial state -- no object. $\endgroup$ – gar Jul 4 '15 at 3:19
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ! $\endgroup$ – Open Season Jul 14 '14 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.