GATE CS 1998 Q1.23 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the number of non-empty (non-zero length) substrings that can be formed from a character string of length $n$ (assuming all characters in the string are distinct):

We can classify the substrings by their length $k$, where $1 \le k \le n$:

• Substrings of length $1$: There are $n$ such substrings.
• Substrings of length $2$: There are $n - 1$ such substrings.
• Substrings of length $3$: There are $n - 2$ such substrings.
• $\dots$
• Substrings of length $n$: There is $1$ such substring.

Summing these up, the total number of non-empty substrings is:

Alternative Approach:

A substring is uniquely defined by choosing its starting position $i$ and ending position $j$ such that $1 \le i \le j \le n$.

• The number of ways to choose two distinct indices $i < j$ is $\binom{n}{2}$.
• The number of ways to choose $i = j$ (substrings of length 1) is $n$.

Total substrings = $\binom{n}{2} + n = \frac{n(n-1)}{2} + n = \frac{n(n+1)}{2}$.

Thus, the correct option is D.