Ch.1: Combinatorics

Chapter 1 of the book "Probability for the Enthusiastic Beginner" by David Morin (2016) Factorials Permutations Ordered sets, repetitions allowed Ordered sets, repetitions not allowed Unordered sets, repetitions not allowed What we know so far Unordered sets, repetitions allowed Binomial coefficients Problems

126 flashcards · Mathematics · by lakesare

Part of Textbooks › Probability for the Enthusiastic Beginner (David Morin) · 7 courses

1. [Combinatorics] What is combinatorics?

   The study of how to count things: the combinations, orderings and subgroups that can be formed from a given set of objects. Example: how many outcomes 4 coin flips have, how many 3-person committees 5 people can form.

2. [Combinatorics] Why is counting central to probability?

   To find the probability of an event, you often count the number of ways the event can happen. Once the relevant things are counted, obtaining the probability is usually a short step.

3. [Factorials] What is NNN factorial, N!N!N! , for a positive integer NNN ?

   The product of the first NNN integers: N!=1⋅2⋅3⋯NN! = 1 \cdot 2 \cdot 3 \cdots NN!=1⋅2⋅3⋯N . Example: 5!=1⋅2⋅3⋅4⋅5=1205! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 1205!=1⋅2⋅3⋅4⋅5=120 .

4. [Factorials] What are 1!,2!,…,6!1!, 2!, \dots, 6!1!,2!,…,6! ?

   1, 2, 6, 24, 120, 720\boldsymbol{1, \ 2, \ 6, \ 24, \ 120, \ 720}1, 2, 6, 24, 120, 720 Each is the previous one times the next integer: 6!=6⋅120=7206! = 6 \cdot 120 = 7206!=6⋅120=720 .

5. [Factorials] How large are 10!10!10! and 20!20!20! ?

   10!=3,628,800\boldsymbol{10! = 3{,}628{,}800}10!=3,628,800 and 20!≈2.43⋅1018\boldsymbol{20! \approx 2.43 \cdot 10^{18}}20!≈2.43⋅1018 N!N!N! grows very fast as NNN increases. Stirling's formula (chapter 2) approximates N!N!N! .

6. [Factorials] What is 0!0!0! , and why?

   0!=1\boldsymbol{0! = 1}0!=1 , by definition, because with this value many formulas hold without exceptions. "Product of the first 0 integers" has no direct meaning, since the product starts at 1.Example: (NN)=N!N! 0!=1\binom{N}{N} = \frac{N!}{N! \, 0!} = 1(NN​)=N!0!N!​=1 , the one way to pick all NNN of NNN people.

7. [Permutations] What is a permutation of a set of objects?

   A way of ordering the objects. Example: Carol, Alice, Bob is one of the 6 permutations of Alice, Bob, Carol.

8. [Permutations] PNP_NPN​ is the number of permutations of NNN objects. What are P1,…,P5P_1, \dots, P_5P1​,…,P5​ ?

   1, 2, 6, 24, 120\boldsymbol{1, \ 2, \ 6, \ 24, \ 120}1, 2, 6, 24, 120 P1=1P_1 = 1P1​=1 and P2=2P_2 = 2P2​=2 might suggest PN=NP_N = NPN​=N , but P3=6P_3 = 6P3​=6 : 123213312132231321\begin{array}{ccc} 123 & 213 & 312 \\ 132 & 231 & 321 \end{array}123132​213231​312321​

9. [Permutations] PNP_NPN​ is the number of permutations (orderings) of NNN objects. Why is PN=N⋅PN−1P_N = N \cdot P_{N-1}PN​=N⋅PN−1​ ?

   Group the permutations by which object comes first: there are NNN groups, and each group consists of the PN−1P_{N-1}PN−1​ permutations of the other N−1N - 1N−1 objects. Example: the permutations of 1, 2, 3, 4 that start with 4 are 4 followed by the 6 permutations of 1, 2, 3, so P4=4⋅6=24P_4 = 4 \cdot 6 = 24P4​=4⋅6=24 .

10. [Permutations] How many permutations (orderings) of NNN objects are there?

    PN=N!\boldsymbol{P_N = N!}PN​=N! From P1=1P_1 = 1P1​=1 and PN=N⋅PN−1P_N = N \cdot P_{N-1}PN​=N⋅PN−1​ : each stage multiplies by a factor NNN , since a permutation can start with any of the NNN objects.Example: P5=5⋅P4=5⋅4⋅3⋅2⋅1=120P_5 = 5 \cdot P_4 = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120P5​=5⋅P4​=5⋅4⋅3⋅2⋅1=120 .

11. [Permutations] When counting permutations of objects labelled 1, 2, 3 (or A, B, C, or ⊗,♠,♡\otimes, \spadesuit, \heartsuit⊗,♠,♡ ), what property of the labels matters?

    Only that the labels are different from each other. The labels stand for distinct objects and need no other meaningful property, so any symbols work.

12. [Permutations] Four people are assigned to four seats in a row, one seat at a time. How does this "seat filling" show that there are 4!4!4! orderings?

    4 choices for the first seat, then 3 for the second, 2 for the third, 1 for the fourth: 4⋅3⋅2⋅1=244 \cdot 3 \cdot 2 \cdot 1 = 244⋅3⋅2⋅1=24 . Each seat has one choice fewer, because one more person has been assigned. The branching tree for N=4N = 4N=4 : the number of branches in each fork decreases by one at each stage.

13. [Permutations] There are aaa possibilities for outcome 1, and for each of these bbb possibilities for outcome 2, and for each of these ccc for outcome 3. How many combined possibilities are there?

    a⋅b⋅c\boldsymbol{a \cdot b \cdot c}a⋅b⋅c , the product, not the sum. The product comes from the words "for each of these".Example: 7 people each carry 3 books, so there are 7⋅3=217 \cdot 3 = 217⋅3=21 books, not 7+3=107 + 3 = 107+3=10 .

14. [Permutations] Nine people are assigned to nine seats in a row, where five specific people must take the left five seats and the other four the right four seats. How many assignments are there?

    5!⋅4!=120⋅24=2,880\boldsymbol{5! \cdot 4! = 120 \cdot 24 = 2{,}880}5!⋅4!=120⋅24=2,880 5!5!5! ways to seat the five on the left, and for each of these, 4!4!4! ways to seat the four on the right.Without the restriction there are 9!=362,8809! = 362{,}8809!=362,880 assignments; the ratio 9!5! 4!=126\frac{9!}{5! \, 4!} = 1265!4!9!​=126 is a quotient of three factorials, the kind that counts unordered sets.

15. [Ordered sets, repetitions allowed] A box contains balls labelled A, B, C, D, E. You draw a ball, write down its letter, and draw again. Which three phrases describe the case where the second draw has the same possibilities as the first?

    Identical trials, with replacement, repetitions allowed. You put the drawn ball back into the box, so a later draw can repeat a letter already drawn. Equivalently: two boxes with identical balls, one draw from each.

16. [Ordered sets, repetitions allowed] Why are rolls of a die or flips of a coin always identical trials (with replacement)?

    The set of possible results is the same at every roll or flip; nothing is removed. So repetitions are automatically allowed. You don't remove the dots on a die after you roll it.

