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
-
A. Flaxman, A. W. Harrow and G. B. Sorkin,
Strings with maximally many distinct subsequences and substrings,
The electronic journal of combinatorics 11:#R8, 2004.