GATE CS 2014 Set 1 Q49 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Let $P(n)$ denote the number of $n$-pennants (sequences of $1$s and $2$s that sum to $n$).

An $n$-pennant can be formed in one of two mutually exclusive ways:

1. By appending $1$ to an $(n-1)$-pennant. There are $P(n-1)$ such pennants.
2. By appending $2$ to an $(n-2)$-pennant. There are $P(n-2)$ such pennants.

This gives us the recurrence relation:

We are given the base cases:

• For $n = 1$: the only pennant is $(1)$, so $P(1) = 1$.
• For $n = 2$: the pennants are $(2)$ and $(1,1)$, so $P(2) = 2$.

Using the recurrence relation, we can compute the values sequentially:

• $P(3) = P(2) + P(1) = 2 + 1 = 3$
• $P(4) = P(3) + P(2) = 3 + 2 = 5$
• $P(5) = P(4) + P(3) = 5 + 3 = 8$
• $P(6) = P(5) + P(4) = 8 + 5 = 13$
• $P(7) = P(6) + P(5) = 13 + 8 = 21$
• $P(8) = P(7) + P(6) = 21 + 13 = 34$
• $P(9) = P(8) + P(7) = 34 + 21 = 55$
• $P(10) = P(9) + P(8) = 55 + 34 = 89$

Thus, the number of $10$-pennants is 89.