Counting using recursion (intro) - Discrete Math

1. The Catalan numbers $C_n$ satisfy $C_0 = 1$ and $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ for $n \geq 1$. These count the number of ways to parenthesize a product of $n+1$ factors. What is $C_3$?
   Answer: 5 Catalan numbers appear frequently in combinatorics problems involving recursive structures like parenthesizations, binary trees, and path counting. When you see the recurrence relation $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$, think about how it breaks down a problem into smaller subproblems. To find $C_3$, you need to work systematically from the base case. Given $C_0 = 1$, let's calculate step by step: For $C_1$: $C_1 = C_0 \cdot C_0 = 1 \cdot 1 = 1$ For $C_2$: $C_2 = C_0 \cdot C_1 + C_1 \cdot C_0 = 1 \cdot 1 + 1 \cdot 1 = 2$ For $C_3$: $C_3 = C_0 \cdot C_2 + C_1 \cdot C_1 + C_2 \cdot C_0 = 1 \cdot 2 + 1 \cdot 1 + 2 \cdot 1 = 5$ You can verify this by listing all parenthesizations of four factors $abcd$: $(((ab)c)d)$, $((ab)(cd))$, $((a(bc))d)$, $(a((bc)d))$, and $(a(b(cd)))$ — exactly 5 ways. Choice A (3) likely comes from miscounting or confusing $C_3$ with $C_2 + 1$. Choice B (4) might result from forgetting one term in the sum or confusing this with the number of factors minus one. Choice C (6) could come from incorrectly applying factorial thinking or overcounting parenthesizations. When working with Catalan numbers, always build up from smaller values systematically. The recurrence relation captures how each parenthesization splits the expression at different points, making each term $C_i C_{n-1-i}$ represent splitting after the $(i+1)$-th factor.
2. Let $f(n)$ be the number of binary strings of length $n$ that contain no three consecutive 1's. If $f(1) = 2$, $f(2) = 4$, and $f(3) = 7$, what is $f(6)$?
   Answer: 44 A valid string of length $n$ can end in 0 (giving $f(n-1)$ possibilities), end in 01 (giving $f(n-2)$ possibilities), or end in 011 (giving $f(n-3)$ possibilities). This yields $f(n) = f(n-1) + f(n-2) + f(n-3)$. Computing: $f(4) = 7 + 4 + 2 = 13$, $f(5) = 13 + 7 + 4 = 24$, $f(6) = 24 + 13 + 7 = 44$. Choice B miscounts by including some invalid strings. Choice C uses an incorrect recurrence. Choice D counts all binary strings without the restriction.
3. Let $P(n, k)$ denote the number of ways to partition a set of $n$ elements into exactly $k$ non-empty subsets (Stirling numbers of the second kind). The recursion is $P(n, k) = kP(n-1, k) + P(n-1, k-1)$. Given $P(3, 2) = 3$, what is $P(4, 2)$?
   Answer: 7 When you encounter Stirling numbers of the second kind, you're dealing with partitions of sets into non-empty subsets. The recursion $P(n, k) = kP(n-1, k) + P(n-1, k-1)$ captures two ways to place the nth element: either add it to one of the existing k partitions, or create a new partition containing just that element. To find $P(4, 2)$, apply the recursion: $P(4, 2) = 2P(3, 2) + P(3, 1)$. You're given that $P(3, 2) = 3$. For $P(3, 1)$, there's only one way to put all 3 elements into 1 subset, so $P(3, 1) = 1$. Therefore: $P(4, 2) = 2(3) + 1 = 7$. Looking at the wrong answers: Choice A (8) likely comes from incorrectly calculating $3 \times 3 - 1 = 8$, misremembering the recursion formula. Choice B (6) results from forgetting the $P(3, 1)$ term entirely and computing $2 \times 3 = 6$. Choice D (9) might arise from incorrectly using $3 \times 3 = 9$, perhaps confusing this with a different combinatorial formula. The correct answer is C (7). Study tip: Always write out the recursion formula explicitly and identify all needed base cases before substituting values. Stirling number problems often involve multiple recursive steps, so organize your work clearly to avoid arithmetic errors and ensure you're applying the correct formula.
