Discrete Math Chapter 7 - Counting
Discrete Math Chapter 7 - Counting
The Counting Basics
The Sum Rule
A count decomposes into a set of independent counts.
Elements of different counts are alternatives.
Example: To travel from city A to B, you may either fly, or take a train, or take a bus. There are 12 different flights, 5 different trains and 10 different buses. How many options do you have to travel from A to B?
The Sum Rule: If a count of elements can be broken down into a set of independent counts, where the first count yields $n_1$ elements, the 2nd $n_2$ elements, and $k$th $n_k$ elements, then the total number of elements is $n = n_1 + n_2 + … + n_k$ .
The Product Rule
A count decomposes into a sequence of dependent counts.
Each element in one count is associated with all elements of the next count.
Example: In an auditorium, the seats are labeled by a letter and numbers between 1 and 50 (e.g., A23). What is the total number of seats?
The Product Rule: If a count of elements can be broken down into a sequence of dependent counts, where the first count yields $n_1$ elements, the 2nd $n_2$ elements, and $k$-th $n_k$ elements, then the total number of elements is $n = n_1 × n_2 × … × n_k$ .
Other Rules
The Subtraction Rule
If a task can be done in $n_1$ or $n_2$ ways, then the number of ways to do the task is $n1 + n2$ minus the number of ways to do the task that are common to the two ways. E.g.,
The Division Rule
If a task can be done using a procedure that can be carried out in n “fine-grained” ways, and every “giant” way $w$ corresponds to exactly $d$ of the $n$ “fine-grained” ways, then there are $n∕d$ “giant” ways to do it. E.g., how many kilobytes in one gigabyte?
More Complex Counting
Typically, a counting problem requires a combination of more than one rule. Example: Each password is 6 to 8 characters long, where each character is a lowercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there?
Tree Diagram
A tree is a structure that consists of a root, branches and leaves. It can represent a counting problem and record the choices we made for alternatives, with the possible outcomes on the leaves.
Example: What is the number of bit strings of length 4 that do not have consecutive 1s?
Example: The first team that wins 3 out of 5 games wins the playoff. In how many different ways can the playoff occur?
The Pigeonhole Principle
If a flock of 13 pigeons flies into a set of 12 pigeonholes to roost, then at least one pigeonhole must have at least two pigeons in it.
The Pigeonhole Principle
If $k$ is a positive integer and $k + 1$ or more objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.
proof by contradiction.
The Generalized Pigeonhole Principle
If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least $⌈N∕k⌉$ objects.
proof by contradiction.
Example
We had 99 registered students in the beginning of this semester. At least how many of them were born in the same month?
Now we have 96 students left. What about now?
Permutations and Combinations
Many counting problems can be solved by finding the number of ways to arrange or select some distinct elements from a set.
A permutation of a set of distinct objects is an ordered arrangement of these objects.
• E.g., in how many ways can we select three students from a group of five students and arrange them to stand in line for a picture?
A combination of a set of distinct objects is an unordered selection of these objects.
• E.g., how many different committees of three students can be formed from a group of five students?
r-Permutations and r-Combinations
An ordered arrangement of $r$ distinct elements from a set of size $n$ is called a r-permutation.
• An n-permutation of a set of size n is simply called a permutation.
Example: What are the 3-permutations of {1, 2, 3, 4}?
• This type of “dictionary” ordering (where we treat numbers as letters) is called a lexicographic ordering and is used quite often.
An unordered selection of $r$ distinct elements from a set of size $n$ is called a r-combination.
Example: what are the 3-combinations of {1, 2, 3, 4}?
r-Permutation
Theorem: Let $n, r$ be integers and $0 ≤ r ≤ n$, then there are $P(n, r) = n(n − 1)(n − 2) ··· (n − r + 1) = \dfrac {n!} {(n – r)!}$ r-permutations of a set with n distinct elements.
• Note that $P(n, 0) = 1$, i.e., there is one way to order $0$ element
Proof: There are n choices for the first number. For each way of choosing the first number, there are $n − 1$ choices for the second number.
…
For each way of choosing the first $r – 1$ numbers, there are $n − r + 1$ choices for the $r$-th number.
Therefore, by the product rule, there are $n(n − 1)(n − 2) ··· (n − r + 1)$ r-permutations, which is equal to $\dfrac {n!} {(n – r)!}$ .
r-Combination
Theorem: Let $n, r$ be integers and $0 ≤ r ≤ n$, then there are $C(n, r) = P(n, r) / P(r, r) = \dfrac {n!}{r! (n – r)!}$ r-combinations of a set with n distinct elements.
• Note that $C(n, 0) = 1$, i.e., there is one way to choose $0$ element
Proof: Since the order of elements in an $r$-combination does not matter and there are $P(r, r)$ different ways to order the $r$ elements in an $r$-combination
each of the $C(n, r)$ $r$-combinations corresponds to exactly $P(r, r)$ r-permutations.
Therefore, by the division rule, we have $C(n, r) = P(n, r) / P(r, r) = n! / r! (n – r)! $
The Birthday Problem
The Birthday Paradox
Suppose that 23 students are in a room. What is the probability that at least two of them share a birthday?
• It’s greater than a half!
Assume a year has 365 days and there are no twins in the room. Calculate the probability as follows:
• Sample space: $|S| = 365^n$ * all cases occur equally likely
$A_n$ : “for $n$ students in a room $≥ 2$ of them share a birthday”
$B_n$ : “for $n$ students in a room none of them share a birthday”
Number of $A_n=a$,
Number of $B_n=b=C(365,n)=365\times364\times…\times(365-(n-1))$
So, we have $a+b=|S|=365^n$
And $Pr[A_n]=\dfrac{a}{|S|}=1-\dfrac{b}{|S|}$
The Birthday Attack
In cryptography, the birthday attack is an attack that uses the probabilistic model shown in the birthday problem to reduce the complexity of finding a collision for a hash function.
Assume a hash function has independent random outputs.
Each hash output can be viewed as a student’s birthday.
Q: What is the smallest number of inputs that we have to choose such that the probability of finding a hash collision is ≥ p?
Let $H$ be the number of possible hash outputs.
The collision probability when choosing $n$ random hash outputs is
Since $e^x=1+x+\dfrac{x^2}{2!}+…$, for $|x|<<1$, $e^x \approx 1+x$
Thus, we have
By iterating, we have the smallest number $n$ :
Binomial Coefficients and Identities
Binomial Coefficients
$Theorem$: For integers $n$ and $k$ with $0 ≤ k ≤ n$, the number of $k$-element subsets of an $n$-element set is
Properties:
Pascal’s Triangle
Take the table and shift each row slightly such that middle element is in the center.
Each (non-1) entry in Pascal’s triangle is the sum of the two entries directly above it.
Pascal’s identity:
A Combinatorial Proof:
Let $S1$ be the set of all $k$-element subsets and $x_n$ be the $n$-th element.
Partition $S1$ into $S2$ and $S3$ and apply the sum rule:
S2: the set of $k$-element subsets that contain $x_n$.
S3: the set of $k$-element subsets that don’t contain $x_n$.
The Binomial Theorem
Let $x$ and $y$ be variables, and let $n$ be a nonnegative integer. Then
Let $x=y=1$, we have $\sum^n_{k=0}\binom{n}{k}=2^n$
Let $x-1,y=-1$, we have $\sum^n_{k=0}(-1)^k\binom{n}{k}=0$
Let $y=1$, we have $\sum^n_{k=0}\binom{n}{k}x^k=(1+x)^n$
Why the name “binomial coefficients”?
Because those numbers occur as coefficients in the expansion of powers of binomial expressions such as $(x + y)^n$
Trinomial Coefficients
What is the coefficient of $x^{k1}$ $y^{k2}$ $z^{k3}$ in $(x + y + z)^n$ ?
If we have $k_1$ red labels, $k_2$ blue labels, and $k_3 = n − k_1 − k_2$ purple labels, then in how many different ways can we apply these labels to $n$ objects?
How many ways to choose the $k_1$ red items? How many ways to choose the $k_2$ blue items from the remaining $n − k_1$ items? Finally, the remaining $k_3 = n – k_1 – k_2$ items get labelled purple.
If $k_1 + k_2 + k_3 = n$, we call $\dfrac{n!}{k_1!k_2!k_3!}$ a trinomial coefficient and denote it as
Inclusion-Exclusion
The Inclusion-Exclusion Principle
The principle is used in counts where the decomposition yields two dependent counting tasks with overlapping elements
If we use the sum rule, some elements would be counted twice.
The principle uses the subtraction rule to correct for the overlapping elements after the sum.
Two-set case:
Three-set case:
$E ∩ F, E ∩ G, F ∩ G$ got counted twice and then deducted once
$E ∩ F ∩ G$ got counted three times then deducted three times and finally got counted once
The Principle of Inclusion-Exclusion: Let $E_1, E_2, …, E_n$ be finite sets, then
Proof by induction: omitted.
The Number of Onto Functions
We can use this principle to find the number of onto functions:
Let A, B be two sets with $|A| = m$ and $|B| = n$.
$number\ of\ (a)$ : the number of onto functions from A to B
$number\ of\ (b)$ : the number of non-onto functions from A to B, i.e., functions with at least one element of B having no preimage
Since there are $nm$ functions from A to B, we have $number\ of\ (a) + number\ of \ (b) = nm$.
So, in order to find $number\ of\ (a)$, we only need to calculate $number\ of\ (b)$.
Ei : set of functions such that the $i$-th element of B has no preimage
Consider any index list i1, i2, …, ik . How many such lists of size k? Functions in do not map to these k elements of B, so there are (n – k)m such functions in total. Therefore,
Solving Linear Recurrence Relations
Linear Recurrence Relations
Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form
where $c_1, c_2, …, c_k$ are real numbers, and $c_k ≠ 0$.
linear: it is a linear combination of previous terms
homogeneous: all terms are multiples of $a_j$ s
degree $k$ : an is expressed by the previous k terms
constant coefficients: coefficients are constants
By induction, such a recurrence relation is uniquely determined by this recurrence relation, and $k$ initial conditions $a_0, a_1, …, a_k−1$.
Solving Recurrences of Degree 2
Consider an arbitrary linear homogeneous relation of degree 2 with constant coefficients:
The characteristic equation (CE) is:
Theorem:
If this CE has two distinct roots $r1, r2$, then a sequence ${an}$ is a solution of the recurrence relation if and only if
where $α_1, α_2$ are constants
Solving Recurrences of Degree k
Consider an arbitrary linear homogeneous relation of degree k with constant coefficients:
The characteristic equation (CE) is:
Theorem:
If this CE has $k$ distinct roots $r_1, r_2 , ···, r_k$ , then the solutions to the above recurrence is of the form $a_n = α_1 · r_1^n + α_2 · r_2^n + ··· + α_k · r_k^n$ for $n ≥ 0$, where $α1, α2, …, αk$ are constants.
The Case of Degenerate Roots
Theorem:
If the CE $r^2 − c_1 · r − c2 = 0$ has only one root $r_0$ (i.e., with multiplicity 2), then
for $n ≥ 0$, where $α1, α2$ are constants.
Theorem:
Suppose the CE $r^k − c_1 · r^(k–1) − ··· − c_k = 0$ has $t$ distinct roots $r_1, …, r_t$ with multiplicities (重数) $m_1, …, m_t$ respectively
Where $m_i\geq1, m_1 + ··· + m_t = k$.
Then for $n ≥ 0$, where $α_{i,j}$ are constants.
Solving Nonhomogeneous Recurrences
Theorem: If $a_n = p(n)$ is any particular solution to the linear nonhomogeneous relation with constant coefficients
Then all its solutions are of the form $a_n = p(n) + h(n)$
where $a_n = h(n)$ is any solution to the associated homogeneous recurrence relation
Generating Functions
Definition
The generating function for the sequence ${ak}$ of real numbers is the infinite series
Geometric seires sum:
We use generating functions to characterize sequences:
$\sum^\infty_{k=0}3x^k$ is the generating function for the sequence ${a_k}$ with $a_k = 3$
$\sum^\infty_{k=0}2^kx^k$ is the generating function for the sequence ${a_k}$ with $a_k = 2^k$
Operations of Generating Functions
Let $f(x)=\sum^{\infty}{k=0}a_kx^k$ and $g(x)=\sum^{\infty}{k=0}b_kx^k$
The Case of Finite Sequences
Definition: The generating function for the finite sequence $a_0, a_1, …$, an of real numbers is a polynomial of degree $n$
A finite sequence $a0, a_1, …, a_n$ can be easily extended to infinity by setting $a{n+1} = a_{n+2} = ··· = 0$
Useful Generating Functions
Solving Recurrences with $G(x)$
Using generating functions to solve recurrence relations:
Step 1: Based on the given recurrence and its initial conditions, find its generating function $G(x)$ as an explicit formula.
Step 2: Rewrite $G(x)$ as the summation of an infinite (or finite) series.
Exercises
1. Answer the following questions:
How many different bit strings of length 7 are there?
How many different functions from a set with $m$ elements to a set with $n$ elements?
How many injective functions from a set with $m$ elements to a set with $n$ elements ($m ≤ n$)?
put $m$ elements to $n$ place $\longrightarrow $ $P(n,m)=\dfrac{n!}{(n-m)!}$
How many onto functions from a set with $m$ elements to a set with $n$ elements ($m ≥ n$)?
2. How many bit strings of length 8 that start with a ‘1’ bit or end with the two bits ‘00’?
It is easy to count bit strings starting with ‘1’: $2^7$
It is easy to count bit strings ending with ‘00’: $2^6$
Deduct the overcounted number of strings starting with ‘1’ and ending with ‘00’: $2^5$
3. Are these linear homogeneous recurrence relations?
Yes, of degree $1$
Yes, of degree $2$
No, not linear
No, not homogeneous
Yes, but coefficients are not constants
4. Solve the recurrence:
With $a_0 = 2, a_1 = 1$ .
The characteristic equation (CE) is
Two roots are $2$ and $5$. So, assume that $a_n = α_1 · 2^n + α_2 · 5^n$
By the two initial conditions, we have
We get $α_1 = 3$ and $α_2 = −1$.
Therefore $a_n = 3 · 2^n − 5^n$
5. What is the closed-form expression of Fibonacci sequence $F_n$ ?
Consider the characteristic equation (CE): $x^2 – x + 1 = 0$. There are two different roots
6. Solve the recurrence:
with $a_0 = 1, a_1 = 0$
CE: $x^2=4x-4$
Root: $r=2$ with multiplicity 2
7. Solve the recurrence:
with $a_1 = 3$
The characteristic equation (CE) of the associated linear homogeneous recurrence relation is
The root is 3. So, assume an = p(n) is a particular solution to the original recurrence relation, then all of its solutions are of the form
It is natural to try a degree-1 polynomial, i.e., $p(n) = cn + d$. Then,
We have $c =(2c+2),d=2d-3c$
We get $c = –1$ and $d = −3/2$.
Therefore, $a_n = α_1 · 3^n − n − \dfrac{3}{2}$.
By the initial condition $a_1 = 3α_1 − 1 − 3/2 = 3$, we get $α_1 = 11/6$.
8. Solve
with $a_0 = 6, a_1 = 30$
Let $G(x)$ be the generating function of $a_k$
Multiply both side with $x^k$ and sum over $k\geq 2$
For the LHS, $\sum^\infty_{k=2}a_kx^k=G(x)-a_0-a_1$
For the RHS,
We have
