Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 3 (Page No. 125)

Question

In a string of length $n$, how many of the following are there?

1.  Prefixes.
2.  Suffixes.
3.  Proper prefixes.
4.  Substrings.
5.  Subsequences.

Answer 1

1. $n + 1 (n$ prefixes for $n$ characters, plus the empty string$)$
2. $n + 1 ($similar to $(a))$
3.  $n - 1 (n$ prefixes for $n$ characters, minus the string itself$)$
4. $n [1$ character substring$] + (n - 1) [2$ character substring$] + \dots + 1 = \dfrac{n (n + 1)}{2}.$  Add $1$ to include the empty substring.
5. $\displaystyle{}\sum_{i=0}^{n} {^{n}C_{i}} = 2^{n}$, if you include the empty subsequence.