COMP 1002 Unit 8 overview
In this unit we will talk about counting, including combinatorics and cardinalities of infinite sets; we will also look more closely at functions and their types. We will start with general counting rules (rules of sum and product), then talk about counting various permutations and combinations of items. Then we will look at inclusion-exclusion principle, proving it using the binomial theorem. After covering types of functions, we will show how to compare sizes of infinite sets, and talk about uncountable sets and unsolvable problems.
Readings
Combinatorics part of this unit is covered in sections 6.1, 6.3, 6.4 and 6.5 in the textbook. Functions and set cardinalities are in 2.3 and 2.5, and generalized inclusion-exclusion principle in 8.5.
Learning objectives
You will learn to count combinations and permutations of objects, with and without repetition and indistinguishable objects, and compute the number of variants using rules of sum and product. You will see how to use combinations in binomial theorem, to make it easy to open parentheses in $(x+y)^n$, and use recursive definition of combinations by Pascal triangle to compute them. You will also see the inclusion-exclusion principle for counting the number of elements in unions of sets, and its proof using the binomial theorem.
We will then define functions, and talk about functions that are one-to-one, onto and bijections, as well as function composition and inverse. Then, we will use the notion of bijection to talk about sizes of infinite sets, showing that a number of sets have the same cardinality as natural numbers (countable sets), yet other sets are uncountable.
Specifically, you will learn to do the following.
- Count the number of permutations of objects and number of ways to select n objects out of k choices with and without order and repetitions.
- Calculate binomial coefficients in an expansion of (x+y)n, using the formulas for the number of combinations as well as Pascal triangle, and determine the sum of binomial coefficients and alternating binomial coefficients.
- Determine the number of elements in a union of n sets give the number of elements in the sets and all their intersections.
- Identify if a given relation is a function, and if so, state what its domain, codomain and range are, and what are the image and preimage of specific elements.
- Identify if a function is total, one-to-one, onto, or a bijection. Give examples of functions with different combinations of these properties, both on a finite domain and on integers.
- Compute composition of functions and inverse of a function.
- Use bijections to compare cardinalities of sets, in particular to prove that sets are countable. Learn that the sets of all integers, all rational numbers and all finite strings over a given finite alphabet are countable, and how to prove that.
- Arrange strings in a string order, as used in proofs of countability.
- Use diagonalization technique to show that some infinite sets are uncountable. Learn that the set of all real numbers, all languages, and in general a power set of a countable sets are uncountable, and how to prove that.
- Give an example of an unsolvable computational problem: the Halting problem.
Vocabulary
You need to know the meaning of the following terminology (and respective notation):
- Rules of sum and product
- Permutations, r-permutations, combinations, combinations with repetition.
- Binomial theorem, binomial coefficients, Pascal triangle
- Principle of inclusion-exclusion
- Function, its domain, codomain, range. Image(x), preimage(y).
- Total vs partial functions, one-to-one, onto, bijection.
- Composition and inverse of functions
- Countable and uncountable sets.
- Halting problem
-