GATE CS 1994 Q1.15 — Combinatorics: Counting, Recurrence Relations, Generating Functions

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

We can count the substrings by their lengths:

• Number of substrings of length $1$: $n$
• Number of substrings of length $2$: $n - 1$
• Number of substrings of length $3$: $n - 2$
• $\dots$
• Number of substrings of length $n$: $1$

The total number of substrings is the sum of these counts:

Alternative Approach:
A substring is uniquely identified by its starting index $i$ and ending index $j$ such that $1 \le i \le j \le n$. Choosing such a pair $(i, j)$ is equivalent to choosing $2$ distinct boundary points from $n+1$ possible boundary positions. The number of ways to do this is:

Thus, the correct option is D.