0
$\begingroup$

Find the recurrence relation for how many ways there are to color a carousel with a circumference of length $n$ with two colors, red and blue such that no two reds will be adjacent

This is like asking about a string of $A,B$ of length $n$ without $AA$ and it can't start and end with $A$.

So: $a_n=\begin{cases} AB\text{____}B = a_{n-3} \\ B\text{______}= a_{n-1} \end {cases}$

$a_n=a_{n-1}+a_{n-3} \\a_1 = 2, a_2 = 3, a_3 =4 $

For $a_3$ these aren't allowed: $\{AAA, AAB, BAA, ABA\}$ so $2^3-4=4$

Can I do this with the beginning and end of the sequence?

$\endgroup$
5
  • $\begingroup$ Your notation is rather nonstandard, but assuming I understand your intentions correctly, how does ABABBBAB get counted? Or BABBA? $\endgroup$
    – hmakholm left over Monica
    Commented Jun 20, 2015 at 14:48
  • $\begingroup$ Yeah I think so, ABABBBAB is in the first case and BABBA is in the second case no? @HenningMakholm $\endgroup$
    – shinzou
    Commented Jun 20, 2015 at 14:49
  • $\begingroup$ @HenningMakholm the string ABBBA isn't supposed to be counted here I think. $\endgroup$
    – shinzou
    Commented Jun 20, 2015 at 14:52
  • $\begingroup$ Oh I get it now, ABBBA is a subsequence of ABABBBAB. $\endgroup$
    – shinzou
    Commented Jun 20, 2015 at 14:54
  • $\begingroup$ ABBBA is the subsequence you need to insert in AB___B to make ABABBBAB. $\endgroup$
    – hmakholm left over Monica
    Commented Jun 20, 2015 at 14:56

1 Answer 1

Reset to default
1
$\begingroup$

I would find it most intuitive to start by having two simultaneous recurrences: $p_n$ is the number of valid strings of length $n$ that start with B and end with A; $q_n$ is the number of valid strings of length $n$ that both start and end with B.

We then have $$ \begin{align} p_n &= q_{n-1} && p_1 = 0 \\ q_n &= p_{n-1} + q_{n-1} && q_1 = 1 \end{align} $$ This gives us $$ \tag{*} q_n = q_{n-1} + q_{n-2} $$ but what we're really interested in is $$ c_n = 2p_n + q_n = 2q_{n-1} + q_n $$ (where the A___B strings count twice because we can use either the string or its reverse). Because this is a linear combination of $q_n$s it will itself satisfy $\text(*)$.

$\endgroup$
4
  • $\begingroup$ I don't understand the last line, is $(*)$ the final answer? $\endgroup$
    – shinzou
    Commented Jun 20, 2015 at 15:19
  • 1
    $\begingroup$ @kuhaku: Yes, because $q_n$ satisfies that recurrence, and $q_{n-1}$ also satisfies it, so any linear combination of them will again satisfy it. $\endgroup$
    – hmakholm left over Monica
    Commented Jun 20, 2015 at 16:31
  • $\begingroup$ Ah I see. That's surprising because it's the same relation as if it was in a line instead of a circle. (so the string is allowed to end in A) $\endgroup$
    – shinzou
    Commented Jun 20, 2015 at 16:38
  • $\begingroup$ @kuhaku: Yes, the difference is only in the initial values. (In my mind this makes sense, because most of the growth in the number of assignments comes from decisions in the middle of the string, which can't see whether it connects at the end or not, so adding an extra position that is not covered by the boundary conditions should be expected to increase the number of solutions with the same factor (asymptotically) in each case). $\endgroup$
    – hmakholm left over Monica
    Commented Jun 20, 2015 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .