Ch.9: Counting and Probability

Chapter 9 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 9.1. Introduction 9.2. Possibility Trees and the Multiplication Rule 9.3. Counting Elements of Disjoint Sets: The Addition Rule 9.4. The Pigeonhole Principle 9.5. Counting Subsets of a Set: Combinations 9.6. r-Combinations with Repetition Allowed 9.7. Pascal's Formula and the Binomial Theorem 9.8. Probability Axioms and Expected Value 9.9. Conditional Probability, Bayes’ Formula, and Independent Events

225 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

1. [Introduction] On the European continent, "meet in eight days" means the same weekday one week later; in English-speaking countries, "in seven days" means the same. What does each convention count?

   Continental: all days, including the first and the last. English: the number of 24-hour periods. Musical intervals are counted the continental way: an interval of a third (e.g. C and E) is two tones with a single tone in between.The difficulty in counting problems is usually not how to count but what to count.

2. [Introduction] Two balanced coins AAA and BBB are tossed. Why does "exactly 1 head" occur about twice as often as "2 heads" or "0 heads"?

   Of the 4 equally likely outcomes, 2 give one head (HT, TH), 1 gives two heads (HH) and 1 gives none (TT). HT means AAA heads and BBB tails. In 50 actual tosses of two quarters: 2 heads 11 times (22%), 1 head 27 times (54%), 0 heads 12 times (24%).

3. [Introduction] What does it mean that a process is random?

   When it takes place, one outcome from some set of outcomes is sure to occur, but it is impossible to predict with certainty which one. Example: an ordinary person tossing an ordinary coin: the outcome is in {heads,tails}\{\text{heads}, \text{tails}\}{heads,tails} , but which one is not known in advance.

4. [Introduction] What is a sample space?

   The set of all possible outcomes of a random process or experiment. Example: rolling one die has sample space {1,2,3,4,5,6}\{1, 2, 3, 4, 5, 6\}{1,2,3,4,5,6} .

5. [Introduction] What is an event?

   A subset of a sample space. Example: for one die, the event "an even number shows" is {2,4,6}\{2, 4, 6\}{2,4,6} .

6. [Introduction] What does N(A)N(A)N(A) denote, for a finite set AAA ?

   The number of elements in AAA . Example: N({a,b,c})=3N(\{a, b, c\}) = 3N({a,b,c})=3 .

7. [Introduction] Equally likely probability formula. SSS is a finite sample space in which all outcomes are equally likely, and EEE is an event in SSS . What is the probability P(E)P(E)P(E) ?

   P(E)=N(E)N(S)\boldsymbol{P(E) = \dfrac{N(E)}{N(S)}}P(E)=N(S)N(E)​ The number of outcomes in EEE divided by the total number of outcomes in SSS .Example: tossing two balanced coins, P(exactly one head)=24=12P(\text{exactly one head}) = \frac{2}{4} = \frac{1}{2}P(exactly one head)=42​=21​ .

8. [Introduction] Who formulated a set of axioms for probability, and when?

   A. N. Kolmogorov, in 1933. The equally likely probability formula P(E)=N(E)N(S)P(E) = \frac{N(E)}{N(S)}P(E)=N(S)N(E)​ can be deduced from these axioms.

9. [Introduction] An ordinary deck has 52 cards: 4 suits (red: ♢\diamondsuit♢ diamonds, ♡\heartsuit♡ hearts; black: ♣\clubsuit♣ clubs, ♠\spadesuit♠ spades), each with 2, 3, ..., 10, J, Q, K, A. The face cards are J, Q, K. One card is picked at random from a thoroughly mixed deck. What is the probability that it is a black face card?

   652≈11.5%\boldsymbol{\frac{6}{52} \approx 11.5\%}526​≈11.5% The event is E={J♣,Q♣,K♣,J♠,Q♠,K♠}E = \{J\clubsuit, Q\clubsuit, K\clubsuit, J\spadesuit, Q\spadesuit, K\spadesuit\}E={J♣,Q♣,K♣,J♠,Q♠,K♠} , so N(E)=6N(E) = 6N(E)=6 ; the sample space is the 52 cards.

10. [Introduction] How many shuffles are needed to thoroughly mix up an ordinary deck of cards?

    Seven (Persi Diaconis, with David Aldous in 1986 and Dave Bayer in 1992). With a somewhat different definition of "thoroughly mixed up", Nick and Lloyd Trefethen showed in 2000 that six shuffles nearly always suffice.

11. [Introduction] A blue die and a gray die are rolled, and the outcome is written as two digits (blue first, gray second), e.g. 24. How many outcomes does the sample space have, and what is the probability that the two numbers add up to 6?

    36 outcomes; probability 536\boldsymbol{\frac{5}{36}}365​ . S={11,12,…,16,21,…,66}S = \{11, 12, \dots, 16, 21, \dots, 66\}S={11,12,…,16,21,…,66} , and the event is E={15,24,33,42,51}E = \{15, 24, 33, 42, 51\}E={15,24,33,42,51} .

12. [Introduction] Monty Hall problem. A prize is behind one of three doors AAA , BBB , CCC . You pick door AAA . The host then opens one of the other doors, shows there is no prize behind it, and offers you to switch to the other closed door. Should you stay or switch?

    Switch: you win with probability 23\frac{2}{3}32​ by switching, and only 13\frac{1}{3}31​ by staying. Three equally likely cases: prize behind AAA (staying wins), behind BBB (host must open CCC , switching wins), behind CCC (host must open BBB , switching wins).This assumes the host always opens a door and offers the switch. In the real show, Monty Hall made the offer only occasionally, mostly when the contestant had already chosen the correct door.

13. [Introduction] Where and when were many of the fundamental principles of probability first formulated?

    In the mid-1600s, in letters between Pierre de Fermat and Blaise Pascal, answering questions of a French nobleman about games of chance. In 1812 Pierre-Simon Laplace published the first general mathematical treatise on probability.

14. [Introduction] Theorem 9.1.1 (The Number of Elements in a List) If mmm and nnn are integers and m≤nm \le nm≤n , how many integers are there from mmm to nnn inclusive?

    n−m+1\boldsymbol{n - m + 1}n−m+1 Example: from 5 through 12 there are 12−5+1=812 - 5 + 1 = 812−5+1=8 integers.

15. [Introduction] Why are there n−m+1n - m + 1n−m+1 integers from mmm to nnn ( m≤nm \le nm≤n )?

    The element m+im + im+i is the (i+1)(i+1)(i+1) st element of the list, so the last element n=m+(n−m)n = m + (n - m)n=m+(n−m) is the (n−m+1)(n - m + 1)(n−m+1) st. The formal proof is by induction: if m,…,km, \dots, km,…,k has k−m+1k - m + 1k−m+1 numbers, then m,…,k,k+1m, \dots, k, k + 1m,…,k,k+1 has (k−m+1)+1=(k+1)−m+1(k - m + 1) + 1 = (k + 1) - m + 1(k−m+1)+1=(k+1)−m+1 numbers.

