Discrete Structures · Unit 5 · 9 hrs
Counting and Discrete Probability
Exam-focused notes for Counting and Discrete Probability (Discrete Structures, CSC165): what the TU syllabus asks and how it has actually been tested, with 14 solved past questions from this unit.
What this unit covers
- Counting
- Basics of Counting
- Pigeonhole Principle
- Permutations and Combinations
- Two Element Subsets
- Counting Subsets of a Set
- Binomial Coefficients
- Generalized Permutations and Combinations
- Generating Permutations and Combinations
- Discrete Probability
- Introduction to Discrete Probability
- Probability Theory
- Probability Calculation in Hashing
- Expected Value and Variance
- Randomized Algorithms
- Advanced Counting
- Recurrence Relations
- Solving Recurrence Relations (Homogeneous and Non-Homogeneous equations)
- Introduction to Divide and Conquer Recurrence Relations
Pigeonhole Principle
State sum rule and product rule. If 26 integers are chosen from the set of consecutive integers {1,2,3,...,50}, prove that there are sure to be two numbers so that one is multiple of the other. [5]
Sum Rule: If a task can be done in one of $n1$ ways or one of $n2$ ways, where none of the set of $n1$ ways is the same as any of the set of $n2$ ways, then there are $n1 + n2$ ways to do the task. Product Rule: If a task can be broken down into a sequence ...
Full solved answer →State pigeonhole principle. Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$, with initial conditions $a_1 = 1$ and $a_2 = 3$.[10]
- Recurrence: $an = 5a{n-1} - 6a{n-2}$ - Initial conditions: $a1 = 1$, $a2 = 3$ --- Statement: If $k+1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects. Generalized form: If $N$ objects are placed into $k$ boxes...
Full solved answer →Show that if there are 30 students in a class, then at least two have same names that begin with the same letter. Explain the pascal's triangle. [5]
- Number of students = 30 - Number of letters in the English alphabet = 26 --- Statement: If $n$ objects are placed into $k$ boxes and $n k$, then at least one box contains two or more objects. More generally, if $n$ objects are placed into $k$ boxes, then ...
Full solved answer →Solving Recurrence Relations
Solve the recurrence relation $a_n = a_{n-1} + 2a_{n-2}$ with initial conditions $a_0 = 2$ and $a_1 = 7$. [5]
- Recurrence: $an = a{n-1} + 2a{n-2}$ - Initial conditions: $a0 = 2$, $a1 = 7$ --- This is a linear homogeneous recurrence with constant coefficients. Assume $an = r^n$: $$r^n = r^{n-1} + 2r^{n-2}$$ Divide by $r^{n-2}$: $$r^2 = r + 2 \implies r^2 - r - 2 = ...
Full solved answer →Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$, with initial conditions $a_0 = 1$, $a_1 = 4$. [5]
$$an = 5a{n-1} - 6a{n-2}, \quad a0 = 1,\ a1 = 4$$ Characteristic equation. Assume $an = r^n$: $$r^2 = 5r - 6 \implies r^2 - 5r + 6 = 0$$ Roots: $$(r-2)(r-3) = 0 \implies r1 = 2,\ r2 = 3$$ Distinct roots, so the general solution is: $$an = \alpha1 \cdot 2^n ...
Full solved answer →Question
State pigeonhole principle. Solve the recurrence relation $a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}$, with initial conditions $a_0 = 1, a_1 = 3, a_2 = 7$. [10]
- Recurrence: $an = 3a{n-1} - 3a{n-2} + a{n-3}$ - Initial conditions: $a0 = 1,\ a1 = 3,\ a2 = 7$ --- Statement: If $n$ objects are placed into $k$ boxes and $n k$, then at least one box contains two or more objects. Generalized form: If $N$ objects are plac...
Full solved answer →Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$, with initial conditions $a_1 = 1$ and $a_2 = 2$. [5]
- Recurrence: $an = 5a{n-1} - 6a{n-2}$ - Initial conditions: $a1 = 1$, $a2 = 2$ This is a linear homogeneous recurrence of degree 2 with constant coefficients. --- Substitute $an = r^n$: $$r^2 = 5r - 6 \implies r^2 - 5r + 6 = 0$$ Factor: $$(r-2)(r-3) = 0 \i...
Full solved answer →Linear Homogeneous Recurrence Relation with Constant Coefficients
A linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form:
$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$
where $c_1, c_2, \ldots, c_k$ are constants and $k$ is the order of the recurrence relation.
To solve such a recurrence relation, we use the characteristic equation method:
- Assume a solution of the form $a_n = r^n$
- Substitute into the recurrence relation to get the characteristic equation
- Solve for the roots $r$
- The general solution depends on the nature of the roots (distinct, repeated, or complex)
- Recurrence: $an = 6a{n-1} - 9a{n-2}$ - Initial conditions: $a0 = 1$, $a1 = 6$ All data present. No missing values. A linear homogeneous recurrence relation of degree $k$ with constant coefficients has the form: $$an = c1 a{n-1} + c2 a{n-2} + \cdots + ck a...
Full solved answer →Permutations and Combinations
When do we use permutation rather than combination? How many 5-digit numbers can be generated using the digits 0 to 9, if each number starts with 98 and no digit appears more than once? [5]
We use a permutation when the order of arrangement matters, i.e., when different orderings of the same selected items are counted as distinct outcomes. We use a combination when only the selection matters and order is irrelevant. Formulas: - Permutation: $P...
Full solved answer →How many 3 digits numbers can be formed from the digits 1,2,3,4 and 5 assuming that:a. Repetitions of digits are allowed b. Repetitions of digits are not allowed [5]
- Available digits: $\{1, 2, 3, 4, 5\}$ → 5 digits - Number to form: 3-digit number (Hundreds, Tens, Units) Multiplication Rule: if positions can be filled in $n1, n2, n3$ ways, total = $n1 \times n2 \times n3$. --- Each of the 3 positions can independently...
Full solved answer →List any two applications of conditions of probability. You have 9 families you would like to incite to a wedding. Unfortunately, you can only invite 6 families. How many different sets of invitations could you write? [5]
- Total families available: $n = 9$ - Families to be invited: $r = 6$ - Order does not matter (a set of invitations), so this is a combination problem. --- Conditional probability $P(AB)$ is the probability of event $A$ occurring given that event $B$ has al...
Full solved answer →Binomial Coefficients
What is the coefficient of $x^2$ in $(1+x)^{11}$? Describe how relation can be represented using matrix. [5]
- Expression: $(1+x)^{11}$ - Required: coefficient of $x^2$ - Second task: describe matrix representation of a relation --- By the Binomial Theorem: $$(1+x)^n = \sum{k=0}^{n} \binom{n}{k} x^k$$ The term containing $x^k$ has coefficient $\binom{n}{k}$. For $...
Full solved answer →Randomized Algorithms
What does probability testing means? Describe how Fermat's Little Theorem tests for a prime number with suitable example. [5]
Probability testing (also called probabilistic primality testing) is a method of determining whether a given integer is prime, not with absolute certainty, but with a high degree of probability. Instead of checking all possible divisors (which is computatio...
Full solved answer →Basics of Counting
What is product rule? How many strings are there of four lowercase letters that have the letter x in them? [5]
- Alphabet size: 26 lowercase letters - String length: 4 - Condition: string must contain the letter 'x' (at least once) - Repetition of letters: allowed (standard assumption for such strings) All data required is present. --- Definition: If a procedure can...
Full solved answer →Make Unit 5 stick
Practice CSC165 with flashcards & quizzes