When order does­n't mat­ter

Pick­ing a team of 33 from 88 play­ers is not the same as giv­ing out 33 medals. With medals, who gets gold mat­ters. In a team, it does­n't; the same three peo­ple make the same team whichever way you name them. That is the whole dif­fer­ence between a per­mu­ta­tion and a com­bi­na­tion. We will define com­bi­na­tions, get the for­mula nCr=n!r!(n−r)!\displaystyle ^nC_r = \tfrac{n!}{r!(n - r)!} from what we know about per­mu­ta­tions, prove the key iden­ti­ties, and then solve selec­tion prob­lems (com­mit­tees, teams and hands of cards), includ­ing the "at least" and "at most" kind.

Com­bi­na­tions

A selec­tion of rr objects from nn dis­tinct objects, where order is ignored, is a com­bi­na­tion. Here is the neat link with per­mu­ta­tions. Each com­bi­na­tion of rr objects can be arranged in r!r! ways, and doing that for every com­bi­na­tion pro­duces every per­mu­ta­tion exactly once. So

nCr⋅r!=nPr⟹nCr=n!r! (n−r)!.\displaystyle ^nC_r \cdot r! = {}^nP_r \quad\Longrightarrow\quad {}^nC_r = \frac{n!}{r!\,(n - r)!}.

Iden­ti­ties. First, nC0=nCn=1^nC_0 = {}^nC_n = 1. Next, nCr=nCn−r^nC_r = {}^nC_{n-r}, because choos­ing who is in is the same as choos­ing who is left out. It fol­lows that nCa=nCb⇒a=b^nC_a = {}^nC_b \Rightarrow a = b or a+b=na + b = n. Finally there is Pas­cal's rule, nCr+nCr−1=n+1Cr^nC_r + {}^nC_{r-1} = {}^{n+1}C_r.

Exam­ple 1. From 88 play­ers you can form 8C3=8⋅7⋅66=56\displaystyle ^8C_3 = \tfrac{8 \cdot 7 \cdot 6}{6} = 56 teams of 33.

Exam­ple 2. If nC9=nC7^nC_9 = {}^nC_7, the two lower num­bers must add up to the top one, so n=16n = 16, and then nC2=120^nC_2 = 120.

Selec­tions with con­di­tions

For "at least" or "at most", don't try to do it in one go. Split the prob­lem into sep­a­rate cases, count each one, and add.

Exam­ple 3. A com­mit­tee of 55 is cho­sen from 66 men and 44 women. With exactly 22 women, choose the women and the men sep­a­rately: 4C2×6C3=6×20=120^4C_2 \times {}^6C_3 = 6 \times 20 = 120. With at least 22 women, add up the cases of two, three and four women: 4C2 6C3+4C3 6C2+4C4 6C1=120+60+6=186^4C_2\,{}^6C_3 + {}^4C_3\,{}^6C_2 + {}^4C_4\,{}^6C_1 = 120 + 60 + 6 = 186.

Exam­ple 4. From a pack of 5252 cards, the num­ber of 55-card hands with exactly one ace is 4C1×48C4=4×194,580=778,320^4C_1 \times {}^{48}C_4 = 4 \times 194{,}580 = 778{,}320.

Exam­ple 5. A stu­dent must answer 88 of 1212 ques­tions, includ­ing at least 33 of the first 55. The cases give 5C3 7C5+5C4 7C4+5C5 7C3=210+175+35=420^5C_3\,{}^7C_5 + {}^5C_4\,{}^7C_4 + {}^5C_5\,{}^7C_3 = 210 + 175 + 35 = 420.

Exam­ple 6: lines and tri­an­gles. Take 1010 points in a plane, no three on a line. Any two points fix a line and any three fix a tri­an­gle, so there are 10C2=45^{10}C_2 = 45 lines and 10C3=120^{10}C_3 = 120 tri­an­gles. In the same way, a poly­gon with nn sides has nC2−n^nC_2 - n diag­o­nals, since the sides are not diag­o­nals. A hexa­gon has 99.

