CLR cover

Additional Problem 20: Number of Distinct Subsequences

\( \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\subs{\mathit{subs}} \)

Let $\subs(x)$ denote the number of distinct subsequences of a word $x$ including the empty one. In this problem we assume the alphabet is $\{a,b\}$.

We say that $x$ is extremal if it maximizes $\subs(x)$ over all words of the same length. It is known that for a given length there are only two extremal (isomorphic) binary words.

Design an efficient (polynomial time) algorithm computing $\subs(x)$.

Show that every finite word of the form $x=abababa...$ is extremal.

What is a compact formula for $subs(x)$, where $x$ is extremal?
Consider extremal finite words of the form $x=abababa...$. Use Fibonacci numbers, observe that $\subs(a)=2, \subs(ab)=4, \subs(aba)=7, \subs(abab)=12$.

References