MAT344H1 Lecture Notes - Lecture 14: Disjoint Sets
Document Summary
Q: suppose you have 3 dogs, 4 lizards, 3 monkeys. You want to assemble a jazz quartet with 2 players from 2 different species. 3c2 * 4c2 + 3c2 * 3c2 + 4c2 * 3c2 = 45. Addition principle: if you are choosing a single option from disjoint sets with choices respectively. Q: how many rearrangements of the letters ysstems, temssys, etc. 7 choose 4 ways of placing non s letters: 7c4 * 4! 7 choose 3 ways of placing s letters: 7c3 * 4! Def: a permutation of numbers 1 through n is an rearrangement/reordering. Def: a r combination of [1 n] is a subset of size r where two combinations [1, 2] is the same as.