17. [Ordered sets, repetitions allowed] A box contains 5 balls A, B, C, D, E. How many ordered pairs of letters can two draws with replacement give?

    5⋅5=25\boldsymbol{5 \cdot 5 = 25}5⋅5=25 5 possibilities for the first draw, and for each of these, 5 for the second. AC and CA are different pairs, and AA is allowed.Example: with 3 draws there are 52⋅5=53=1255^2 \cdot 5 = 5^3 = 12552⋅5=53=125 ordered triplets, with 4 draws 54=6255^4 = 62554=625 .

18. [Ordered sets, repetitions allowed] You pick nnn objects, one after another, from a box of NNN distinct objects, with replacement, and the order matters. How many outcomes are there?

    Nn\boldsymbol{N^n}Nn NNN results for the first pick, for each of these NNN for the second ( N2N^2N2 in total), for each of these NNN for the third ( N3N^3N3 ), and so on. N=3N = 3N=3 : after n=1,2,3,4n = 1, 2, 3, 4n=1,2,3,4 trials there are 3,9,27,813, 9, 27, 813,9,27,81 outcomes. The marked branch is ACAB.

19. [Ordered sets, repetitions allowed] Picking nnn objects from NNN distinct objects, with replacement, with the order mattering: each pick has NNN possible results.Why is the number of outcomes NnN^nNn and not nNnNnN ?

    For each result of the earlier picks, every pick has NNN results, so the counts multiply. Example: 3 coin flips have 23=82^3 = 823=8 outcomes, not 3⋅2=63 \cdot 2 = 63⋅2=6 .

20. [Ordered sets, repetitions allowed] What are the two differences between the count NnN^nNn (ordered, with replacement) and the count N!N!N! (permutations of NNN objects)?

    Factors The factors of NnN^nNn are all NNN , since the ball is put back. The factors of N!N!N! decrease from NNN to 1, since a used object can't be used again. Example: 33=3⋅3⋅3=273^3 = 3 \cdot 3 \cdot 3 = 2733=3⋅3⋅3=27 , but 3!=3⋅2⋅1=63! = 3 \cdot 2 \cdot 1 = 63!=3⋅2⋅1=6 . Number of factors In NnN^nNn you choose the number of trials nnn , which may be larger than NNN . N!N!N! has exactly NNN factors, since it orders the entire set of NNN objects. Example: 4 picks from 2 objects give 24=162^4 =…

21. [Ordered sets, repetitions allowed] A six-sided die is rolled twice. How many ordered outcomes are there?

    62=36\boldsymbol{6^2 = 36}62=36 The order matters: (2, 5), a 2 on the first roll and a 5 on the second, is different from (5, 2).

22. [Ordered sets, repetitions allowed] Two six-sided dice are rolled. What is the probability that the sum is 7?

    636=16≈16.7%\boldsymbol{\frac{6}{36} = \frac{1}{6} \approx 16.7\%}366​=61​≈16.7% Of the 36 equally likely ordered outcomes, six have sum 7: (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1).7 is the sum with the most outcomes, so it is the most probable sum.

23. [Ordered sets, repetitions allowed] A coin is flipped four times. How many ordered outcomes are there?

    24=16\boldsymbol{2^4 = 16}24=16 Two possibilities (H or T) for each of the four flips.

24. [Ordered sets, repetitions allowed] You have the list of the 16 ordered outcomes of 4 coin flips. How do you get the list for 5 flips?

    Put an H in front of all 16 outcomes, then a T in front of all 16 again: 2⋅16=32=252 \cdot 16 = 32 = 2^52⋅16=32=25 outcomes. Conversely, the 4-flip outcomes starting with H are H followed by the 23=82^3 = 823=8 outcomes of 3 flips.

25. [Ordered sets, repetitions allowed] A coin is flipped four times. What is the probability of exactly two Heads?

    616=38=37.5%\boldsymbol{\frac{6}{16} = \frac{3}{8} = 37.5\%}166​=83​=37.5% Of the 16 equally likely ordered outcomes, six have two Heads: HHTT, HTHT, HTTH, THHT, THTH, TTHH.Two Heads is the most likely number of Heads.

26. [Ordered sets, repetitions not allowed] You choose an ordered set of nnn objects from NNN objects without repetitions (e.g. a committee of nnn people with distinct positions). Why must n≤Nn \le Nn≤N ?

    Each object can be used at most once, so at most NNN can be chosen. With repetitions allowed, nnn has no upper bound (there are NnN^nNn ordered sets).

27. [Ordered sets, repetitions not allowed] How many ordered pairs of distinct people (e.g. president and secretary) can be chosen from 5 people A, B, C, D, E, by first listing all pairs of letters?

    52−5=205^2 - 5 = 2052−5=20 : of the 5×55 \times 55×5 square of pairs, the 5 pairs with a repeated letter (AA, BB, CC, DD, EE on the diagonal) are not allowed. For NNN people: N2−N=N(N−1)N^2 - N = N(N-1)N2−N=N(N−1) ordered pairs.

28. [Ordered sets, repetitions not allowed] How many ordered pairs of distinct people can be chosen from 5 people, by filling two seats one at a time?

    5⋅4=20\boldsymbol{5 \cdot 4 = 20}5⋅4=20 5 possibilities for the first seat, and for each of these, 4 for the second, since only 4 people are left. For NNN people: N(N−1)N(N-1)N(N−1) .

29. [Ordered sets, repetitions not allowed] Ordered pairs of distinct people from NNN people: list all N2N^2N2 pairs, then subtract the NNN pairs with a repeated person.Why does this method become hard for ordered triplets or larger sets?

    It is hard to count the nnn -tuples in which some person appears twice (or three times, etc.), which must be subtracted from NnN^nNn . For pairs they are simply the NNN diagonal entries of the square. Filling seats one at a time generalizes easily instead.

30. [Ordered sets, repetitions not allowed] How many ordered sets of nnn objects can be chosen from NNN objects without repetition, written as a product?

    N(N−1)(N−2)⋯(N−(n−1))\boldsymbol{N(N-1)(N-2) \cdots (N-(n-1))}N(N−1)(N−2)⋯(N−(n−1)) Assign the objects to nnn seats one at a time: NNN choices for the first seat, N−1N - 1N−1 for the second, and so on.Example: an ordered committee of 4 from 13 people: 13⋅12⋅11⋅10=17,16013 \cdot 12 \cdot 11 \cdot 10 = 17{,}16013⋅12⋅11⋅10=17,160 .

31. [Ordered sets, repetitions not allowed] In the count N(N−1)(N−2)⋯(N−(n−1))N(N-1)(N-2) \cdots (N-(n-1))N(N−1)(N−2)⋯(N−(n−1)) of ordered sets of nnn objects chosen from NNN without repetition, why is the last factor N−(n−1)N - (n-1)N−(n−1) ?

    When the nnn th seat is filled, n−1n - 1n−1 objects have already been chosen, so N−(n−1)N - (n-1)N−(n−1) are left. Equivalently, it makes the product have exactly nnn factors. Check: n=2n = 2n=2 gives N(N−1)N(N-1)N(N−1) .

