CLR cover

Problem 142: Maximal number of (distinct) subsequences

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

For a word $x\in \{\sa{a},\sa{b}\}^*$, let $\Subs(x)$ denote the set of subsequences occurring in $x$, including the empty word, and let $\subs(x) = |\Subs(x)|$.

For a word $x\in \{\sa{a},\sa{b}\}^*$, design an efficient (polynomial time) algorithm computing $\subs(x)$.

What is a compact formula for the maximal number $S(n)$ of (distinct) subsequences of a binary word of length $n$.

References