16. [Introduction] How many three-digit integers (100 to 999) are divisible by 5, and what is the probability that a randomly chosen three-digit integer is divisible by 5?

    180; probability 180900=15\boldsymbol{\frac{180}{900} = \frac{1}{5}}900180​=51​ . The multiples of 5 are 5⋅20=1005 \cdot 20 = 1005⋅20=100 up to 5⋅199=9955 \cdot 199 = 9955⋅199=995 , one for each integer from 20 to 199: 199−20+1=180199 - 20 + 1 = 180199−20+1=180 . There are 999−100+1=900999 - 100 + 1 = 900999−100+1=900 three-digit integers.

17. [Introduction] An array A[1],A[2],…,A[n]A[1], A[2], \dots, A[n]A[1],A[2],…,A[n] is cut at A[m]A[m]A[m] into the subarrays A[1],…,A[m]A[1], \dots, A[m]A[1],…,A[m] and A[m+1],…,A[n]A[m+1], \dots, A[n]A[m+1],…,A[n] . How many elements does each subarray have?

    m\boldsymbol{m}m and n−m\boldsymbol{n - m}n−m By the list formula: m−1+1=mm - 1 + 1 = mm−1+1=m and n−(m+1)+1=n−mn - (m + 1) + 1 = n - mn−(m+1)+1=n−m .Example: n=10n = 10n=10 , m=4m = 4m=4 : subarrays of 4 and 6 elements.

18. [Introduction] An element of the array A[1],A[2],…,A[n]A[1], A[2], \dots, A[n]A[1],A[2],…,A[n] is chosen at random. What is the probability that its subscript is even?

    ⌊n/2⌋n\boldsymbol{\dfrac{\lfloor n/2 \rfloor}{n}}n⌊n/2⌋​ : 12\frac{1}{2}21​ if nnn is even, n−12n\frac{n-1}{2n}2nn−1​ if nnn is odd. The even subscripts 2,4,…2, 4, \dots2,4,… are 2⋅1,2⋅2,…2 \cdot 1, 2 \cdot 2, \dots2⋅1,2⋅2,… , up to 2⋅n22 \cdot \frac{n}{2}2⋅2n​ ( nnn even) or 2⋅n−122 \cdot \frac{n-1}{2}2⋅2n−1​ ( nnn odd). For odd nnn the probability gets closer to 12\frac{1}{2}21​ as nnn grows.Example: n=5n = 5n=5 : subscripts 2 and 4, probability 25\frac{2}{5}52​ .

19. [Possibility Trees, Multiplication Rule] What is a possibility tree, and what does each path from its root to a leaf represent?

    A tree listing all possibilities of events that happen in order; each root-to-leaf path is one possible outcome of the whole process. Each branching point has one branch for each possible result of the next step.Example: tossing a coin twice gives a root with 2 branches (H, T), each with 2 branches: 4 paths HH, HT, TH, TT.

20. [Possibility Trees, Multiplication Rule] Teams AAA and BBB play each other repeatedly until one team wins two games in a row or a total of three games. In how many ways can this tournament be played?

    10 ways. A–A, A–B–A–A, A–B–A–B–A, A–B–A–B–B, A–B–B, B–A–A, B–A–B–A–A, B–A–B–A–B, B–A–B–B, B–B. AAA wins in 5 of them and BBB in 5; at least 2 and at most 5 games are played.

21. [Possibility Trees, Multiplication Rule] Teams AAA and BBB play until one team wins two games in a row or a total of three games. There are 10 ways the tournament can be played.If all 10 ways are equally likely, what is the probability that five games are needed?

    410=40%\boldsymbol{\frac{4}{10} = 40\%}104​=40% Five games are played in A–B–A–B–A, A–B–A–B–B, B–A–B–A–B and B–A–B–A–A.

22. [Possibility Trees, Multiplication Rule] Theorem 9.2.1 (The Multiplication Rule) An operation consists of kkk steps, and the iii th step can be performed in nin_ini​ ways regardless of how the preceding steps were performed. In how many ways can the entire operation be performed?

    n1n2⋯nk\boldsymbol{n_1 n_2 \cdots n_k}n1​n2​⋯nk​ ways Example: pairing one of 4 input/output units A,B,C,DA, B, C, DA,B,C,D with one of 3 central processing units X,Y,ZX, Y, ZX,Y,Z : 4⋅3=3+3+3+3=124 \cdot 3 = 3 + 3 + 3 + 3 = 124⋅3=3+3+3+3=12 ways.

23. [Possibility Trees, Multiplication Rule] When applying the multiplication rule, what may depend on the earlier steps, and what may not?

    Which ways are available for a step may depend on earlier steps; the number of ways for each step may not. Example: forming a 2-letter word with distinct letters from {a,b,c}\{a, b, c\}{a,b,c} : the letters available second depend on the first letter, but there are always 2, so 3⋅2=63 \cdot 2 = 63⋅2=6 words.

24. [Possibility Trees, Multiplication Rule] A PIN is a sequence of four symbols, each one of the 26 letters or the 10 digits, with repetition allowed. How many PINs are there?

    364=1,679,616\boldsymbol{36^4 = 1{,}679{,}616}364=1,679,616 Four steps (choose the 1st, 2nd, 3rd, 4th symbol), each with 36 ways regardless of the earlier choices.

25. [Possibility Trees, Multiplication Rule] Sets A1,A2,…,AkA_1, A_2, \dots, A_kA1​,A2​,…,Ak​ have n1,n2,…,nkn_1, n_2, \dots, n_kn1​,n2​,…,nk​ elements. How many elements does A1×A2×⋯×AkA_1 \times A_2 \times \dots \times A_kA1​×A2​×⋯×Ak​ have, and why?

    n1n2⋯nk\boldsymbol{n_1 n_2 \cdots n_k}n1​n2​⋯nk​ Build a kkk -tuple (a1,…,ak)(a_1, \dots, a_k)(a1​,…,ak​) in kkk steps: choose a1∈A1a_1 \in A_1a1​∈A1​ ( n1n_1n1​ ways), then a2∈A2a_2 \in A_2a2​∈A2​ ( n2n_2n2​ ways), and so on; apply the multiplication rule.Example: ∣{1,2}×{a,b,c}∣=2⋅3=6|\{1, 2\} \times \{a, b, c\}| = 2 \cdot 3 = 6∣{1,2}×{a,b,c}∣=2⋅3=6 .

26. [Possibility Trees, Multiplication Rule] A PIN is a sequence of four symbols from the 26 letters and 10 digits. How many PINs have no repeated symbol?

    36⋅35⋅34⋅33=1,413,720\boldsymbol{36 \cdot 35 \cdot 34 \cdot 33 = 1{,}413{,}720}36⋅35⋅34⋅33=1,413,720 Each step has one symbol fewer available than the one before.With repetition allowed there are 364=1,679,61636^4 = 1{,}679{,}616364=1,679,616 PINs, so a random PIN has no repeated symbol with probability 1,413,7201,679,616≈0.8417\frac{1{,}413{,}720}{1{,}679{,}616} \approx 0.84171,679,6161,413,720​≈0.8417 , about 84%.

27. [Possibility Trees, Multiplication Rule] How many distinct input/output tables are there for circuits with two input signals PPP and QQQ ?

    24=16\boldsymbol{2^4 = 16}24=16 With the input rows 11, 10, 01, 00 in a fixed order, filling in the output column is a four-step operation, each step with 2 ways (0 or 1). So such a circuit can function in only 16 distinct ways.