32. [Ordered sets, repetitions not allowed] What is NPn_N P_nN​Pn​ , the number of ordered sets of nnn objects chosen from NNN objects without repetition, in terms of factorials?

    NPn=N!(N−n)!\boldsymbol{{}_N P_n = \dfrac{N!}{(N-n)!}}N​Pn​=(N−n)!N!​ Multiply N(N−1)⋯(N−(n−1))N(N-1) \cdots (N-(n-1))N(N−1)⋯(N−(n−1)) by (N−n)!(N−n)!\frac{(N-n)!}{(N-n)!}(N−n)!(N−n)!​ : the numerator becomes N!N!N! .Example: 5P2=5!3!=1206=20_5 P_2 = \frac{5!}{3!} = \frac{120}{6} = 205​P2​=3!5!​=6120​=20 .

33. [Ordered sets, repetitions not allowed] An ordered set of nnn objects chosen from NNN objects without repetition is called a partial permutation (also a kkk -permutation).

    Partial, because only part of the set of NNN objects is permuted. The letter kkk is often used in place of nnn .

34. [Ordered sets, repetitions not allowed] What is NPN_N P_NN​PN​ , and why?

    NPN=N!\boldsymbol{{}_N P_N = N!}N​PN​=N! With n=Nn = Nn=N , the ordered set is a permutation of all NNN objects. In the formula: N!(N−N)!=N!0!=N!\frac{N!}{(N-N)!} = \frac{N!}{0!} = N!(N−N)!N!​=0!N!​=N! , using 0!=10! = 10!=1 .

35. [Ordered sets, repetitions not allowed] How is NPn=N(N−1)⋯(N−(n−1))_N P_n = N(N-1) \cdots (N-(n-1))N​Pn​=N(N−1)⋯(N−(n−1)) (ordered, no repetition) obtained by modifying each of the counts N!N!N! (permutations) and NnN^nNn (ordered, with replacement)?

    From N!N!N! Stop the product N(N−1)(N−2)⋯N(N-1)(N-2) \cdotsN(N−1)(N−2)⋯ after nnn factors instead of going down to 1. In the branching tree: stop branching at the nnn th level. Example: 5P2=5⋅4_5 P_2 = 5 \cdot 45​P2​=5⋅4 , instead of 5!=5⋅4⋅3⋅2⋅15! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 15!=5⋅4⋅3⋅2⋅1 . From NnN^nNn Replace the nnn equal factors N⋅N⋯N \cdot N \cdotsN⋅N⋯ by the decreasing factors N(N−1)⋯N(N-1) \cdotsN(N−1)⋯ , since one object fewer is available at each pick. In the branching tree: one…

36. [Unordered sets, repetitions not allowed] How many unordered pairs of people (e.g. a committee of two equivalent members) can be chosen from 5 people A, B, C, D, E, by first listing all pairs of letters?

    52−52=10\boldsymbol{\frac{5^2 - 5}{2} = 10}252−5​=10 Subtracting 5 removes the pairs with a repeated letter (AA, ..., EE). Dividing by 2 removes the double counting: AB and BA are the same pair.For NNN people: N2−N2=N(N−1)2\frac{N^2 - N}{2} = \frac{N(N-1)}{2}2N2−N​=2N(N−1)​ .

37. [Unordered sets, repetitions not allowed] How many unordered pairs of people can be chosen from 5 people, by filling two seats one at a time?

    5⋅42=10\boldsymbol{\frac{5 \cdot 4}{2} = 10}25⋅4​=10 Filling two seats gives 5⋅4=205 \cdot 4 = 205⋅4=20 ordered pairs, which counts every pair twice (XY and YX), so divide by 2. For NNN people: N(N−1)2\frac{N(N-1)}{2}2N(N−1)​ .

38. [Unordered sets, repetitions not allowed] There are NPn=N!(N−n)!_N P_n = \frac{N!}{(N-n)!}N​Pn​=(N−n)!N!​ ordered sets of nnn objects chosen from NNN without repetition.Why is the number of unordered sets of nnn objects NPnn!\frac{{}_N P_n}{n!}n!N​Pn​​ ?

    Each unordered set of nnn objects is counted n!n!n! times in NPn_N P_nN​Pn​ , once for each of its n!n!n! orderings. Example: a committee of X, Y, Z appears as XYZ, XZY, YXZ, YZX, ZXY, ZYX in NP3_N P_3N​P3​ , so divide by 3!=63! = 63!=6 .

39. [Unordered sets, repetitions not allowed] How many unordered sets of nnn objects can be chosen from NNN objects without repetition?

    (Nn)=N!n! (N−n)!\boldsymbol{\binom{N}{n} = \dfrac{N!}{n!\,(N-n)!}}(nN​)=n!(N−n)!N!​ Also written NCn_N C_nN​Cn​ (C for combinations), and read " NNN choose nnn ".Example: committees of 4 from 6 people: (64)=6!4! 2!=72024⋅2=15\binom{6}{4} = \frac{6!}{4! \, 2!} = \frac{720}{24 \cdot 2} = 15(46​)=4!2!6!​=24⋅2720​=15 .

40. [Unordered sets, repetitions not allowed] The number N!n! (N−n)!\frac{N!}{n!\,(N-n)!}n!(N−n)!N!​ of unordered sets of nnn objects chosen from NNN objects is called a binomial coefficient.

    Written (Nn)\binom{N}{n}(nN​) or NCn_N C_nN​Cn​ , and read " NNN choose nnn ".

41. [Unordered sets, repetitions not allowed] What is the only difference between NPn_N P_nN​Pn​ (ordered sets of nnn from NNN , no repetition) and (Nn)\binom{N}{n}(nN​) (unordered sets of nnn from NNN , no repetition)?

    The division by n!n!n! : (Nn)=NPnn!\binom{N}{n} = \frac{{}_N P_n}{n!}(nN​)=n!N​Pn​​ . The n!n!n! removes the overcounting of the orderings of each set. Neither count allows repetitions.

42. [Unordered sets, repetitions not allowed] What are (NN)\binom{N}{N}(NN​) and (N0)\binom{N}{0}(0N​) , and why do the values make sense?

    Both are 1. (NN)=N!N! 0!=1\binom{N}{N} = \frac{N!}{N! \, 0!} = 1(NN​)=N!0!N!​=1 : there is one way to pick all NNN people. (N0)=N!0! N!=1\binom{N}{0} = \frac{N!}{0! \, N!} = 1(0N​)=0!N!N!​=1 : there is one way to pick no one. Both use 0!=10! = 10!=1 .

43. [Unordered sets, repetitions not allowed] Which other binomial coefficient equals (Nn)\binom{N}{n}(nN​) ?

    (NN−n)\boldsymbol{\binom{N}{N-n}}(N−nN​) : any two lower numbers that add up to NNN give the same value. Example: (64)=(62)=15\binom{6}{4} = \binom{6}{2} = 15(46​)=(26​)=15 , and (113)=(118)=165\binom{11}{3} = \binom{11}{8} = 165(311​)=(811​)=165 .

