Discrete Mathematics (H) Lecture 13 Notes

Counting

Counting is the process of determining the number of some objects with certain properties.

The Sum Rule and The Product Rule

Example

• the number of steps in a computer program
• the number of passwords between 6~10 characters
• the number of telephone numbers with 8 digits

We usually simplify the solution of nontrivial counting problems by decomposing them into smaller ones:

Product Rule

If a count of elements can be broken down into a sequence of dependent counts where the first count yields elements, the second elements, and -th count elements, then the total number of elements is

Example

1. how many different bit strings of length 7 are there?
2. how many different functinos are there from a set with elements to a set with elements?
3. how many one-to-one functions are there from a set with elements to a set with elements?

Solution 1. Using the product rule, since each bit in the bit string has two possibilities, we have

Solution 2. Each of the  elements in the domain can map to any of the  elements in the codomain. Therefore, the total number of functions is: Solution 3. For a function to be one-to-one, each element in the domain must map to a distinct element in the codomain. This is only possible if . The number of such functions is given by the number of permutations of  elements taken  at a time:

Sum Rule

If a count of elements can be broken down into a set of independent counts where the first count yields elements, the second elements, and -th count elements, then the total number of elements is

Example

You need to travel from city A to B. You may either fly, take a train, or a bus. There are 12 different flights, 5 different trains and 10 buses. How many options do you have to get from A to B?

Solution. We may use the sum rule, so

More complex counting typically requires a combination of the sum and product rules.

Tree Diagrams

A tree is a structure that consists of a root, branches and leaves. We can use trees to represent counting problems and record the choices we made for alternatives.

Example

What is the number of bit strings of length 4 that do not have two consecutive 1’s?

Solution.

Pigeonhole Principle

Assume that there are a set of objects and a set of bins to store them. The pigeonhole principle states that if there are more objects than bins then there is at least one bin with more than one object. More formally:

Pigeonhole Principle

If there are and bins, then there is at least on bin with two or more objects.

Generalized Pigeonhole Principle

If objects are placed into bins, then there is at least one bin containing at least objects.

Bijections and Permutations

Definition: Permutation

A bijection from a set onto itself is called a permutation.

The following loop is a part of program to determine the number of triangles formed by points in the plane:

trianglecount = 0
for i = 1 to n
	for j = i+1 to n
		for k = j+1 to n
			if points i, j, k are not collinear
				trianglecount = trianglecount + 1

Among all iterations of line 5, what is the total number of times this line checks three points to see if they are collinear?

Solution. Since there is a triple for loop, and

• the second loop begins with and increases up to .
• the third loop begins with and increases up to .

Thus each triple with is examined exactly once. So we need to compute the number of increasing triples with . We claim that the number of increasing triples is exactly the same as the number of 3-element subsets from . This essentially means the function is a bijection. We prove this by

• one-to-one: if , then .
• onto: if is a 3-element subset then it can be written as where , so .

Bijection Principle

Two sets have the same size iff there is a one-to-one function from one set onto the other.

Inclusion-Exclusion Principle

Inclusion-Exclusion Principle

Suppose are sets, then

Proof by induction.

• Base case:

• Inductive step. The inductive hypothesis is

Let and , by the same formula we used in base case: The first term is given by i.h. For the third term, by distributive law, where . Then Note that So the inductive step holds.

Permutations and Combinations

Definition: -element Permutation of

The number of lists of distinct elements from is

Definition: -element Combination of

The number of sets of distinct elements from is It is also known as the binomial coefficients.

Some properties of binomial coefficients:

• is the number of -element subsets of an -element set.
• since there are only one set of size .
• since there are only one set of size .
• obvious from equation.

To prove the last property, we use the sum rule and the power sets:

Let be the set of all subsets of , and be the set of all -subsets of , then

Binomial Coefficients

The Pascal’s Triangle (or 杨辉三角): From the Pascal’s triangle, we can observe the identity:

Pascal Identity

Each (non-) entry in Pascal’s Triangle is the sum of the two entries directly above it (to left and to right), i.e.

Combinatorial Proof. is the number of -element subsets of an -element set. Therefore, each term represents the number of subsets of a particular size chosen from an appropriately sized set.

• represents the number of -subsets of an -element set.
• represents the number of -subsets of an -element set.

Observe that the set of all -element subsets can be partitioned into two parts:

• : set of -element subsets that contain .
• : set of -element subsets that don’t contain .

Where is arbitrarily chosen.

The Binomial Theorem

Binomial Theorem

For any integer

Proof by induction.

• Base case:

So the base case holds.

• Inductive step: Assume that some integers , the binomial theorem holds, then

This completes the inductive step.

Trinomial Coefficients

Question

Suppose we have labels for one kind, e.g., red, labels for another, e.g., blue, and labels of a third kind. In how many different ways can we apply these labels to objects?

Solution. There are ways to choose the red items, then there are ways to choose the blue items from the remaining . The remaining items get labelled a third color. Using the product rule, the total number of labellings is

When , we call a trinomial coefficient and denote it as

The Birthday Paradox

Question

Suppose that 25 students are in a room. What is the probability that at least two of them share a birthday?

Solution. Let denotes the event “there are students in a room and at least two of them share a birthday”. The sample space is then . Let denotes the event “there are students in a room and none of them share a birthday”. So we have: By using calculator we can find we only need to have !

For the probability: Then We may generalize this as Since , for , . Thus we have So we have Let be the smallest number of values we have to choose, s.t. the probability for finding a collision is at least . By inverting the expression above, we have

Euclidean Algorithm

The number of divisions requires to find is , where .

Proof idea. See the key steps in the Euclidean algorithm: We can observe that We claim that .

• Case 1. : then
• Case 2. : then