28. [Possibility Trees, Multiplication Rule] For a nonempty finite set SSS of characters, what is a string over SSS , its length, and the null string?

    String over SSS A finite sequence of elements of SSS . Example: 0110 is a string over {0,1}\{0, 1\}{0,1} . Length The number of characters in the string. Example: 0110 has length 4. Null string The string with no characters, denoted ε\varepsilonε ; it has length 0. The PINs of four letters or digits are exactly the strings of length 4 over {x∣x is a letter or a digit}\{x \mid x \text{ is a letter or a digit}\}{x∣x is a letter or a digit} .

29. [Possibility Trees, Multiplication Rule] How many bit strings of length 3 are there? List them.

    8: 000, 001, 010, 100, 011, 101, 110, 111 2⋅2⋅2=82 \cdot 2 \cdot 2 = 82⋅2⋅2=8 by the multiplication rule.

30. [Possibility Trees, Multiplication Rule] How many times is the body of the inner loop executed? for i:=1i := 1i:=1 to 444 \quad for j:=1j := 1j:=1 to 333 \quad\quad [body, with no statements that leave the inner loop] \quad next jjj next iii

    4⋅3=12\boldsymbol{4 \cdot 3 = 12}4⋅3=12 times During each of the 4 iterations of the outer loop, the inner loop is iterated 3 times.

31. [Possibility Trees, Multiplication Rule] A president, a treasurer and a secretary are chosen from Ann, Bob, Cyd and Dan (one person per office). Ann cannot be president, and either Cyd or Dan must be secretary.Why is "3 choices for president, 3 for treasurer, 2 for secretary, so 3⋅3⋅2=183 \cdot 3 \cdot 2 = 183⋅3⋅2=18 ways by the multiplication rule" wrong?

    The number of choices for secretary depends on who was chosen as president and treasurer, so the multiplication rule does not apply in this order. Example: Bob president and Ann treasurer leaves 2 choices (Cyd, Dan); Bob president and Cyd treasurer leaves only 1 (Dan).

32. [Possibility Trees, Multiplication Rule] A president, a treasurer and a secretary are chosen from Ann, Bob, Cyd and Dan (one person per office). Ann cannot be president, and either Cyd or Dan must be secretary.In how many ways can the officers be chosen?

    8 ways. The possibility tree, choosing president, then treasurer, then secretary.

33. [Possibility Trees, Multiplication Rule] A president, a treasurer and a secretary are chosen from Ann, Bob, Cyd and Dan (one person per office). Ann cannot be president, and either Cyd or Dan must be secretary.In which order of steps does the multiplication rule apply, and what does it give?

    Secretary, then president, then treasurer: 2⋅2⋅2=8\boldsymbol{2 \cdot 2 \cdot 2 = 8}2⋅2⋅2=8 . Secretary: Cyd or Dan. President: neither Ann nor the secretary, so 2 left. Treasurer: either of the 2 people not yet chosen.

34. [Possibility Trees, Multiplication Rule] What is a permutation of a set of objects?

    An ordering of the objects in a row. Example: {a,b,c}\{a, b, c\}{a,b,c} has the 6 permutations abcabcabc , acbacbacb , bacbacbac , bcabcabca , cabcabcab , cbacbacba .

35. [Possibility Trees, Multiplication Rule] Theorem 9.2.2 For any integer n≥1n \ge 1n≥1 , how many permutations does a set with nnn elements have?

    n!\boldsymbol{n!}n! Example: {a,b,c,d}\{a, b, c, d\}{a,b,c,d} has 4!=244! = 244!=24 permutations.

36. [Possibility Trees, Multiplication Rule] Why does a set with nnn elements have n!n!n! permutations?

    Choose the element to write first ( nnn ways), then second ( n−1n - 1n−1 ways), ..., then nnn th (1 way); by the multiplication rule, n(n−1)⋯2⋅1=n!n(n-1) \cdots 2 \cdot 1 = n!n(n−1)⋯2⋅1=n! . Each step has one way fewer than the one before, since an element already written cannot be chosen again.

37. [Possibility Trees, Multiplication Rule] How many ways can the letters of COMPUTER be arranged in a row, and how many if CO must stay together in this order?

    8!=40,320\boldsymbol{8! = 40{,}320}8!=40,320 and 7!=5,040\boldsymbol{7! = 5{,}040}7!=5,040 The 8 letters are distinct. With CO as one unit, there are 7 objects: CO, M, P, U, T, E, R.So in a random arrangement, CO stays together in order with probability 5,04040,320=18=12.5%\frac{5{,}040}{40{,}320} = \frac{1}{8} = 12.5\%40,3205,040​=81​=12.5% .

38. [Possibility Trees, Multiplication Rule] Six diplomats sit around a circular table; two seatings are the same if one is a rotation of the other. How many different seatings are there?

    5!=120\boldsymbol{5! = 120}5!=120 Only relative positions matter, so place diplomat AAA in a fixed seat; the other five can then be arranged in the remaining seats in 5!5!5! orders.

39. [Possibility Trees, Multiplication Rule] What is an rrr -permutation of a set of nnn elements, and how is the number of them denoted?

    An ordered selection of rrr elements taken from the set; their number is denoted P(n,r)P(n, r)P(n,r) . Calculators also write nPr_nP_rn​Pr​ , Pn,rP_{n,r}Pn,r​ or nPr^nP_rnPr​ .Example: the 2-permutations of {a,b,c}\{a, b, c\}{a,b,c} are ababab , acacac , bababa , bcbcbc , cacaca , cbcbcb , so P(3,2)=6P(3, 2) = 6P(3,2)=6 .

40. [Possibility Trees, Multiplication Rule] Theorem 9.2.3 If nnn and rrr are integers and 1≤r≤n1 \le r \le n1≤r≤n , what are the two formulas for the number P(n,r)P(n, r)P(n,r) of rrr -permutations of a set of nnn elements?

    First version P(n,r)=n(n−1)(n−2)⋯(n−r+1)P(n, r) = n(n-1)(n-2) \cdots (n - r + 1)P(n,r)=n(n−1)(n−2)⋯(n−r+1) Example: P(7,4)=7⋅6⋅5⋅4=840P(7, 4) = 7 \cdot 6 \cdot 5 \cdot 4 = 840P(7,4)=7⋅6⋅5⋅4=840 . Second version P(n,r)=n!(n−r)!P(n, r) = \dfrac{n!}{(n - r)!}P(n,r)=(n−r)!n!​ Example: P(7,4)=7!3!=50406=840P(7, 4) = \frac{7!}{3!} = \frac{5040}{6} = 840P(7,4)=3!7!​=65040​=840 .

41. [Possibility Trees, Multiplication Rule] Why is the number of rrr -permutations of an nnn -set equal to n(n−1)⋯(n−r+1)n(n-1) \cdots (n - r + 1)n(n−1)⋯(n−r+1) ?

    Fill rrr positions one at a time: nnn choices for position 1, n−1n - 1n−1 for position 2, ..., and n−(r−1)=n−r+1n - (r - 1) = n - r + 1n−(r−1)=n−r+1 for position rrr ; then multiply. Just before position rrr is filled, r−1r - 1r−1 elements have been used.