44. [Unordered sets, repetitions not allowed] Why is (Na)=(NN−a)\binom{N}{a} = \binom{N}{N-a}(aN​)=(N−aN​) algebraically?

    Both equal N!a! (N−a)!\dfrac{N!}{a!\,(N-a)!}a!(N−a)!N!​ : the denominators contain the same two factorials, in the other order. (NN−a)=N!(N−a)! (N−(N−a))!=N!(N−a)! a!\binom{N}{N-a} = \frac{N!}{(N-a)! \, (N-(N-a))!} = \frac{N!}{(N-a)! \, a!}(N−aN​)=(N−a)!(N−(N−a))!N!​=(N−a)!a!N!​

45. [Unordered sets, repetitions not allowed] Why is (Nn)=(NN−n)\binom{N}{n} = \binom{N}{N-n}(nN​)=(N−nN​) , explained in words?

    Choosing the nnn objects that are picked is the same as choosing the N−nN - nN−n objects that are not picked. Each set of nnn objects corresponds to exactly one complementary set of N−nN - nN−n objects, so the two numbers of sets are equal.Example: picking a committee of 2 from 6 people is the same as picking the 4 people who are not on it.

46. [Unordered sets, repetitions not allowed] When computing (Nn)\binom{N}{n}(nN​) by hand, which factorial in the denominator should you cancel against N!N!N! ?

    The larger one. Example: (113)=(118)=11!3! 8!=11⋅10⋅93⋅2⋅1=165\binom{11}{3} = \binom{11}{8} = \frac{11!}{3! \, 8!} = \frac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165(311​)=(811​)=3!8!11!​=3⋅2⋅111⋅10⋅9​=165 .

47. [Unordered sets, repetitions not allowed] From 10 people, how many committees can be formed that consist of a president, two (equivalent) vice presidents and four (equivalent) regular members?

    12,600\boldsymbol{12{,}600}12,600 Pick the president, then the vice presidents from the remaining 9, then the regular members from the remaining 7: (101)(92)(74)=10⋅36⋅35=12,600\binom{10}{1}\binom{9}{2}\binom{7}{4} = 10 \cdot 36 \cdot 35 = 12{,}600(110​)(29​)(47​)=10⋅36⋅35=12,600

48. [Unordered sets, repetitions not allowed] From 10 people, form a committee of a president, two (equivalent) vice presidents and four (equivalent) regular members.How do you count the committees starting from 10P7_{10} P_710​P7​ , the number of ordered sets of 7 of the 10 people?

    10P74! 2!=10⋅9⋅8⋅7⋅6⋅5⋅44!⋅2!=12,600\boldsymbol{\dfrac{{}_{10} P_7}{4! \, 2!} = \dfrac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4}{4! \cdot 2!} = 12{,}600}4!2!10​P7​​=4!⋅2!10⋅9⋅8⋅7⋅6⋅5⋅4​=12,600 Seat the 7 in a row: president in seat 1, vice presidents in seats 2 and 3, regular members in seats 4 to 7. The order of the 2 vice presidents doesn't matter (divide by 2!2!2! ), nor the order of the 4 regular members (divide by 4!4!4! ). 604,800/48=12,600604{,}800 / 48 = 12{,}600604,800/48=12,…

49. [Unordered sets, repetitions not allowed] From 10 people, form a committee of a president, two (equivalent) vice presidents and four (equivalent) regular members.Does the order in which the parts of the committee are picked change the count?

    No, every order gives 12,600, since the number of committees can't depend on a valid counting method. Every order gives the numerator 10⋅9⋅8⋅7⋅6⋅5⋅410 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 410⋅9⋅8⋅7⋅6⋅5⋅4 and the denominator 1!⋅2!⋅4!1! \cdot 2! \cdot 4!1!⋅2!⋅4! .Example: regular members first: (104)(62)(41)=210⋅15⋅4=12,600\binom{10}{4}\binom{6}{2}\binom{4}{1} = 210 \cdot 15 \cdot 4 = 12{,}600(410​)(26​)(14​)=210⋅15⋅4=12,600 .Example: all 7 first, then the president, then the vice presid…

50. [Unordered sets, repetitions not allowed] A standard deck has 52 cards: 4 suits for each of the 13 values 2, ..., 10, J, Q, K, A. A full house is a five-card hand with three cards of one value and two of another (e.g. 999QQ). How many full houses are there?

    13⋅12⋅(43)(42)=156⋅24=3,744\boldsymbol{13 \cdot 12 \cdot \binom{4}{3} \binom{4}{2} = 156 \cdot 24 = 3{,}744}13⋅12⋅(34​)(24​)=156⋅24=3,744 13⋅12=15613 \cdot 12 = 15613⋅12=156 types (value occurring three times, value occurring twice), and for each type, (43)=4\binom{4}{3} = 4(34​)=4 choices of the three suits and (42)=6\binom{4}{2} = 6(24​)=6 of the two suits.Out of (525)=2,598,960\binom{52}{5} = 2{,}598{,}960(552​)=2,598,960 five-card hands, so about 0.14%0.14\%0.14% of all hands.

51. [Unordered sets, repetitions not allowed] A full house is a five-card hand with three cards of one value and two of another (13 values, 4 suits each), e.g. 999QQ.Why is the number of types (like 999QQ) 13P2=13⋅12=156_{13} P_2 = 13 \cdot 12 = 15613​P2​=13⋅12=156 and not (132)=78\binom{13}{2} = 78(213​)=78 ?

    The order of the two values matters: three 9s and two Qs is a different hand type from three Qs and two 9s. Equivalently: (132)\binom{13}{2}(213​) pairs of values, times 2 for which value occurs three times.If a hand were 4 cards of type AABB, the number of types would be (132)\binom{13}{2}(213​) , since both values occur twice.

52. [Unordered sets, repetitions not allowed] A full house is a five-card hand with three cards of one value and two of another (13 values, 4 suits each), e.g. 999QQ.Why are the three 9s of 999QQ chosen in (43)\binom{4}{3}(34​) ways and not 4P3_4 P_34​P3​ ways?

    The order of the cards in a hand doesn't matter. So (43)=4\binom{4}{3} = 4(34​)=4 choices of three of the four 9s, and (42)=6\binom{4}{2} = 6(24​)=6 of two of the four Qs: 24 hands of type 999QQ.

53. [What we know so far] What are the formulas for permutations of NNN objects, and for choosing nnn of NNN objects ordered with repetition, ordered without repetition, and unordered without repetition?

    Permutations of NNN objects N!N!N! Example: A, B, C can be ordered in 3!=63! = 63!=6 ways. Ordered, repetitions allowed NnN^nNn ( nnn objects chosen from NNN ) Example: rolling a die twice gives 62=366^2 = 3662=36 ordered outcomes. Ordered, repetitions not allowed NPn=N!(N−n)!\displaystyle {}_N P_n = \frac{N!}{(N-n)!}N​Pn​=(N−n)!N!​ Example: president and vice-president from 5 people: 5P2=5⋅4=20 {}_5 P_2 = 5 \cdot 4 = 205​P2​=5⋅4=20 . Unordered, repetitions not allowed NCn=(Nn)=N!n!(N−n)!\displ…

