Consider a string of characters $a, b, c$ only. Such a string is called good if the number of $a$'s + number of $b$'s is equal to the number of $c$'s.

Given an integer $n$, find the number of strings of length $n$ consisting only of characters $ a,b,c$ such that all of its substrings of length $k$ are good.


$ n = 3 ,k = 2 $ is $6$,

$ n = 2,k = 1 $ is $0$

I could only solve when there are only two characters but can anyone help me how to solve when there are three characters.


1 Answer 1


For a good string $s$ of length $k$, let $M(n,s)$ denote the number of strings of length $n$ terminating in $s$ in which every $k$-letter substring is good. The quantity $M(n,s)$ is given by the following recurrence: $$ \begin{align} &M(k,s) = 1 \\ &M(n+1,ta) = M(n+1,tb) = M(n,at) + M(n,bt) \\ &M(n+1,tc) = M(n,ct) \end{align} $$ Here $t$ is a string of length $k-1$. Summing over all good strings $s$, we can solve your problem.

Since $a$ and $b$ are really interchangeable, we can also consider a slightly different recurrence, in which $s$ only consists of $a$'s and $c$'s: $$ \begin{align*} &M'(k,s) = 2^{\#_a(s)} \\ &M'(n+1,ta) = 2M'(n,at) \\ &M'(n+1,tc) = M'(n,ct) \end{align*} $$ Here the second parameter is a "template" in which $a$ stands for either $a$ or $b$.

Using either recurrence, you can find explicit formulas for any given value of $k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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