42. [Possibility Trees, Multiplication Rule] Why is n(n−1)⋯(n−r+1)=n!(n−r)!n(n-1) \cdots (n - r + 1) = \dfrac{n!}{(n-r)!}n(n−1)⋯(n−r+1)=(n−r)!n!​ ?

    n!=n(n−1)⋯(n−r+1)⋅(n−r)!n! = n(n-1) \cdots (n - r + 1) \cdot (n - r)!n!=n(n−1)⋯(n−r+1)⋅(n−r)! , so dividing by (n−r)!(n - r)!(n−r)! leaves n(n−1)⋯(n−r+1)n(n-1) \cdots (n - r + 1)n(n−1)⋯(n−r+1) . Example: 6!4!=6⋅5⋅4!4!=6⋅5=30\frac{6!}{4!} = \frac{6 \cdot 5 \cdot 4!}{4!} = 6 \cdot 5 = 304!6!​=4!6⋅5⋅4!​=6⋅5=30 .

43. [Possibility Trees, Multiplication Rule] How should you compute P(15,2)=15!13!P(15, 2) = \dfrac{15!}{13!}P(15,2)=13!15!​ ?

    Cancel 13!13!13! before multiplying out: 15⋅14⋅13!13!=15⋅14=210\frac{15 \cdot 14 \cdot 13!}{13!} = 15 \cdot 14 = 21013!15⋅14⋅13!​=15⋅14=210 . Factorials grow fast: 15!=1,307,674,368,00015! = 1{,}307{,}674{,}368{,}00015!=1,307,674,368,000 and 13!=6,227,020,80013! = 6{,}227{,}020{,}80013!=6,227,020,800 can exceed a calculator's exact arithmetic.

44. [Possibility Trees, Multiplication Rule] P(5,5)=5!0!P(5, 5) = \dfrac{5!}{0!}P(5,5)=0!5!​ . Why must 0!=10! = 10!=1 for this to be right?

    P(5,5)P(5, 5)P(5,5) must equal 5!=1205! = 1205!=120 , the number of permutations of a 5-set, and 5!0!=5!\frac{5!}{0!} = 5!0!5!​=5! only when 0!=10! = 10!=1 . A 5-permutation of a 5-element set is the same as a permutation of the set.

45. [Possibility Trees, Multiplication Rule] How many ways can three of the letters of BYTES be chosen and written in a row, and how many if the first letter must be B?

    P(5,3)=60\boldsymbol{P(5, 3) = 60}P(5,3)=60 and P(4,2)=12\boldsymbol{P(4, 2) = 12}P(4,2)=12 5⋅4⋅3=605 \cdot 4 \cdot 3 = 605⋅4⋅3=60 . With B fixed first, the other two positions are filled from Y, T, E, S: 4⋅3=124 \cdot 3 = 124⋅3=12 .

46. [Possibility Trees, Multiplication Rule] How do you prove P(n,2)+P(n,1)=n2P(n, 2) + P(n, 1) = n^2P(n,2)+P(n,1)=n2 for all integers n≥2n \ge 2n≥2 ?

    P(n,2)=n!(n−2)!=n(n−1)P(n, 2) = \frac{n!}{(n-2)!} = n(n-1)P(n,2)=(n−2)!n!​=n(n−1) and P(n,1)=n!(n−1)!=nP(n, 1) = \frac{n!}{(n-1)!} = nP(n,1)=(n−1)!n!​=n , so the sum is n2−n+n=n2n^2 - n + n = n^2n2−n+n=n2 . Example: n=4n = 4n=4 : P(4,2)+P(4,1)=12+4=16=42P(4, 2) + P(4, 1) = 12 + 4 = 16 = 4^2P(4,2)+P(4,1)=12+4=16=42 .

47. [The Addition Rule] The Addition Rule A finite set AAA is the union of kkk distinct mutually disjoint subsets A1,A2,…,AkA_1, A_2, \dots, A_kA1​,A2​,…,Ak​ . Then N(A)= ?N(A) = \; ?N(A)=?

    N(A)=N(A1)+N(A2)+⋯+N(Ak)\boldsymbol{N(A) = N(A_1) + N(A_2) + \dots + N(A_k)}N(A)=N(A1​)+N(A2​)+⋯+N(Ak​) N(X)N(X)N(X) is the number of elements of a finite set XXX . The formal proof is by mathematical induction on kkk .Example: {1,2,3,4,5}={1,2}∪{3,4,5}\{1, 2, 3, 4, 5\} = \{1, 2\} \cup \{3, 4, 5\}{1,2,3,4,5}={1,2}∪{3,4,5} , and 5=2+35 = 2 + 35=2+3 .

48. [The Addition Rule] A password consists of one to three letters chosen from the 26 letters of the alphabet, with repetitions allowed. How many passwords are possible?

    26+262+263=18,278\boldsymbol{26 + 26^2 + 26^3 = 18{,}278}26+262+263=18,278 The passwords of length 1, 2 and 3 form three mutually disjoint sets, so the addition rule applies. Length jjj : 26j26^j26j passwords by the multiplication rule.

49. [The Addition Rule] How many three-digit integers (100 to 999) are divisible by 5? Count with the addition rule.

    90+90=180\boldsymbol{90 + 90 = 180}90+90=180 A multiple of 5 ends in 0 or in 5, which splits the set into two disjoint subsets. Ending in 0: 9 choices for the left-most digit (1 to 9) times 10 for the middle digit gives 90; likewise 90 ending in 5.

50. [The Addition Rule] The Difference Rule AAA is a finite set and BBB is a subset of AAA . Then N(A−B)= ?N(A - B) = \; ?N(A−B)=?

    N(A−B)=N(A)−N(B)\boldsymbol{N(A - B) = N(A) - N(B)}N(A−B)=N(A)−N(B) Example: A={1,2,3,4}A = \{1, 2, 3, 4\}A={1,2,3,4} , B={1,2}B = \{1, 2\}B={1,2} : N(A−B)=N({3,4})=4−2=2N(A - B) = N(\{3, 4\}) = 4 - 2 = 2N(A−B)=N({3,4})=4−2=2 .

51. [The Addition Rule] Why does the difference rule N(A−B)=N(A)−N(B)N(A - B) = N(A) - N(B)N(A−B)=N(A)−N(B) hold for a subset BBB of a finite set AAA ?

    BBB and A−BA - BA−B are disjoint and their union is AAA , so by the addition rule N(B)+N(A−B)=N(A)N(B) + N(A - B) = N(A)N(B)+N(A−B)=N(A) ; subtract N(B)N(B)N(B) from both sides.

52. [The Addition Rule] A PIN consists of exactly four symbols chosen from the 26 letters and the 10 digits, with repetitions allowed. There are 364=1,679,61636^4 = 1{,}679{,}616364=1,679,616 such PINs, and 36⋅35⋅34⋅33=1,413,72036 \cdot 35 \cdot 34 \cdot 33 = 1{,}413{,}72036⋅35⋅34⋅33=1,413,720 of them have no repeated symbol. How many PINs contain a repeated symbol, and what is the probability that a random PIN does?

    265,896265{,}896265,896 PINs; probability 265,8961,679,616≈0.158=15.8%\frac{265{,}896}{1{,}679{,}616} \approx 0.158 = 15.8\%1,679,616265,896​≈0.158=15.8% By the difference rule: 1,679,616−1,413,720=265,8961{,}679{,}616 - 1{,}413{,}720 = 265{,}8961,679,616−1,413,720=265,896 . All PINs are taken as equally likely.

