Create Presentation
Download Presentation

Download Presentation
## Counting I: One To One Correspondence and Choice Trees

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Hint: Count without counting!**How many seats in this auditorium?**If I have 14 teeth on the top and 12 teeth on the bottom,**how many teeth do I have in all?**Addition Rule**• Let A and B be two disjoint, finite sets. • The size of AB is the sum of the size of A and the size of B.**Corollary (by induction)**• Let A1, A2, A3, …, An be disjoint, finite sets.**S Set of all outcomes where the dice show different**values.S = ? • Ai set of outcomes where the black die says i and the white die says something else.**S Set of all outcomes where the dice show different**values.S = ? • T set of outcomes where dice agree.**S Set of all outcomes where the black die shows a**smaller number than the white die. S = ? • Ai set of outcomes where the black die says i and the white die says something larger.**S Set of all outcomes where the black die shows a**smaller number than the white die. S = ? • L set of all outcomes where the black die shows a larger number than the white die. • S + L = 30 • It is clear by symmetry that S = L. • Therefore S = 15**Let’s put each outcome in S in correspondence with an**outcome in L by swapping the color of the dice. S L Pinning down the idea of symmetry by exhibiting a correspondence.**Pinning down the idea of symmetry by exhibiting a**correspondence. Let’s put each outcome in S in correspondence with an outcome in L by swappingthe color of the dice. • Each outcome in S gets matched with exactly one outcome in L, with none left over. • Thus:S = L.**Let f:A®B be a function from a set A to a set B.**• f is 1-1 if and only if • x,yÎA, x ¹ y Þ f(x) ¹ f(y) • f is onto if and only if • zÎB xÎA f(x) = z**Let f:A®B be a function from a set A to a set B.**• f is 1-1 if and only if • x,yÎA, x ¹ y Þ f(x) ¹ f(y) • f is onto if and only if • zÎB xÎA f(x) = z There Exists For Every**A**B Let’s restrict our attention to finite sets.**A**B 1-1 Onto Correspondence(just “correspondence” for short)**Correspondence Principle**• If two finite sets can be placed into 1-1 onto correspondence, then they have the same size.**Correspondence Principle**• If two finite sets can be placed into 1-1 onto correspondence, then they have the same size. It’s one of the most important mathematical ideas of all time!**Question: How many n-bit sequences are there?**• 000000 0 • 000001 1 • 000010 2 • 000011 3 • . • . • 1…11111 2n-1 • 2n sequences**S = a,b,c,d,e has many subsets.**• a, a,b, a,d,e, a,b,c,d,e, e, Ø, … The empty set is a set with all the rights and privileges pertaining thereto.**Question: How many subsets can be formed from the elements**of a 5-element set? b c, e1 means “TAKE IT”0 means “LEAVE IT”**Question: How many subsets can be formed from the elements**of a 5-element set? Each subset corresponds to a 5-bit sequence**S = a1, a2, a3,…, anb = b1b2b3…bn**f(b) = ai | bi=1 **f is 1-1: Any two distinct binary sequences b and b’ have**a position i at which they differ. Hence, f(b) is not equal to f(b’) because they disagree on element ai. f(b) = ai | bi=1 **f is onto: Let S be a subset of {a1,…,an}. Let bk = 1 if**ak in S; bk = 0 otherwise. f(b1b2…bn) = S. f(b) = ai | bi=1 **I own 3 beanies and 2 ties. How many different ways can I**dress up in a beanie and a tie?**A restaurant has a menu with 5 appetizers, 6 entrees, 3**salads, and 7 desserts. • How many items on the menu? • 5 + 6 + 3 + 7 = 21 • How many ways to choose a complete meal? • 5 * 6 * 3 * 7 = 630**A restaurant has a menu with 5 appetizers, 6 entrees, 3**salads, and 7 desserts. • How many ways to order a meal if I might not have some of the courses? • 6 * 7 * 4 * 8 = 1344**Leaf Counting Lemma**• Let T be a depth n tree when each node at depth 0 i n-1 has Pi children. The number of leaves of T is given by: • P0P1P2…Pn-1**0**0 0 0 1 1 1 1 0 1 0 1 0 1 Choice Tree for 2n n-bit sequences We can use a “choice tree” to represent the construction of objects of the desired type.**0**0 0 0 1 1 1 1 0 1 0 1 0 1 2n n-bit sequences 011 101 111 010 100 110 001 000 Label each leaf with the object constructed by the choices along the path to the leaf.**0**0 0 0 1 1 1 1 0 1 0 1 0 1 2 choices for first bitX 2 choices for second bitX 2 choices for third bit …X 2 choices for the nth**A choice tree is a rooted, directed tree with an object**called a “choice” associated with each edge and a label on each leaf.**A choice tree provides a “choice tree representation”**of a set S, if • Each leaf label is in S • Each element of S occurs on exactly one leaf**We will now combine the correspondence principle with the**leaf counting lemma to make a powerful counting rule for choice tree representation.**Product Rule**• IF S has a choice tree representation with P1 possibilities for the first choice, P2 for the second, and so on, • THEN • there are P1P2P3…Pn objects in S • Proof: The leaves of the choice tree are in 1-1 onto correspondence with the elements of S.**Product Rule**• Suppose that all objects of a type S can be constructed by a sequence of choices with P1 possibilities for the first choice, P2 for the second, and so on. • IF • 1) Each sequence of choices constructs an object of type S • AND • 2) Each object has exactly one sequence which constructs it • THEN • there are P1P2P3…Pn objects of type S.**How many different orderings of deck with 52 cards?**• What type of object are we making? • Ordering of a deck Construct an ordering of a deck by a sequence of 52 choices: 52 possible choices for the first card; 51 possible choices for the second card; 50 possible choices for the third card; … 1 possible choice for the 52cond card.**How many different orderings of deck with 52 cards?**• By the product rule: • 52 * 51 * 50 * … * 3 * 2 * 1 = 52! • 52 “factorial” orderings**A permutation or arrangement of n objects is an ordering of**the objects. • The number of permutations of n distinct objects is n!**How many sequences of 7 letters contain at least two of the**same letter? 267 - 26*25*24*23*22*21*20**Sometimes it is easiest to count the number of objects with**property Q, by counting the number of objects that do not have property Q.**Let P(x): *! {True, False} be any predicate. We can**associate P with the set: Pset = {x2* | P(x) }