0

A sequence of $n$ characters, consisting of the characters $A$, $B$, $C$, $D$; how many sequences of length $n$ exist without three consecutive characters being identical?

This problem was part of a set of programming problems whose solutions were based on counting principles. Input: N Output: number of strings corresponding to above condition

To simplify the output, we were required to give the result modulo some specifc number as the output, but that's probably an irrelevant detail.

My first thought was inclusion-exclusion, but I couldn't figure out the solution. Can anyone provide any insight?

Example: Input: N = 3 Output: Count = 60 Justification: 4^3 - {$AAA$, $BBB$, $CCC$, $DDD$} = 64 - 4 = 60

Numi
  • 3

1 Answers1

1

Hint: If $T_n$ is the amount of such sequences of length $n$, $$T_n=3\left(T_{n-1}+T_{n-2}\right),$$ for $n\geq3$.

ViHdzP
  • 4,582
  • 2
  • 18
  • 44
  • I cant really wrap my head about this, but I also know nothing about recurrence relations, I'll read up on it and then attempt this route; thank you! But any help regarding an approach using inclusion-exclusiom or something like that – Numi Jan 03 '20 at 02:45
  • I’ll give another hint. Any valid string of length at least $3$ is composed of a shorter valid string, with one of $3$ characters at the end, either once or twice. Can you see where this is going now? – ViHdzP Jan 03 '20 at 04:27
  • 1
    I think so: you mean that we can create a valid string out of valid substrings by selecting a character that is not the terminating character of the substring, and append it either once or twice; since there are only three options for the appended character, u added the coefficient 3. Is that right? – Numi Jan 03 '20 at 14:33
  • So, 3[T(n-1)] is the subset of Tn where a single character is added, and 3[T(n-2)] the subset to which two identical characters were added? – Numi Jan 03 '20 at 14:35
  • So then it would follow that I find some formula for Tn in terms of n using initial conditions T1 = 4, T2 = 16? – Numi Jan 03 '20 at 14:41
  • @Numi Yep, precisely so. – ViHdzP Jan 03 '20 at 17:45
  • Many thanks, after reading the theory regarding linear, I've gotten to the step of creating the characteristic equation. My roots are irrational, but I suppose once expanded out it will become an integer. I have a last follow up question regarding the final solution: my equation is now Tn = C((3+[sqrt(21)])/2)^(n-1) + D(same term except minus sqrt(21)). Is it valid for me to sub in T0 = 0? – Numi Jan 04 '20 at 06:20
  • @Numi Your value $T_0$ would be such that $T_2=3\left(T_0+T_1\right)$, but the argument that got us our recursion isn’t valid for $n\leq2$. So, plugging in wouldn’t be valid. You can, however, calculate it directly: the only string of length zero is the empty string, which does satisfy your condition. Therefore, $T_0=1$. – ViHdzP Jan 04 '20 at 06:25