53. [The Addition Rule] Probability of the complement of an event SSS is a finite sample space and AAA is an event in SSS . Then P(Ac)= ?P(A^c) = \; ?P(Ac)=?

    P(Ac)=1−P(A)\boldsymbol{P(A^c) = 1 - P(A)}P(Ac)=1−P(A) Example: a random PIN of 4 symbols has no repeated symbol with probability ≈0.842\approx 0.842≈0.842 , so it has a repeated symbol with probability ≈1−0.842=0.158\approx 1 - 0.842 = 0.158≈1−0.842=0.158 .

54. [The Addition Rule] How does the difference rule give P(S−A)=1−P(A)P(S - A) = 1 - P(A)P(S−A)=1−P(A) for an event AAA in a finite sample space SSS of equally likely outcomes?

    P(S−A)=N(S−A)N(S)=N(S)−N(A)N(S)=1−N(A)N(S)=1−P(A)\boldsymbol{P(S - A) = \frac{N(S - A)}{N(S)} = \frac{N(S) - N(A)}{N(S)} = 1 - \frac{N(A)}{N(S)} = 1 - P(A)}P(S−A)=N(S)N(S−A)​=N(S)N(S)−N(A)​=1−N(S)N(A)​=1−P(A) The first and last steps use the definition of probability in the equally likely case; the second step uses the difference rule.

55. [The Addition Rule] A Python identifier starts with one of 53 symbols (52 letters and the underscore), followed by any number of symbols from a set of 63 (those 53 plus the 10 digits). 31 reserved keywords, each of at most 8 characters, are not identifiers. How is the number of identifiers of at most 8 characters computed?

    Addition rule over the lengths 1 to 8, then the difference rule for the 31 keywords: ∑j=1853⋅63j−1−31\boldsymbol{\sum_{j=1}^{8} 53 \cdot 63^{j-1} - 31}∑j=18​53⋅63j−1−31 Length jjj : 53 choices for the first character and 63 for each of the other j−1j - 1j−1 . The geometric sum is 53⋅638−163−1=212,133,167,002,88053 \cdot \frac{63^8 - 1}{63 - 1} = 212{,}133{,}167{,}002{,}88053⋅63−1638−1​=212,133,167,002,880 , so there are 212,133,167,002,849212{,}133{,}167{,}002{,}849212,133,167,002,849 identifie…

56. [The Addition Rule] How is a 32-bit IP address written in dotted decimal form?

    Each group of 8 bits is written as a decimal number from 0 to 255, and the four numbers are separated by dots. Example: 10001100 11000000 00100000 1000100010001100\;11000000\;00100000\;1000100010001100110000000010000010001000 is 140.192.32.136140.192.32.136140.192.32.136 , since 100011002=128+8+4=14010001100_2 = 128 + 8 + 4 = 140100011002​=128+8+4=140 , 110000002=128+64=19211000000_2 = 128 + 64 = 192110000002​=128+64=192 , 001000002=3200100000_2 = 32001000002​=32 , 100010002=128+8=13610001000_2…

57. [The Addition Rule] An IP address of 32 bits consists of a network ID followed by a host ID. In a Class B network the network ID is the left-most 16 bits and starts with 101010 ; the host ID is the other 16 bits and may be neither all 0's nor all 1's. How many Class B networks can there be, and how many host IDs can one have?

    214=16,3842^{14} = 16{,}384214=16,384 networks; 216−2=65,5342^{16} - 2 = 65{,}534216−2=65,534 host IDs. 14 free bits in the network ID; by the difference rule, the 2 forbidden host IDs are subtracted from the 216=65,5362^{16} = 65{,}536216=65,536 bit strings of length 16.Class A: network ID is 8 bits starting with 000 . Class C: network ID is 24 bits starting with 110110110 .

58. [The Addition Rule] A Class B IP address starts with the bits 101010 , and its network ID is its first 16 bits. Which first number www can the dotted decimal form w.x.y.zw.x.y.zw.x.y.z of a Class B address have?

    128≤w≤191\boldsymbol{128 \le w \le 191}128≤w≤191 www is the first 8 bits, from 100000002=12810000000_2 = 128100000002​=128 to 101111112=19110111111_2 = 191101111112​=191 . Also yyy and zzz (the host ID) are not both 0 and not both 255.

59. [The Addition Rule] Why can't a general formula for N(A∪B)N(A \cup B)N(A∪B) use only N(A)N(A)N(A) and N(B)N(B)N(B) ?

    N(A∪B)N(A \cup B)N(A∪B) depends on how many elements AAA and BBB have in common, so the formula must also contain N(A∩B)N(A \cap B)N(A∩B) . Example: disjoint sets give N(A∪B)=N(A)+N(B)N(A \cup B) = N(A) + N(B)N(A∪B)=N(A)+N(B) , but A=BA = BA=B gives N(A∪B)=N(A)N(A \cup B) = N(A)N(A∪B)=N(A) .

60. [The Addition Rule] The Inclusion/Exclusion Rule for two sets AAA and BBB are finite sets. Then N(A∪B)= ?N(A \cup B) = \; ?N(A∪B)=?

    N(A∪B)=N(A)+N(B)−N(A∩B)\boldsymbol{N(A \cup B) = N(A) + N(B) - N(A \cap B)}N(A∪B)=N(A)+N(B)−N(A∩B) N(A)+N(B)N(A) + N(B)N(A)+N(B) counts each element of A∩BA \cap BA∩B twice, so N(A∩B)N(A \cap B)N(A∩B) is subtracted once.Example: A={1,2,3}A = \{1, 2, 3\}A={1,2,3} , B={3,4}B = \{3, 4\}B={3,4} : N(A∪B)=3+2−1=4N(A \cup B) = 3 + 2 - 1 = 4N(A∪B)=3+2−1=4 .

61. [The Addition Rule] The Inclusion/Exclusion Rule for three sets AAA , BBB and CCC are finite sets. Then N(A∪B∪C)= ?N(A \cup B \cup C) = \; ?N(A∪B∪C)=?

    N(A)+N(B)+N(C)−N(A∩B)−N(A∩C)−N(B∩C)+N(A∩B∩C)\boldsymbol{N(A) + N(B) + N(C) - N(A \cap B) - N(A \cap C) - N(B \cap C) + N(A \cap B \cap C)}N(A)+N(B)+N(C)−N(A∩B)−N(A∩C)−N(B∩C)+N(A∩B∩C) Example: A={1,2}A = \{1, 2\}A={1,2} , B={2,3}B = \{2, 3\}B={2,3} , C={2,4}C = \{2, 4\}C={2,4} : 2+2+2−1−1−1+1=4=N({1,2,3,4})2 + 2 + 2 - 1 - 1 - 1 + 1 = 4 = N(\{1, 2, 3, 4\})2+2+2−1−1−1+1=4=N({1,2,3,4}) .