54. [What we know so far] Among the results N!N!N! , NnN^nNn , NPn {}_N P_nN​Pn​ and (Nn)\binom{N}{n}(nN​) , which one is of a different kind, and why?

    N!N!N! : it is the special case n=Nn = Nn=N , while the other three choose a general number nnn of objects from NNN . How the four results are obtained from each other.

55. [Unordered sets, repetitions allowed] Picking nnn objects from NNN objects: whether we replace or not, and whether order matters or not, gives 4 scenarios. Which scenario does this table leave open? with replacementwithout replacementorder mattersNnN!(N−n)!order doesn’t matter?N!n!(N−n)!\begin{array}{c|c|c} & \text{with replacement} & \text{without replacement} \\ \hline \text{order matters} & N^n & \dfrac{N!}{(N-n)!} \\[2ex] \hline \text{order doesn't matter} & ? & \dfrac{N!}{n!(N-n)!} \e…

    With replacement, order doesn't matter. Example: rolling five dice in a group (as in Yahtzee), where only which numbers come up counts.

56. [Unordered sets, repetitions allowed] Rolling five dice in a group, where the order of the dice doesn't matter, is the same as drawing which balls from a box?

    n=5n = 5n=5 balls from a box of N=6N = 6N=6 balls labeled 1 to 6, with replacement, order not mattering.

57. [Unordered sets, repetitions allowed] How many different sets of 4 letters can you pick from the letters A, B, C, with replacement and with the order not mattering?

    15 typeAAAAAAABAABBAABCsets3633\begin{array}{c|c|c|c|c} \text{type} & \text{AAAA} & \text{AAAB} & \text{AABB} & \text{AABC} \\ \hline \text{sets} & 3 & 6 & 3 & 3 \end{array}typesets​AAAA3​AAAB6​AABB3​AABC3​​ 3+6+3+3=15=(62)3 + 6 + 3 + 3 = 15 = \binom{6}{2}3+6+3+3=15=(26​) . There are 15 sets but only 4 types of sets.

58. [Unordered sets, repetitions allowed] Picking 4 letters from A, B, C, with replacement and the order not mattering, there are 3⋅2=63 \cdot 2 = 63⋅2=6 sets of the type AAAB (3 choices for the letter that appears three times, then 2 for the letter that appears once).Why are there only 3 sets of the type AABB, not 3⋅2=63 \cdot 2 = 63⋅2=6 ?

    Two A's and two B's is the same set as two B's and two A's, so you only choose which 2 letters appear: (32)=3\binom{3}{2} = 3(23​)=3 .

59. [Unordered sets, repetitions allowed] Picking 4 letters from A, B, C with replacement, the unordered sets CCCA and BBBB each count as one of the 15 possible sets.If each draw is A, B or C with equal probability, why is CCCA 4 times as likely as BBBB?

    CCCA arises from 4 ordered draws (CCCA, CCAC, CACC, ACCC), BBBB from only 1. Each of the 34=813^4 = 8134=81 ordered sequences is equally likely; the unordered sets are not.

60. [Unordered sets, repetitions allowed] How many different sets of 3 letters can you pick from A, B, C, D, with replacement and with the order not mattering?

    20 typeAAAAABABCsets4124\begin{array}{c|c|c|c} \text{type} & \text{AAA} & \text{AAB} & \text{ABC} \\ \hline \text{sets} & 4 & 12 & 4 \end{array}typesets​AAA4​AAB12​ABC4​​ AAB: 4 choices for the letter that appears twice, then 3 for the letter that appears once. 4+12+4=20=(63)4 + 12 + 4 = 20 = \binom{6}{3}4+12+4=20=(36​) .

61. [Unordered sets, repetitions allowed] How many different sets of 5 letters can you pick from A, B, C, with replacement and with the order not mattering?

    21 typeAAAAAAAAABAAABBAAABCAABBCsets36633\begin{array}{c|c|c|c|c|c} \text{type} & \text{AAAAA} & \text{AAAAB} & \text{AAABB} & \text{AAABC} & \text{AABBC} \\ \hline \text{sets} & 3 & 6 & 6 & 3 & 3 \end{array}typesets​AAAAA3​AAAAB6​AAABB6​AAABC3​AABBC3​​ 3+6+6+3+3=21=(72)3 + 6 + 6 + 3 + 3 = 21 = \binom{7}{2}3+6+6+3+3=21=(27​) .

62. [Unordered sets, repetitions allowed] What is NUn {}_N U_nN​Un​ , and what is its formula?

    The number of ways to pick nnn objects from NNN objects, with replacement and with the order not mattering: NUn=(n+(N−1)N−1)\displaystyle \boldsymbol{{}_N U_n = \binom{n + (N-1)}{N-1}}N​Un​=(N−1n+(N−1)​) UUU stands for "unordered".Example: 4 letters from A, B, C: 3U4=(4+22)=(62)=15 {}_3 U_4 = \binom{4 + 2}{2} = \binom{6}{2} = 153​U4​=(24+2​)=(26​)=15 .

63. [Unordered sets, repetitions allowed] Stars and bars. How is an unordered set of nnn letters, picked with replacement from NNN letters, written as stars and bars?

    List the letters alphabetically, write each as a star, and put a bar at each transition from one letter to the next. The number of stars before the first bar is the number of A's, between the first and second bar the number of B's, and so on. Example: with N=3N = 3N=3 : AAABCC (top) and BBBBBC (bottom, no A's).

64. [Unordered sets, repetitions allowed] In stars and bars for picking nnn letters with replacement from NNN letters (order not mattering), why are there N−1N - 1N−1 bars and (n+(N−1)N−1)\binom{n + (N-1)}{N-1}(N−1n+(N−1)​) configurations?

    NNN letters have N−1N - 1N−1 transitions between them, so we choose which N−1N - 1N−1 of the n+(N−1)n + (N-1)n+(N−1) places hold bars. Each placement of the bars gives a different set of letters, and every set arises this way. Example: n=6n = 6n=6 , N=3N = 3N=3 : 8 places, 2 bars: (82)=28\binom{8}{2} = 28(28​)=28 sets.

65. [Unordered sets, repetitions allowed] In NUn=(n+(N−1)N−1) {}_N U_n = \binom{n + (N-1)}{N-1}N​Un​=(N−1n+(N−1)​) , from which number is 1 subtracted: nnn (the number of picks) or NNN (the number of distinct letters)?

    From NNN , the number of distinct letters. NNN letters need N−1N - 1N−1 bars between them; the nnn picks are the nnn stars.Example: 1 pick from 3 letters gives the 3 sets A, B, C, and (1+22)=3\binom{1 + 2}{2} = 3(21+2​)=3 ; subtracting 1 from nnn instead would give (0+33)=1\binom{0 + 3}{3} = 1(30+3​)=1 .

66. [Unordered sets, repetitions allowed] In stars and bars with the letters A, B, C, D (picked with replacement, order not mattering), which set does this configuration represent?

    ABBBDD 1 star before the first bar (one A), 3 stars next (three B's), none between the second and third bar (no C), 2 stars after the last bar (two D's).

67. [Unordered sets, repetitions allowed] Why is NUn=(n+(N−1)N−1) {}_N U_n = \binom{n + (N-1)}{N-1}N​Un​=(N−1n+(N−1)​) also equal to (n+(N−1)n)\binom{n + (N-1)}{n}(nn+(N−1)​) ?

    Choosing the N−1N - 1N−1 places for the bars is the same as choosing the nnn places for the stars. Example: n=6n = 6n=6 , N=3N = 3N=3 : (82)=(86)=28\binom{8}{2} = \binom{8}{6} = 28(28​)=(68​)=28 .

68. [Unordered sets, repetitions allowed] Choosing nnn of NNN objects: what goes in place of ? (as a formula with factorials)? with replacementwithout replacementorder mattersNnN!(N−n)!order doesn’t matter?N!n!(N−n)!\begin{array}{c|c|c} & \text{with replacement} & \text{without replacement} \\ \hline \text{order matters} & N^n & \dfrac{N!}{(N-n)!} \\[2ex] \hline \text{order doesn't matter} & ? & \dfrac{N!}{n!(N-n)!} \end{array}order mattersorder doesn’t matter​with replacementNn?​without repla…

    (n+N−1)!n!(N−1)!\boldsymbol{\dfrac{(n + N - 1)!}{n!(N-1)!}}n!(N−1)!(n+N−1)!​ This is (n+N−1n)=(n+N−1N−1)\binom{n + N - 1}{n} = \binom{n + N - 1}{N - 1}(nn+N−1​)=(N−1n+N−1​) , the number of ways to pick nnn of NNN objects with replacement, order not mattering.

69. [Unordered sets, repetitions allowed] The number of ways to pick nnn objects from NNN objects, with replacement and with the order not mattering, is NUn=(n+(N−1)N−1) {}_N U_n = \binom{n + (N-1)}{N-1}N​Un​=(N−1n+(N−1)​) .What does this give for N=1N = 1N=1 , and for n=1n = 1n=1 ? Why are these right?

    N=1N = 1N=1 : (n0)=1\binom{n}{0} = 1(0n​)=1 . n=1\ n = 1 n=1 : (NN−1)=N\binom{N}{N-1} = N(N−1N​)=N . With one letter A, the only set is AA...A. With one pick, the NNN possible sets are A1,…,ANA_1, \dots, A_NA1​,…,AN​ .

70. [Unordered sets, repetitions allowed] Dividing the money. In how many ways can you divide ten identical one-dollar bills among four (distinguishable) people?

    (10+33)=(133)=286\displaystyle \boldsymbol{\binom{10 + 3}{3} = \binom{13}{3} = 286}(310+3​)=(313​)=286 Example: amounts 4, 0, 3, 3 and 3, 4, 0, 3 count as different divisions.

71. [Unordered sets, repetitions allowed] Why is the number of ways to divide nnn identical dollar bills among NNN people equal to the number of ways to pick nnn letters from NNN letters, with replacement and with the order not mattering?

    Label the people with the letters; a person receives one dollar each time their letter is drawn. Since it doesn't matter when a person gets a given bill, the order of the letters is irrelevant: the string CBBDCBDBAD is the same as ABBBBCCDDD, i.e. amounts 1, 4, 2, 3.

72. [Unordered sets, repetitions allowed] Which counting problems all have the answer (n+(N−1)N−1)\binom{n + (N-1)}{N-1}(N−1n+(N−1)​) ?

    Unordered strings with repetition Pick nnn letters from NNN letters, with replacement, order not mattering. Example: 4 letters from A, B, C: (62)=15\binom{6}{2} = 15(26​)=15 . Money partitions Divide nnn identical dollar bills among NNN people. Example: 10 dollars among 4 people: (133)=286\binom{13}{3} = 286(313​)=286 . Balls into boxes Put nnn identical balls into NNN boxes. Example: 2 balls into 2 boxes: 2+0, 1+1, 0+2, so (31)=3\binom{3}{1} = 3(13​)=3 . Sums of non-negative integers Write nnn…

73. [Unordered sets, repetitions allowed] Picking 4 letters from A, B, C with replacement, the unordered sets are 3 of type AAAA, 6 of type AAAB, 3 of type AABB and 3 of type AABC. How do these numbers reproduce the 34=813^4 = 8134=81 ordered sets?

    Multiply each type by its number of orderings: 3⋅1+6⋅4+3⋅6+3⋅12=813 \cdot 1 + 6 \cdot 4 + 3 \cdot 6 + 3 \cdot 12 = 813⋅1+6⋅4+3⋅6+3⋅12=81 . AAAA has 1 ordering, AAAB 4, AABB (42)=6\binom{4}{2} = 6(24​)=6 , AABC 12.

74. [Unordered sets, repetitions allowed] Why are there 12 orderings of the letters AABC?

    4 places for the B, then 3 places for the C: 4⋅3=124 \cdot 3 = 124⋅3=12 . Alternatively: (42)=6\binom{4}{2} = 6(24​)=6 ways to place the A's, then 2 ways to order B and C.

75. [Unordered sets, repetitions allowed] Why is counting unordered sets with replacement less useful in probability than the other three counting scenarios?

    These sets are not all equally likely, while in the other three scenarios they are (if each object in the box is equally likely to be drawn). Example: drawing 4 times from A, B, C, the set CCCA arises from 4 orderings, the set BBBB from only 1.

76. [Unordered sets, repetitions allowed] "With replacement" means the same as identical trials; "without replacement" means the same as depleting trials.

    In depleting trials the number of possible outcomes decreases by 1 after each trial. Example: rolling dice and flipping coins are identical trials; picking a committee and assigning people to seats are depleting trials.

77. [Unordered sets, repetitions allowed] Describe each of the four scenarios (with/without replacement, order matters/doesn't) in a short phrase.

    With replacement: identical trials; without: depleting trials. Order matters: in a line; order doesn't matter: in a blob. with replacementwithout replacementorder mattersidentical trials in a linedepleting trials in a lineorder doesn’t matteridentical trials in a blobdepleting trials in a blob\begin{array}{c|c|c} & \text{with replacement} & \text{without replacement} \\ \hline \text{order matters} & \text{identical trials in a line} & \text{depleting trials in a line} \\ \hline \text{order does…

78. [Unordered sets, repetitions allowed] What is a standard example of each of the four scenarios (with/without replacement, order matters/doesn't)?

    With replacement, order matters Ordered dice rolls: NnN^nNn With replacement, order doesn't matter Unordered dice rolls: (n+N−1N−1)\binom{n + N - 1}{N - 1}(N−1n+N−1​) Without replacement, order matters Committees with distinct assignments (e.g. president, treasurer): N!(N−n)!\dfrac{N!}{(N-n)!}(N−n)!N!​ Without replacement, order doesn't matter Committees with equivalent members: (Nn)\dbinom{N}{n}(nN​)

79. [Binomial coefficients] Flipping 4 coins: in how many ways can you get exactly 0, 1, 2, 3, 4 Heads?

    1, 4, 6, 4, 1 1+4+6+4+1=16=241 + 4 + 6 + 4 + 1 = 16 = 2^41+4+6+4+1=16=24 , the total number of outcomes.

80. [Binomial coefficients] What does row nnn of Pascal's triangle list, in terms of coin flips?

    The numbers of ways to get exactly 0,1,…,n0, 1, \dots, n0,1,…,n Heads in nnn coin flips. n=0:1n=1:11n=2:121n=3:1331n=4:14641\begin{array}{lccccccccc} n = 0: &&&&& 1 \\ n = 1: &&&& 1 && 1 \\ n = 2: &&& 1 && 2 && 1 \\ n = 3: && 1 && 3 && 3 && 1 \\ n = 4: & 1 && 4 && 6 && 4 && 1 \end{array}n=0:n=1:n=2:n=3:n=4:​1​1​14​13​126​13​14​1​1​ Row n=0n = 0n=0 is a single 1: with zero coins there is exactly one outcome, zero Heads.

81. [Binomial coefficients] What are rows n=5n = 5n=5 and n=6n = 6n=6 of Pascal's triangle?

    1, 5, 10, 10, 5, 1 and 1, 6, 15, 20, 15, 6, 1 Each entry is the sum of the two entries above it, e.g. 15=5+1015 = 5 + 1015=5+10 , 20=10+1020 = 10 + 1020=10+10 .

82. [Binomial coefficients] Why is the number of ways to get exactly kkk Heads in nnn coin flips equal to (nk)\binom{n}{k}(kn​) (the number of kkk -person committees from nnn people)?

    Choosing which kkk of the nnn flips are Heads is choosing a kkk -person committee from nnn people. Seat the nnn people in a row; person iii is on the committee exactly when flip iii is Heads.Example: 2 Heads in 6 flips: (62)=15\binom{6}{2} = 15(26​)=15 ways.

83. [Binomial coefficients] What is the sum of row nnn of Pascal's triangle, (n0)+(n1)+⋯+(nn)\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n}(0n​)+(1n​)+⋯+(nn​) , and why, in terms of coin flips?

    2n\boldsymbol{2^n}2n Both sides count all outcomes of nnn coin flips; the left side sorts them by the number of Heads.Example: 1+4+6+4+1=16=241 + 4 + 6 + 4 + 1 = 16 = 2^41+4+6+4+1=16=24 .

84. [Binomial coefficients] Expand (a+b)4(a + b)^4(a+b)4 .

    a4+4a3b+6a2b2+4ab3+b4\boldsymbol{a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4}a4+4a3b+6a2b2+4ab3+b4 The coefficients are row n=4n = 4n=4 of Pascal's triangle.

85. [Binomial coefficients] Multiplying out (a+b)5=(a+b)(a+b)(a+b)(a+b)(a+b)(a + b)^5 = (a+b)(a+b)(a+b)(a+b)(a+b)(a+b)5=(a+b)(a+b)(a+b)(a+b)(a+b) without collecting terms, how many terms do you get, and why?

    25=32\boldsymbol{2^5 = 32}25=32 Each term picks either aaa or bbb from each of the 5 factors. E.g. aaa from factors 1 and 3, bbb from factors 2, 4, 5 gives ababb=a2b3ababb = a^2b^3ababb=a2b3 .

86. [Binomial coefficients] What is the coefficient of a2b3a^2b^3a2b3 in (a+b)5(a + b)^5(a+b)5 , and why?

    (53)=10\boldsymbol{\binom{5}{3} = 10}(35​)=10 A term a2b3a^2b^3a2b3 arises by choosing which 3 of the 5 factors (a+b)(a + b)(a+b) contribute bbb (equivalently, which 2 contribute aaa : (52)=10\binom{5}{2} = 10(25​)=10 ).

87. [Binomial coefficients] Binomial theorem. (a+b)n= ?(a + b)^n = \; ?(a+b)n=?

    ∑k=0n(nk)an−kbk\displaystyle \boldsymbol{\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k}k=0∑n​(kn​)an−kbk =(n0)an+(n1)an−1b+⋯+(nn−1)abn−1+(nn)bn= \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \dots + \binom{n}{n-1}ab^{n-1} + \binom{n}{n}b^n=(0n​)an+(1n​)an−1b+⋯+(n−1n​)abn−1+(nn​)bn , for any values of aaa and bbb . Also called the binomial expansion or binomial formula.Example: (a+b)3=a3+3a2b+3ab2+b3(a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3(a+b)3=a3+3a2b+3ab2+b3 .

88. [Binomial coefficients] How does the binomial theorem prove (n0)+(n1)+⋯+(nn)=2n\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n(0n​)+(1n​)+⋯+(nn​)=2n , without coin flips?

    Set a=b=1a = b = 1a=b=1 in (a+b)n=∑k=0n(nk)an−kbk(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k(a+b)n=∑k=0n​(kn​)an−kbk . The right side becomes ∑k(nk)\sum_k \binom{n}{k}∑k​(kn​) , the left side (1+1)n=2n(1 + 1)^n = 2^n(1+1)n=2n .

89. [Binomial coefficients] Which three questions have the answer (nk)\binom{n}{k}(kn​) ?

    Committees How many different (unordered) committees of kkk people can be chosen from nnn people? Example: 2 of 4 people: (42)=6\binom{4}{2} = 6(24​)=6 . Coin flips Flip a coin nnn times. How many outcomes have exactly kkk Heads? Example: 2 Heads in 4 flips: (42)=6\binom{4}{2} = 6(24​)=6 . Binomial expansion What is the coefficient of an−kbka^{n-k}b^kan−kbk in (a+b)n(a + b)^n(a+b)n ? Example: a2b2a^2b^2a2b2 in (a+b)4(a + b)^4(a+b)4 : (42)=6\binom{4}{2} = 6(24​)=6 . In each case a binary choice…

90. [Binomial coefficients] For committees, coin flips and the expansion of (a+b)n(a + b)^n(a+b)n , what does the substitution k→n−kk \to n - kk→n−k in (nk)\binom{n}{k}(kn​) correspond to?

    Choosing the kkk people not on the committee, replacing Heads with Tails, or replacing an−kbka^{n-k}b^kan−kbk with akbn−ka^kb^{n-k}akbn−k . The count stays the same: (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}(kn​)=(n−kn​) .Example: (52)=(53)=10\binom{5}{2} = \binom{5}{3} = 10(25​)=(35​)=10 .

91. [Binomial coefficients] Why are the numbers (nk)\binom{n}{k}(kn​) called binomial coefficients?

    They are the coefficients in the expansion of (a+b)n(a + b)^n(a+b)n , the power of a binomial. Morin first defines (nk)\binom{n}{k}(kn​) as the number of unordered subgroups of kkk of nnn objects and only then shows that these are the coefficients. Both equal n!k!(n−k)!\frac{n!}{k!(n-k)!}k!(n−k)!n!​ .

92. [Binomial coefficients] How is each entry of row nnn of Pascal's triangle obtained from row n−1n - 1n−1 ? Give the formula.

    It is the sum of the two entries above it: (nk)=(n−1k−1)+(n−1k)\displaystyle \boldsymbol{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}(kn​)=(k−1n−1​)+(kn−1​) At the end of a row there is only one entry above, a 1.Example: (63)=(52)+(53)\binom{6}{3} = \binom{5}{2} + \binom{5}{3}(36​)=(25​)+(35​) , i.e. 20=10+1020 = 10 + 1020=10+10 .

93. [Binomial coefficients] Why does (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}(kn​)=(k−1n−1​)+(kn−1​) hold, in terms of committees?

    Single out one person, Alice: (n−1k−1)\binom{n-1}{k-1}(k−1n−1​) committees of kkk people contain her, (n−1k)\binom{n-1}{k}(kn−1​) don't. If Alice is on the committee, the other k−1k - 1k−1 members come from the remaining n−1n - 1n−1 people; if not, all kkk do.Example: n=4n = 4n=4 , k=2k = 2k=2 : 3 pairs contain Alice, 3 don't, 6=3+36 = 3 + 36=3+3 .

94. [Problems] Six girls and four boys are assigned to ten seats in a row, so that a girl sits in the 3rd seat and a boy in the 8th seat. How many arrangements are possible?

    6⋅4⋅8!=967,680\boldsymbol{6 \cdot 4 \cdot 8! = 967{,}680}6⋅4⋅8!=967,680 6 choices for the girl in seat 3, then 4 for the boy in seat 8, then 8!8!8! orders of the remaining 8 people in the remaining 8 seats.Without the conditions there would be 10!=3,628,80010! = 3{,}628{,}80010!=3,628,800 ; the conditions keep the fraction 6⋅410⋅9≈0.27\frac{6 \cdot 4}{10 \cdot 9} \approx 0.2710⋅96⋅4​≈0.27 of them.

95. [Problems] From NNN people, ordered triplets are formed with repetitions allowed ( N3N^3N3 of them). How many contain a repeated person, and what is left after subtracting them?

    3N2−2N3N^2 - 2N3N2−2N contain a repeat; N3−(3N2−2N)=N(N−1)(N−2)N^3 - (3N^2 - 2N) = N(N-1)(N-2)N3−(3N2−2N)=N(N−1)(N−2) are left, the number of ordered triplets without repetition. Type AAA: NNN triplets. Type AAB: NNN choices for A, N−1N - 1N−1 for B, and 3 orders (AAB, ABA, BAA), so 3N(N−1)3N(N-1)3N(N−1) .Example: N=5N = 5N=5 : 5+60=655 + 60 = 655+60=65 triplets with a repeat, and 125−65=60=5⋅4⋅3125 - 65 = 60 = 5 \cdot 4 \cdot 3125−65=60=5⋅4⋅3 .

96. [Problems] Ordered quadruplets are formed from 5 people, repetitions allowed ( 54=6255^4 = 62554=625 of them). Into which types do the quadruplets with a repeated person fall, and how many of each are there?

    AAAA: 555 5 choices of A. AAAB: 5⋅4⋅4=805 \cdot 4 \cdot 4 = 805⋅4⋅4=80 5 choices of A, 4 of B, 4 positions for B. AABB: (52)⋅(42)=10⋅6=60\binom{5}{2} \cdot \binom{4}{2} = 10 \cdot 6 = 60(25​)⋅(24​)=10⋅6=60 (52)\binom{5}{2}(25​) choices of the two letters, (42)\binom{4}{2}(24​) choices of the positions of A. AABC: 5⋅(42)⋅12=3605 \cdot \binom{4}{2} \cdot 12 = 3605⋅(24​)⋅12=360 5 choices of A, (42)\binom{4}{2}(24​) of {B,C}\{B, C\}{B,C} , then 4⋅3=124 \cdot 3 = 124⋅3=12 choices of the positions of…

97. [Problems] How does Gauss's trick show that 1+2+⋯+N=N(N+1)21 + 2 + \dots + N = \frac{N(N+1)}{2}1+2+⋯+N=2N(N+1)​ ?

    Write 1,2,…,N1, 2, \dots, N1,2,…,N above N,N−1,…,1N, N-1, \dots, 1N,N−1,…,1 : each of the NNN columns sums to N+1N + 1N+1 , so the two rows total N(N+1)N(N+1)N(N+1) , which counts every number twice. The story: as a schoolboy, Gauss (1777 to 1855) was told to add the numbers 1 through 100 and quickly answered 5050.Example: 1+2+3+4=4⋅52=101 + 2 + 3 + 4 = \frac{4 \cdot 5}{2} = 101+2+3+4=24⋅5​=10 .

98. [Problems] Why does the number of unordered pairs chosen from NNN people, (N2)\binom{N}{2}(2N​) , equal 1+2+⋯+(N−1)1 + 2 + \dots + (N - 1)1+2+⋯+(N−1) ?

    Group the pairs by their alphabetically later member: the jjj -th person is the later member of j−1j - 1j−1 pairs. So 1+2+⋯+(N−1)=(N2)=N(N−1)21 + 2 + \dots + (N - 1) = \binom{N}{2} = \frac{N(N-1)}{2}1+2+⋯+(N−1)=(2N​)=2N(N−1)​ , another proof of the formula for 1+⋯+N1 + \dots + N1+⋯+N .Example: for A, B, C, D, E the pairs are AB; AC, BC; AD, BD, CD; AE, BE, CE, DE, i.e. 1+2+3+4=10=(52)1 + 2 + 3 + 4 = 10 = \binom{5}{2}1+2+3+4=10=(25​) .

99. [Problems] Proof by induction that 1+2+⋯+N=N(N+1)21 + 2 + \dots + N = \frac{N(N+1)}{2}1+2+⋯+N=2N(N+1)​ : what is the inductive step?

    N(N+1)2+(N+1)=(N+1)(N2+1)=(N+1)(N+2)2\boldsymbol{\frac{N(N+1)}{2} + (N + 1) = (N+1)\left(\frac{N}{2} + 1\right) = \frac{(N+1)(N+2)}{2}}2N(N+1)​+(N+1)=(N+1)(2N​+1)=2(N+1)(N+2)​ If the formula holds for NNN , then adding N+1N + 1N+1 gives the formula with NNN replaced by N+1N + 1N+1 . Together with the case N=1N = 1N=1 ( 1=1⋅221 = \frac{1 \cdot 2}{2}1=21⋅2​ ), this gives the formula for N=2,3,4,…N = 2, 3, 4, \dotsN=2,3,4,…

100. [Problems] Why is the base case ( N=1N = 1N=1 ) essential in an induction proof?

     The inductive step alone can hold for a false formula: then the chain of implications has no case to start from. Example: 1+⋯+N=N(N+1)2+731 + \dots + N = \frac{N(N+1)}{2} + 731+⋯+N=2N(N+1)​+73 satisfies the inductive step (add N+1N + 1N+1 to both sides), but it holds for no NNN .