求三元字符串及{0,1,2}^n中无重复字符计数的递推关系及推导步骤

Hey there! Let's walk through this problem clearly—tracking the "state" of the last character in the string is the key to unlocking the recurrence relation here, so let's break it down step by step.

First, let's clarify: both of your questions are actually the same problem! A "三元字符串" (ternary string) is exactly a string from the set {0,1,2}^n, so we can solve them together.

Step 1: Define our variables #

Let’s start by defining:

• a_n: the total number of valid length-n ternary strings (no adjacent duplicate characters like "00", "11", or "22").

To make this easier, we can split this into more specific states (since the choice of next character depends only on the last one):

• x_n: number of valid length-n strings ending with 0
• y_n: number of valid length-n strings ending with 1
• z_n: number of valid length-n strings ending with 2

Naturally, a_n = x_n + y_n + z_n.

Step 2: Find recurrence relations for the state variables #

Think about how to build a valid string of length n from a valid string of length n-1:

• For x_n (strings ending with 0): The previous character (in the length-n-1 string) can’t be 0—it has to be either 1 or 2. So every valid string ending with 1 or 2 of length n-1 can be extended by a 0 to make a valid length-n string ending with 0. That gives us:
  x_n = y_{n-1} + z_{n-1}
• By symmetry, the same logic applies to y_n and z_n:
  y_n = x_{n-1} + z_{n-1}
z_n = x_{n-1} + y_{n-1}

Step 3: Simplify to get the recurrence for a_n #

Since the characters 0, 1, 2 are identical in our problem (no bias toward any character), x_n = y_n = z_n for all n. Let's use this symmetry to simplify:

• Let’s substitute y_{n-1} = x_{n-1} and z_{n-1} = x_{n-1} into the equation for x_n:
  x_n = x_{n-1} + x_{n-1} = 2x_{n-1}
• Since a_n = 3x_n, we can rewrite this in terms of a_n:
  a_n = 3 * 2x_{n-1}
  But a_{n-1} = 3x_{n-1}, so substituting that in gives:
  a_n = 2a_{n-1}

Step 4: Set initial conditions #

We need base cases to start the recurrence:

• For n=1: There are 3 valid strings ("0", "1", "2"), so a_1 = 3.
• For n=2: Each length-1 string can be extended by 2 different characters (not matching the last one), so a_2 = 3*2 = 6—which also fits a_2 = 2*a_1 = 6.

Final Recurrence Relation #

Putting it all together, the recurrence relation for the number of valid length-n ternary strings with no adjacent duplicates is:

a_n = 2 * a_{n-1}
with initial condition a_1 = 3

If you want to write it without relying on the previous term's value, you can also express it explicitly as a_n = 3 * 2^{n-1}, but the recurrence form you asked for is the one above.

内容的提问来源于stack exchange，提问作者Student