62. [The Addition Rule] What is the inclusion/exclusion rule for nnn finite sets A1,…,AnA_1, \dots, A_nA1​,…,An​ ?

    Add the N(Ai)N(A_i)N(Ai​) , subtract the pairwise intersections, add the triple intersections, and so on, up to (−1)n+1N(A1∩⋯∩An)(-1)^{n+1} N(A_1 \cap \dots \cap A_n)(−1)n+1N(A1​∩⋯∩An​) . N(⋃i=1nAi)=∑iN(Ai)−∑i<jN(Ai∩Aj)+∑i<j<kN(Ai∩Aj∩Ak)−⋯+(−1)n+1N(A1∩⋯∩An)\displaystyle N\Big(\bigcup_{i=1}^n A_i\Big) = \sum_{i} N(A_i) - \sum_{i<j} N(A_i \cap A_j) + \sum_{i<j<k} N(A_i \cap A_j \cap A_k) - \dots + (-1)^{n+1} N(A_1 \cap \dots \cap A_n)N(i=1⋃n​Ai​)=i∑​N(Ai​)−i<j∑​N(Ai​∩Aj​)+i<j<k∑​N(Ai​∩Aj​∩Ak​)−⋯+…

63. [The Addition Rule] How many integers from 1 through 1,000 are multiples of 3 or multiples of 5?

    333+200−66=467\boldsymbol{333 + 200 - 66 = 467}333+200−66=467 By inclusion/exclusion: 333 multiples of 3 ( 3⋅333=9993 \cdot 333 = 9993⋅333=999 ), 200 multiples of 5, and 66 multiples of both, i.e. of 15 ( 15⋅66=99015 \cdot 66 = 99015⋅66=990 ).

64. [The Addition Rule] 467 of the integers from 1 through 1,000 are multiples of 3 or multiples of 5.How many are neither multiples of 3 nor multiples of 5, and which set identity does the count use?

    1,000−467=5331{,}000 - 467 = 5331,000−467=533 , using De Morgan's law Ac∩Bc=(A∪B)cA^c \cap B^c = (A \cup B)^cAc∩Bc=(A∪B)c . With AAA , BBB the multiples of 3 and of 5 in the universe U={1,…,1000}U = \{1, \dots, 1000\}U={1,…,1000} : N(Ac∩Bc)=N((A∪B)c)=N(U)−N(A∪B)N(A^c \cap B^c) = N((A \cup B)^c) = N(U) - N(A \cup B)N(Ac∩Bc)=N((A∪B)c)=N(U)−N(A∪B) by the difference rule.

65. [The Addition Rule] Of 50 students, 30 took precalculus ( PPP ), 18 calculus ( CCC ), 26 Java ( JJJ ); 9 took PPP and CCC , 16 took PPP and JJJ , 8 took CCC and JJJ ; 47 took at least one of the three. How many took none of the three, and how many took all three?

    3 took none; 6 took all three. None: 50−47=350 - 47 = 350−47=3 by the difference rule. All three, by inclusion/exclusion: 47=30+18+26−9−16−8+N(P∩C∩J)47 = 30 + 18 + 26 - 9 - 16 - 8 + N(P \cap C \cap J)47=30+18+26−9−16−8+N(P∩C∩J) , so N(P∩C∩J)=47−41=6N(P \cap C \cap J) = 47 - 41 = 6N(P∩C∩J)=47−41=6 .

66. [The Addition Rule] In the inclusion/exclusion formula for three sets, how many of its eight terms must be known to find the remaining one?

    Any seven. The formula is one linear equation in the eight numbers N(A∪B∪C)N(A \cup B \cup C)N(A∪B∪C) , N(A)N(A)N(A) , N(B)N(B)N(B) , N(C)N(C)N(C) , N(A∩B)N(A \cap B)N(A∩B) , N(A∩C)N(A \cap C)N(A∩C) , N(B∩C)N(B \cap C)N(B∩C) , N(A∩B∩C)N(A \cap B \cap C)N(A∩B∩C) .

67. [The Addition Rule] Of 50 students, 30 took precalculus ( PPP ), 18 calculus ( CCC ), 26 Java ( JJJ ); 9 took PPP and CCC , 16 took PPP and JJJ , 8 took CCC and JJJ ; 6 took all three; 3 took none. How do you find the number in each region of the Venn diagram of PPP , CCC , JJJ ?

    Start with the innermost region (6) and work outward, subtracting the counts already placed. PPP and CCC but not JJJ : 9−6=39 - 6 = 39−6=3 . PPP and JJJ but not CCC : 16−6=1016 - 6 = 1016−6=10 . CCC and JJJ but not PPP : 8−6=28 - 6 = 28−6=2 . Only PPP : 30−3−10−6=1130 - 3 - 10 - 6 = 1130−3−10−6=11 . Only JJJ : 26−10−6−2=826 - 10 - 6 - 2 = 826−10−6−2=8 . Only CCC : 18−3−6−2=718 - 3 - 6 - 2 = 718−3−6−2=7 .

68. [The Pigeonhole Principle] What does the pigeonhole principle state, informally?

    If nnn pigeons fly into mmm pigeonholes and n>mn > mn>m , then at least one pigeonhole contains two or more pigeons. n=5n = 5n=5 pigeons, m=4m = 4m=4 pigeonholes: pigeons 1 and 4 are in pigeonhole 3.

69. [The Pigeonhole Principle] The Pigeonhole Principle (as a statement about functions) fff is a function from a finite set XXX with nnn elements to a finite set YYY with mmm elements, and n>mn > mn>m . Then … ?

    fff is not one-to-one: at least two elements of XXX have the same image in YYY . In an arrow diagram of fff , at least two arrows point to the same element of YYY .

70. [The Pigeonhole Principle] The pigeonhole principle is also called the Dirichlet box principle, after the mathematician who first stated it formally (1805 to 1859).

71. [The Pigeonhole Principle] In a group of 13 people, must two of them be born in the same month? In a group of 6?

    13: yes. 6: no. The function from people (pigeons) to their birth months (pigeonholes) goes from a 13-set to a 12-set, so it is not one-to-one. Six people can be born in January through June.

72. [The Pigeonhole Principle] New York City has at least 5,000,000 residents, and no person has more than 300,000 hairs on the head. Must two residents have the same number of hairs on their heads?

    Yes, by the pigeonhole principle. The function from residents to their number of hairs goes into {0,1,…,300,000}\{0, 1, \dots, 300{,}000\}{0,1,…,300,000} , a set of 300,001 elements, which is smaller than the set of residents. So the function is not one-to-one.

73. [The Pigeonhole Principle] A drawer contains 10 black and 10 white socks. What is the least number of socks you must pull out, without looking, to be sure of a matched pair?

    3 The function from the socks pulled out to their colors goes into a 2-set; with 3 socks it is not one-to-one. Two socks can have different colors.

74. [The Pigeonhole Principle] Five integers are selected from A={1,2,3,4,5,6,7,8}A = \{1, 2, 3, 4, 5, 6, 7, 8\}A={1,2,3,4,5,6,7,8} . Must two of them have sum 9, and why?

    Yes: partition AAA into {1,8},{2,7},{3,6},{4,5}\{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}{1,8},{2,7},{3,6},{4,5} ; two of the 5 integers lie in the same subset, and the two elements of each subset add up to 9. Pigeons: the 5 integers; pigeonholes: the 4 subsets. The function sending aia_iai​ to the subset that contains aia_iai​ is well defined because the subsets are disjoint and their union is AAA .