Regular hexagon with its 6 sides drawn thick and all 9 diagonals drawn in orange, next to the count 6C2 - 6 = 15 - 6 = 9.
Exam­ple 6: a hexa­gon has 15 join­ing lines, 6 of them sides, so 9 diag­o­nals

Exam­ple 7: choose, then arrange. Many prob­lems need both tools. How many words of 22 vow­els and 33 con­so­nants can be made from the let­ters of DAUGH­TER (vow­els A, U, E; con­so­nants D, G, H, T, R)? First choose the let­ters, then arrange them: 3C2×5C3×5!=3×10×120=3600^3C_2 \times {}^5C_3 \times 5! = 3 \times 10 \times 120 = 3600.

Prac­tice ques­tions

  1. Eval­u­ate 12C4^{12}C_4 and 12C8^{12}C_8. Why are they equal?
  2. Find nn: nC2=66^nC_2 = 66; 2nC3:nC3=12:1^{2n}C_3 : {}^nC_3 = 12 : 1.
  3. How many chords can be drawn through 1515 points on a cir­cle? How many tri­an­gles with ver­tices among them?
  4. In how many ways can a team of 1111 be cho­sen from 1616 play­ers if 22 par­tic­u­lar play­ers must be included? If a par­tic­u­lar player is excluded?
  5. A bag holds 55 red and 66 white balls. In how many ways can 44 balls be drawn with 22 of each colour? With at least one red?
  6. How many diag­o­nals has a decagon?
  7. A com­mit­tee of 77 is cho­sen from 99 boys and 55 girls with at least 33 girls. How many ways?
  8. From the let­ters of EQUA­TION, how many 55-let­ter words use 33 vow­els and 22 con­so­nants?
  9. A per­son has 88 friends and invites 55 to din­ner. In how many ways, if two of the friends refuse to come together?
  10. Prove nCr+nCr−1=n+1Cr^nC_r + {}^nC_{r-1} = {}^{n+1}C_r alge­braically.

Answers

Show answers
  1. 495495 both, because choos­ing 44 to include is the same as choos­ing 88 to leave out.
  2. n=12n = 12; 2n(2n−1)(2n−2)n(n−1)(n−2)=12\displaystyle \tfrac{2n(2n - 1)(2n - 2)}{n(n - 1)(n - 2)} = 12 gives 4(2n−1)n−2=12\displaystyle \tfrac{4(2n - 1)}{n - 2} = 12, n=5n = 5.
  3. 105105; 455455.
  4. 14C9=2002^{14}C_9 = 2002; 15C11=1365^{15}C_{11} = 1365.
  5. 5C2 6C2=150^5C_2\,{}^6C_2 = 150; 11C4−6C4=330−15=315^{11}C_4 - {}^6C_4 = 330 - 15 = 315.
  6. 45−10=3545 - 10 = 35.
  7. 5C3 9C4+5C4 9C3+5C5 9C2=1260+420+36=1716^5C_3\,{}^9C_4 + {}^5C_4\,{}^9C_3 + {}^5C_5\,{}^9C_2 = 1260 + 420 + 36 = 1716.
  8. Vow­els E, U, A, I, O; con­so­nants Q, T, N: 5C3 3C2×5!=10×3×120=3600^5C_3\,{}^3C_2 \times 5! = 10 \times 3 \times 120 = 3600.
  9. 8C5−6C3=56−20=36^8C_5 - {}^6C_3 = 56 - 20 = 36.
  10. n!r!(n−r)!+n!(r−1)!(n−r+1)!=n! [(n−r+1)+r]r!(n−r+1)!=(n+1)!r!(n+1−r)!\displaystyle \tfrac{n!}{r!(n - r)!} + \tfrac{n!}{(r - 1)!(n - r + 1)!} = \tfrac{n!\,[(n - r + 1) + r]}{r!(n - r + 1)!} = \tfrac{(n + 1)!}{r!(n + 1 - r)!}.