MAT344H1 Lecture Notes - Lecture 15: Bijection
Document Summary
Permutation is an arrangements = ordering of a set of distinct elements r-combinations = r-selections = choices of an r element subset of [1 n] (1) ex. Number of permutation of n element set = n(n-1)(n-2) . (2). 1 = n! Number r combinations of n of set = Proof: start by choosing for r = 2, n = 4 then for example (1), 4c2 = 6. We can enumerate r combinations of a set of n elements by enumerating permutation of n elements and selecting 1st r elements as our r combination. So we need to divide them by r!. a. = using addition principle b. i. i. c. Number of ways to choose r elements from [1 n], ways of choosing r elements from [2 . n] + ways of choosing r elements [1 n] s. t. Here a bijection {n-r elements subsets} is complement of {r element subsets of [1 n]}