75. [The Pigeonhole Principle] Four integers are selected from {1,2,3,4,5,6,7,8}\{1, 2, 3, 4, 5, 6, 7, 8\}{1,2,3,4,5,6,7,8} . Must two of them have sum 9?

    No. 1,2,3,41, 2, 3, 41,2,3,4 : the largest sum of two of them is 7. Here 4 pigeons and 4 pigeonholes ( {1,8},{2,7},{3,6},{4,5}\{1, 8\}, \{2, 7\}, \{3, 6\}, \{4, 5\}{1,8},{2,7},{3,6},{4,5} ), so the pigeonhole principle does not apply.

76. [The Pigeonhole Principle] Which consequence of the pigeonhole principle holds for the decimal expansion of every rational number?

    It either terminates or repeats. Example: 3.6253.6253.625 terminates; 2.38246‾2.38\overline{246}2.38246 repeats the digits 246246246 forever.

77. [The Pigeonhole Principle] What is the decimal expansion of 433\frac{4}{33}334​ , and at which point of the long division does it start to repeat?

    433=0.12‾\boldsymbol{\frac{4}{33} = 0.\overline{12}}334​=0.12 : the remainder 4 appears again after two division steps. Once a remainder repeats, the sequence of quotients and remainders repeats forever.

78. [The Pigeonhole Principle] a,ba, ba,b are positive integers and r0=a,r1,r2,…r_0 = a, r_1, r_2, \dotsr0​=a,r1​,r2​,… are the remainders in the long division of aaa by bbb . Why must the decimal expansion of ab\frac{a}{b}ba​ terminate or repeat?

    Each rir_iri​ is in {0,…,b−1}\{0, \dots, b - 1\}{0,…,b−1} , so either some ri=0r_i = 0ri​=0 (the expansion terminates) or some value repeats, rj=rkr_j = r_krj​=rk​ with j<kj < kj<k . In the second case the digits obtained from the divisions of rjr_jrj​ through rk−1r_{k-1}rk−1​ repeat forever. The bound on rir_iri​ comes from the quotient-remainder theorem. The pigeonhole principle is used in the form: a function from an infinite set to a finite set is not one-to-one. Example: for 314\frac{3}{14…

79. [The Pigeonhole Principle] Why is 0.01011011101111011111…0.01011011101111011111\dots0.01011011101111011111… (each string of 1's has one more 1 than the string before it) not rational?

    Its decimal expansion neither terminates nor repeats, and every rational number has a terminating or repeating decimal expansion.

80. [The Pigeonhole Principle] What generalization of the pigeonhole principle concerns a function from an infinite set to a finite set?

    Such a function cannot be one-to-one. Example: the function from the infinite sequence of remainders r0,r1,…r_0, r_1, \dotsr0​,r1​,… in a long division by bbb to the values {0,…,b−1}\{0, \dots, b - 1\}{0,…,b−1} .

81. [The Pigeonhole Principle] What does the generalized pigeonhole principle state, informally?

    If nnn pigeons fly into mmm pigeonholes and k<nmk < \frac{n}{m}k<mn​ for a positive integer kkk , then some pigeonhole contains at least k+1k + 1k+1 pigeons. Example: n=9n = 9n=9 , m=4m = 4m=4 , k=2k = 2k=2 : 2<94=2.252 < \frac{9}{4} = 2.252<49​=2.25 , so some pigeonhole contains 3 pigeons (here pigeonhole 3).

82. [The Pigeonhole Principle] The Generalized Pigeonhole Principle (as a statement about functions) fff is a function from a finite set XXX with nnn elements to a finite set YYY with mmm elements, and kkk is a positive integer with k<nmk < \frac{n}{m}k<mn​ . Then … ?

    Some y∈Yy \in Yy∈Y is the image of at least k+1k + 1k+1 distinct elements of XXX . Example: f:{1,…,7}→{a,b,c}f: \{1, \dots, 7\} \to \{a, b, c\}f:{1,…,7}→{a,b,c} and k=2<73k = 2 < \frac{7}{3}k=2<37​ : some letter is the image of at least 3 numbers.

83. [The Pigeonhole Principle] The Generalized Pigeonhole Principle (contrapositive form) fff is a function from a finite set XXX with nnn elements to a finite set YYY with mmm elements, kkk is a positive integer, and f−1(y)f^{-1}(y)f−1(y) has at most kkk elements for each y∈Yy \in Yy∈Y . Then … ?

    n≤km\boldsymbol{n \le km}n≤km f−1(y)={x∈X∣f(x)=y}f^{-1}(y) = \{x \in X \mid f(x) = y\}f−1(y)={x∈X∣f(x)=y} is the inverse image of yyy .Example: if each of 26 initials is the last initial of at most 3 people, there are at most 3⋅26=783 \cdot 26 = 783⋅26=78 people.

84. [The Pigeonhole Principle] Why must at least 4 people in a group of 85 have the same last initial?

    3<8526≈3.273 < \frac{85}{26} \approx 3.273<2685​≈3.27 , so by the generalized pigeonhole principle some initial belongs to at least 3+1=43 + 1 = 43+1=4 people. Pigeons: the 85 people; pigeonholes: the 26 initials. Contrapositive form: if each initial belonged to at most 3 people, there would be at most 3⋅26=783 \cdot 26 = 783⋅26=78 people.

85. [The Pigeonhole Principle] 42 students share 12 computers; each student uses exactly 1 computer, and no computer is used by more than 6 students. Show that at least 5 computers are used by 3 or more students.

    Let kkk be the number of computers used by 3 or more students. They serve at most 6k6k6k students, the other 12−k12 - k12−k at most 2(12−k)2(12 - k)2(12−k) , so 6k+24−2k≥426k + 24 - 2k \ge 426k+24−2k≥42 , i.e. k≥4.5k \ge 4.5k≥4.5 , so k≥5k \ge 5k≥5 . Each bound is the contrapositive form of the generalized pigeonhole principle: at most jjj students per computer on ccc computers means at most jcjcjc students.

86. [The Pigeonhole Principle] 42 students share 12 computers; each student uses exactly 1 computer, and no computer is used by more than 6 students.How does the argument by contradiction show that at least 5 computers are used by 3 or more students?

    If at most 4 computers had 3 or more students, then 8 computers would serve at most 2 each and the other 4 at most 6 each: at most 16+24=40<4216 + 24 = 40 < 4216+24=40<42 students. Contradiction, since all 42 students use a computer.

87. [The Pigeonhole Principle] When is a set finite?

    It is empty, or there is a one-to-one correspondence from {1,2,…,n}\{1, 2, \dots, n\}{1,2,…,n} to it for some positive integer nnn . It then has 0 or nnn elements, and can be written {x1,…,xn}\{x_1, \dots, x_n\}{x1​,…,xn​} . A set that is not finite is infinite.

88. [The Pigeonhole Principle] Pigeonhole principle: a function fff from a finite set XXX with nnn elements to a finite set Y={y1,…,ym}Y = \{y_1, \dots, y_m\}Y={y1​,…,ym​} with n>mn > mn>m is not one-to-one.How does the proof use the addition rule?

    The inverse images f−1(y1),…,f−1(ym)f^{-1}(y_1), \dots, f^{-1}(y_m)f−1(y1​),…,f−1(ym​) are mutually disjoint with union XXX , so n=N(f−1(y1))+⋯+N(f−1(ym))n = N(f^{-1}(y_1)) + \dots + N(f^{-1}(y_m))n=N(f−1(y1​))+⋯+N(f−1(ym​)) . If fff were one-to-one, each term would be at most 1, giving n≤mn \le mn≤m , a contradiction. Union XXX : each xxx has an image. Disjoint: no xxx has two images.

89. [The Pigeonhole Principle] One-to-One and Onto for Finite Sets XXX and YYY are finite sets with the same number of elements, and fff is a function from XXX to YYY . Then fff is one-to-one if and only if … ?

    fff is onto. This fails for infinite sets. Example: f:Z+→Z+f: \mathbb{Z}^+ \to \mathbb{Z}^+f:Z+→Z+ , f(n)=2nf(n) = 2nf(n)=2n is one-to-one but not onto.

90. [The Pigeonhole Principle] X={x1,…,xm}X = \{x_1, \dots, x_m\}X={x1​,…,xm​} and YYY both have mmm elements, and f:X→Yf: X \to Yf:X→Y is one-to-one. Why is fff onto?

    By the addition rule, m=N(Y)=m+N(S)m = N(Y) = m + N(S)m=N(Y)=m+N(S) , so N(S)=0N(S) = 0N(S)=0 , where SSS is the set of elements of YYY that are the image of no element of XXX . YYY is the union of the mutually disjoint sets {f(x1)},…,{f(xm)}\{f(x_1)\}, \dots, \{f(x_m)\}{f(x1​)},…,{f(xm​)} and SSS ; the mmm singletons are distinct because fff is one-to-one.

91. [The Pigeonhole Principle] XXX and Y={y1,…,ym}Y = \{y_1, \dots, y_m\}Y={y1​,…,ym​} both have mmm elements, and f:X→Yf: X \to Yf:X→Y is onto. Why is fff one-to-one?

    m=N(X)=∑i=1mN(f−1(yi))m = N(X) = \sum_{i=1}^m N(f^{-1}(y_i))m=N(X)=∑i=1m​N(f−1(yi​)) with each term ≥1\ge 1≥1 , so each term is exactly 1. The inverse images f−1(yi)f^{-1}(y_i)f−1(yi​) are mutually disjoint with union XXX (addition rule), and each is nonempty because fff is onto. A term of 2 or more would make the sum greater than mmm .

92. [The Pigeonhole Principle] What is a one-to-one function from a finite set to itself, and why is it also onto?

    A permutation of the set; it is onto because a function between finite sets with the same number of elements is one-to-one if and only if it is onto. Example: the function a↦ca \mapsto ca↦c , b↦db \mapsto db↦d , c↦bc \mapsto bc↦b , d↦ad \mapsto ad↦a on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} is the permutation cdbacdbacdba (the images of a,b,c,da, b, c, da,b,c,d in order).

93. [Counting Subsets of a Set: Combinations] nnn and rrr are nonnegative integers with r≤nr \le nr≤n . What is an rrr -combination of a set of nnn elements?

    A subset of rrr of the nnn elements. Example: {a,c}\{a, c\}{a,c} is a 2-combination of {a,b,c}\{a, b, c\}{a,b,c} .

94. [Counting Subsets of a Set: Combinations] What does the symbol (nr)\binom{n}{r}(rn​) denote ( n,rn, rn,r nonnegative integers, r≤nr \le nr≤n )?

    The number of subsets of size rrr ( rrr -combinations) that can be chosen from a set of nnn elements. Calculators write C(n,r)C(n, r)C(n,r) , nCr\,_nC_rn​Cr​ , Cn,rC_{n,r}Cn,r​ or nCr\,^nC_rnCr​ instead.Example: (32)=3\binom{3}{2} = 3(23​)=3 : the 2-subsets of {a,b,c}\{a, b, c\}{a,b,c} are {a,b},{a,c},{b,c}\{a, b\}, \{a, c\}, \{b, c\}{a,b},{a,c},{b,c} .

95. [Counting Subsets of a Set: Combinations] The symbol (nr)\binom{n}{r}(rn​) is read "n choose r".

96. [Counting Subsets of a Set: Combinations] S={Ann,Bob,Cyd,Dan}S = \{\text{Ann}, \text{Bob}, \text{Cyd}, \text{Dan}\}S={Ann,Bob,Cyd,Dan} . List the 3-combinations of SSS . What is (43)\binom{4}{3}(34​) ?

    (43)=4\boldsymbol{\binom{4}{3} = 4}(34​)=4 : {\{{ Bob, Cyd, Dan }\}} , {\{{ Ann, Cyd, Dan }\}} , {\{{ Ann, Bob, Dan }\}} , {\{{ Ann, Bob, Cyd }\}} Each subset of size 3 is obtained by leaving out one of the 4 elements of SSS .

97. [Counting Subsets of a Set: Combinations] What is the difference between an ordered selection and an unordered selection of rrr elements from a set of nnn elements?

    Ordered selection ( rrr -permutation) Two ordered selections are the same only if the same elements are chosen in the same order. Example: 010101 and 101010 are different 2-permutations of {0,1,2,3}\{0, 1, 2, 3\}{0,1,2,3} . Unordered selection ( rrr -combination) Two unordered selections are the same if they consist of the same elements, regardless of the order in which the elements are chosen. Example: choosing 0 then 1 and choosing 1 then 0 give the same 2-combination {0,1}\{0, 1\}{0,1} .

98. [Counting Subsets of a Set: Combinations] How many unordered selections of two elements can be made from {0,1,2,3}\{0, 1, 2, 3\}{0,1,2,3} ? List them systematically.

    (42)=6\boldsymbol{\binom{4}{2} = 6}(24​)=6 : {0,1},{0,2},{0,3},{1,2},{1,3},{2,3}\{0, 1\}, \{0, 2\}, \{0, 3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}{0,1},{0,2},{0,3},{1,2},{1,3},{2,3} First the subsets containing 0, then those containing 1 but not already listed, then those containing 2 but not already listed.

99. [Counting Subsets of a Set: Combinations] Computing (nr)\binom{n}{r}(rn​) by listing all possibilities is called the method of complete enumeration.

    It is feasible only when nnn and rrr are small.

100. [Counting Subsets of a Set: Combinations] Theorem 9.5.1 For nonnegative integers nnn and rrr with r≤nr \le nr≤n , give the two formulas for (nr)\binom{n}{r}(rn​) in terms of P(n,r)P(n, r)P(n,r) and in terms of factorials.

     (nr)=P(n,r)r!=n!r! (n−r)!\boldsymbol{\binom{n}{r} = \dfrac{P(n, r)}{r!} = \dfrac{n!}{r!\,(n - r)!}}(rn​)=r!P(n,r)​=r!(n−r)!n!​ P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n-r)!}P(n,r)=(n−r)!n!​ is the number of rrr -permutations (ordered selections of rrr distinct elements) of a set of nnn elements.Example: (42)=P(4,2)2!=122=6\binom{4}{2} = \frac{P(4, 2)}{2!} = \frac{12}{2} = 6(24​)=2!P(4,2)​=212​=6 .