4. A sequence $b_n$ counts the number of binary strings of length $n$ that do not contain two consecutive 1's. Given that $b_0 = 1$, $b_1 = 2$, and $b_2 = 3$, what is $b_5$?
   Answer: 13 The recursion is $b_n = b_{n-1} + b_{n-2}$ for $n \geq 2$. A valid string of length $n$ either ends in 0 (any valid string of length $n-1$ followed by 0) or ends in 01 (any valid string of length $n-2$ followed by 01). Computing: $b_3 = 2 + 3 = 5$, $b_4 = 3 + 5 = 8$, $b_5 = 5 + 8 = 13$. Choice A (11) incorrectly uses $b_4 + b_3$, choice C (16) doubles $b_4$, and choice D (21) is $b_8$.
5. Let $c_n$ count the number of ways to arrange $n$ distinct books on a shelf such that no book is in its original position (derangements). Given the recursion $c_n = (n-1)(c_{n-1} + c_{n-2})$ and $c_1 = 0$, $c_2 = 1$, what is $c_4$?
   Answer: 9 When you encounter a recursion problem about derangements, you're working with a fundamental counting principle where each term depends on previous terms. The key is to apply the given formula systematically, using the provided base cases. Given the recursion $c_n = (n-1)(c_{n-1} + c_{n-2})$ with $c_1 = 0$ and $c_2 = 1$, you need to build up to $c_4$ step by step. First, find $c_3$: $c_3 = (3-1)(c_2 + c_1) = 2(1 + 0) = 2$ Then calculate $c_4$: $c_4 = (4-1)(c_3 + c_2) = 3(2 + 1) = 3 \times 3 = 9$ Therefore, $c_4 = 9$, which is answer choice D. Looking at the wrong answers: Choice A (6) likely comes from incorrectly computing $c_3 = 3$ and then getting $c_4 = 3(1 + 2) = 9$, but making an arithmetic error to reach 6. Choice B (8) might result from forgetting the factor of $(n-1)$ and calculating $c_4 = c_3 + c_2 + c_1 + c_0$ with some assumed value. Choice C (11) could come from misapplying the recursion formula, perhaps adding the factor incorrectly as $c_4 = (c_3 + c_2) + (4-1) = 3 + 8 = 11$. When solving recursion problems, always work methodically from the base cases upward, double-check your arithmetic at each step, and make sure you're applying the exact formula given—don't try to shortcut or modify the recursion relation.
6. A sequence $s_n$ counts the number of subsets of $\{1, 2, \ldots, n\}$ that contain no two consecutive integers. Given $s_0 = 1$ and $s_1 = 2$, and the recursion $s_n = s_{n-1} + s_{n-2}$ for $n \geq 2$, what is $s_4$?
   Answer: 8 When you encounter problems about counting subsets with restrictions, think about how each new element affects your existing valid subsets. This is a classic application of recurrence relations in combinatorics. To find $s_4$, you need to understand why the recursion $s_n = s_{n-1} + s_{n-2}$ works. When building valid subsets of $\{1, 2, \ldots, n\}$, you have two cases: either include element $n$ or don't. If you don't include $n$, you can use any valid subset of $\{1, 2, \ldots, n-1\}$, giving you $s_{n-1}$ possibilities. If you do include $n$, you cannot include $n-1$ (no consecutive integers), so you can only use valid subsets of $\{1, 2, \ldots, n-2\}$, giving you $s_{n-2}$ possibilities. Now calculate step by step: - $s_0 = 1$ (just the empty set) - $s_1 = 2$ (empty set and $\{1\}$) - $s_2 = s_1 + s_0 = 2 + 1 = 3$ - $s_3 = s_2 + s_1 = 3 + 2 = 5$ - $s_4 = s_3 + s_2 = 5 + 3 = 8$ The answer is C) 8. Option A) 7 might come from miscounting or making an arithmetic error. Option B) 13 could result from incorrectly applying the recursion or confusing this with a different counting problem. Option D) 5 is actually $s_3$, suggesting you stopped one step too early. Study tip: With recurrence relations, always write out several terms carefully. The Fibonacci-like pattern here appears frequently in combinatorics problems involving restrictions.
7. The Tribonacci sequence satisfies $t_1 = 1$, $t_2 = 1$, $t_3 = 2$, and $t_n = t_{n-1} + t_{n-2} + t_{n-3}$ for $n \geq 4$. A modified version counts only those sequences where $t_n$ is even. Let $E_n = 1$ if $t_n$ is even, 0 otherwise. What is $\sum_{k=1}^{6} E_k$?
   Answer: 2 First compute the Tribonacci sequence: $t_1 = 1$ (odd), $t_2 = 1$ (odd), $t_3 = 2$ (even), $t_4 = 1+1+2 = 4$ (even), $t_5 = 1+2+4 = 7$ (odd), $t_6 = 2+4+7 = 13$ (odd). So $E_1 = 0$, $E_2 = 0$, $E_3 = 1$, $E_4 = 1$, $E_5 = 0$, $E_6 = 0$. Therefore $\sum_{k=1}^{6} E_k = 0+0+1+1+0+0 = 2$. Choice A miscounts parity, choice C counts all positive terms, choice D only counts one even term.
