Given a line segment of length $n$, determine the number of divisions of this line segment into black or white segments of length 3 and red, green or blue segments of length 2.
I tried using recurrence relation $a_n = 3a_{n-3} + 2a_{n-2}$ but I realised it's not correct, since for example, let $n = 5$, then I treat $3*blue + 2*blue$ and $2*blue+3*blue$ as two different decompositions, which is not correct.
Any ideas how to solve it?


You have the coefficients reversed as the length 3 segments come in 2 colors, and the length 2 segments come in 3 colors. Also the configuration you state can't actually occur because the length 3 segments and the length 2 segments have disjoint sets of colors, so $3*blue+2*blue$ is not possible, as the length 3 piece would have to be black or white.

So your relation ought to really be: $a_n=2a_{n-3}+3a_{n-2}$.

  • $\begingroup$ Yeah, you are right. There must've been some kind of lag in my brain... $\endgroup$ – Acee Feb 12 '17 at 16:33

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.