Lecture notes on counting, used in CS 70 Fall 2001(Paraphrased from Prof. Demmel’s Math 55 Lecture notes #15, #17) Review Counting Principles 1) The Sum Rule: If S1 and S2 are disjoint sets, then the number of members of S1 U S2 is |S1 U S2| = |S1| + |S2| 2) Inclusion-Exclusion Principle: If S1 and S2 are arbitrary sets, then |S1 U S2| = |S1| + |S2| - |S1 inter S2| 3) The Product Rule: If S1 and S2 are sets, and S1 x S2 ={(s1,s2) : s1 in S1 and s2 in S2} is the Cartesian product of S1 and S2, then |S1 x S2| = |S1| x |S2| If S1, S2, ... , Sk are sets, S1 x S2 x ... Sk the Cartesian product, then |S1 x ... x Sk| = |S1| x ... x |Sk| 4) Tree diagrams EX: How many bit strings of length 4 without two consecutive zeros? Ans: 8; Enumerate all possibilities in a tree: Legal bit strings 0 - 1 0101 / / 0 0110 0 - 1 - 1 - 1 0111 / / 0 1010 / 0 - 1 - 1 1011 / / 0 - 1 1101 / / / / 0 1110 x -----1 - 1 - 1 - 1 1111 Bit # 1 2 3 4 Tree Diagrams (formally) Draw a tree where the children of each node represent all the possible values of the next entry EX: How many 2-out-of-3 game playoffs are there? Ans: 6 Winner sequence Winner b bb b / / b bab b b - a - a baa a / / b abb b / / b - a aba a x -- a - a aa a (5) Pigeonhole Principle: If k+1 or more objects (pigeons) are placed in k boxes (holes), then at least one box contains 2 or more objects. (proof by contradition: if each box had at most one object, there would only be k or fewer objects, a contradiction) EX: In any group of 27 English words, at 2 begin with the same letter, since there are only 26 letters.7) Permuations DEF: a permutation of a set S of n distinct objects is an ordered list of these objects DEF: an r-permutation is an ordered list of r elements of S EX: S={1,2,3}, all permutations={(1,2,3),(2,1,3),(1,3,2),(2,3,1),(3,1,2),(3,2,1)} all 2-permutations={(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)} DEF: the number of r-permutations of a set S with n elements is P(n,r) Theorem: P(n,r) = n*(n-1)*(n-2)*...*(n-r+1) = n!/(n-r)! Proof: (product rule): there are n ways to choose the first in list, n-1 ways to choose second, ... , n-r+1 ways to choose rth EX: P(3,3)=3*2*1=6, P(3,2)=3*2=6 EX: how many different ways can a salesman visit 8 cities? P(8,8)=8!=40320 EX: How many different ways can 10 horses in a race win, place and show (come in first, second, third)? P(10,3) = 10*9*8 = 720 8) Combinations DEF: an r-combination from a set S is simply an unordered subset of r elements from S EX: S={1,2,3}, all 2-combinations={{1,2},{1,3},{2,3}} Comparing to all 2-permutations, we see we ignore order, DEF: C(n,r) = number of r-combinations from a set with n-elements Theorem: C(n,r) = n! / [ (n-r)! r! ] Proof: the set of all r-permutations can be formed from the set of all r-combinations by taking all r! orderings of each r-combination, so P(n,r)=r! * C(n,r), and C(n,r)=P(n,r)/r!= n! / [ (n-r)! r! ]= n*(n-1)*(n-2)*...*(n-r+1)/r! EX: C(3,2)=P(3,2)/2!=6/2=3 DEF C(n,r) also called binomial coefficient, written (n \\ r), pronounced "n choose r" Note that C(0,0)= 0!/0!*0! = 1; C(n,0)=C(n,n)=1 Corollary: C(n,r)=C(n,n-r) Proof: C(n,r)=n!/[(n-r)! r!] = n!/[ r! (n-r)!] = n!/[(n-(n-r))! (n-r)!] = C(n,n-r) EX C(3,1)=C(3,2)=1 DEF Pascal triangle: (0) (0) (1) (1) (0) (1) (2) (2) (2) (0) (1) (2) (3) (3) (3) (3) (0) (1) (2) (3) (4) (4) (4) (4) (4) (0) (1) (2) (3) (4) (5) (5) (5) (5) (5) (5) (0) (1) (2) (3) (4) (5) (6) (6) (6) (6) (6) (6) (6) (0) (1) (2) (3) (4) (5) (6) ... row sum 1 1 1 1 2 1 2 1 4 1 3 3 1 8 1 4 6 4 1 16 1 5 10 10 5 1 32 1 6 15 20 15 6 1 64 Note that to get any entry, you sum its neighbors to left above, right aboveEX: How many different desserts can you make out of 4 scoops of ice cream, each of which may be chocolate (C), vanilla (V) or strawberry (S)? Here are the 15 possibilities: CCCC VVVV SSSS CCCV VVVC SSSC CCCS VVVS SSSV CCVS VVCS SSCV CCVV VVSS CCSS Here is a more systematic way to get the answers: we will represent each dessert by a sequence of 4 stars (representing the 4 scoops) and 2 bars (dividing the starts into 3 groups: C, V and S). Here are some examples: **|*|* represents 2 Cs, 1 V and 1 S *|**|* represents 1 C , 2 V’s and 1 S *|***| represents 1 C , 3 V’s and 0 S’s |****| represents 0 C , 4 V’s and 0 S’s ||**** represents 0 C , 0 V’s and 4 S’s etc The idea is that every sequence of 4 stars and 2 bars represents exactly one dessert. How many such sequences are there? The idea is that we take 6 possible possible positions (for 4 stars and 2 bars) and choose 2 of them for bars. There are C(6,2) = 6!/(2! 4!) = 15 ways to do this. Here is the general result: Theorem: Suppose I have n types of objects ("flavors"). How many differnt sets ("desserts") consisting of r objects ("scoops") are there? The answer is C(n+r-1,n-1).
View Full Document
Unlocking...