8. Let $a_n$ be the number of ways to tile a $2 \times n$ rectangle using $1 \times 2$ dominoes (which can be placed horizontally or vertically). Given that $a_1 = 1$ and $a_2 = 2$, what is $a_6$?
   Answer: 13 To tile a $2 \times n$ rectangle, we can either place a vertical domino in the last column (leaving a $2 \times (n-1)$ rectangle) or place two horizontal dominoes in the last two columns (leaving a $2 \times (n-2)$ rectangle). This gives us the recurrence $a_n = a_{n-1} + a_{n-2}$. Starting with $a_1 = 1$ and $a_2 = 2$, we get $a_3 = 3$, $a_4 = 5$, $a_5 = 8$, and $a_6 = 13$. Choice A gives $a_5$. Choice C is $a_7$. Choice D is $a_8$.
9. Let $a_n$ represent the number of ways to tile a $2 \times n$ rectangle using $1 \times 2$ dominoes. If $a_1 = 1$ and $a_2 = 2$, what is the value of $a_6$?
   Answer: 13 The recursive relation is $a_n = a_{n-1} + a_{n-2}$ for $n \geq 3$. To tile a $2 \times n$ rectangle, we can either place a vertical domino at the end (leaving a $2 \times (n-1)$ rectangle) or place two horizontal dominoes at the end (leaving a $2 \times (n-2)$ rectangle). Computing: $a_3 = 1 + 2 = 3$, $a_4 = 2 + 3 = 5$, $a_5 = 3 + 5 = 8$, $a_6 = 5 + 8 = 13$. Choice B (21) is $a_8$, choice C (8) is $a_5$, and choice D (34) is $a_9$.
10. Let $w(n)$ count the number of ways to write $n$ as an ordered sum of positive integers where each term is either 1 or a prime number. For example, $w(4) = 4$ since $4 = 1+1+1+1 = 1+1+2 = 1+2+1 = 2+1+1$. What is $w(7)$?
    Answer: 20 We use the recurrence $w(n) = w(n-1) + \sum_{p \leq n, p \text{ prime}} w(n-p)$. Computing step by step: $w(1) = 1$, $w(2) = 2$, $w(3) = 3$, $w(4) = 4$, $w(5) = 6$, $w(6) = 9$. Then $w(7) = w(6) + w(5) + w(4) + w(2) = 9 + 6 + 4 + 1 = 20$ (using primes 2, 3, 5). Choice A undercounts by missing some compositions. Choice B uses an incorrect set of allowed terms. Choice D overcounts by including composite numbers.
11. Consider sequences of length $n$ using the symbols A, B, C where no two consecutive symbols are the same, and the sequence cannot start with C. Let $g(n)$ denote the number of such sequences. If $g(1) = 2$ and $g(2) = 4$, what is $g(5)$?
    Answer: 36 Let $a_n$ be sequences ending in A, $b_n$ ending in B, $c_n$ ending in C. Then $a_n = b_{n-1} + c_{n-1}$, $b_n = a_{n-1} + c_{n-1}$, $c_n = a_{n-1} + b_{n-1}$, with $a_1 = 1, b_1 = 1, c_1 = 0$. Computing: $g(3) = 8$, $g(4) = 20$, $g(5) = 36$. Choice A ignores the restriction on starting with C. Choice C uses an incorrect recurrence relation. Choice D counts sequences that can start with any symbol.
12. Let $f(n)$ be the number of ways to climb $n$ stairs if you can take 1, 2, or 3 steps at a time. If $f(1) = 1$, $f(2) = 2$, and $f(3) = 4$, what is $f(6)$?
    Answer: 24 The recursion is $f(n) = f(n-1) + f(n-2) + f(n-3)$ for $n \geq 4$. To reach stair $n$, you can come from stair $n-1$ (1 step), $n-2$ (2 steps), or $n-3$ (3 steps). Computing: $f(4) = 1 + 2 + 4 = 7$, $f(5) = 2 + 4 + 7 = 13$, $f(6) = 4 + 7 + 13 = 24$. Choice B (13) is $f(5)$, choice C (7) is $f(4)$, and choice D (44) is $f(7)$.

Start this quiz