GATE CS 2003 Q4 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Let the sorted sequence $A$ of $8$ distinct elements be represented as $A = \{a_1, a_2, \dots, a_8\}$ where $a_1 < a_2 < \dots < a_8$.

We need to form two sequences, $B$ of size $5$ and $C$ of size $3$, such that:

1. Both $B$ and $C$ are sorted in ascending order.
2. Merging $B$ and $C$ yields the original sequence $A$.

Since the merge of $B$ and $C$ results in $A$, the elements of $B$ and $C$ must partition the elements of $A$. That is, $B \cup C = A$ and $B \cap C = \emptyset$.

Because both $B$ and $C$ must be sorted in ascending order, the order of elements in each sequence is uniquely determined once the elements themselves are chosen. For example, if we choose any $5$ elements from $A$ to form $B$, there is exactly one way to arrange them in ascending order. The remaining $3$ elements will form $C$, and they also have exactly one valid ascending arrangement.

Thus, the number of distinct pairs of sequences $(B, C)$ is simply the number of ways to choose $5$ elements out of $8$ for sequence $B$:

Therefore, there are $56$ distinct pairs of sequences.