matura.mkSecondary school › Counting and probability
Combinations
Choosing groups, at least and at most, geometry, subsets and positive or non-negative solutions. 10 problems with step-by-step solutions.
Solve each problem in your notebook first, then open the solution.
Problem 1 Combinations
\(C(n, r) = \dbinom{n}{r} = \dfrac{n!}{r!\,(n - r)!}\).
a) Calculate \(C(9, 4)\), \(C(10, 3)\cdot C(6, 2)\), \(C(20, 18)\).
b) \(C(n, 4) = C(n, 6)\). Find \(n\) and \(C(n, 8)\).
c) \(P(n, 3) = 12\cdot C(n, 2)\). Find \(n\).
Show solution
a) \(126\); \(120\cdot 15 = 1800\); \(C(20, 2) = 190\).
b) \(C(n, r) = C(n, n - r)\), so \(n = 10\); \(C(10, 8) = 45\).
c) \(n(n - 1)(n - 2) = 6n(n - 1)\), \(n - 2 = 6\), \(n = 8\).
Problem 2 Choosing groups
a) How many groups of 4 pupils can be chosen from a class of 12?
b) A tray holds 9 different fruits, including a pear. How many selections of 3 fruits include the pear? How many do not?
c) A coach chooses 5 players from 12 and names one of them captain. In how many ways?
Show solution
a) \(C(12, 4) = 495\).
b) With the pear: \(C(8, 2) = 28\). Without: \(C(8, 3) = 56\).
c) \(C(12, 5)\cdot 5 = 792\cdot 5 = 3960\).
Problem 3 Splitting into groups
a) 10 children get presents: 5 get a book, 3 get a ball and 2 get a puzzle. In how many ways?
b) In how many ways can 8 people be split into two groups of 4 if one group goes to Ohrid and the other to Bitola? And if the two groups just play a game against each other?
c) In how many ways can 12 different toys be given to 3 children so that each gets 4?
Show solution
a) \(C(10, 5)\cdot C(5, 3) = 252\cdot 10 = 2520\).
b) \(C(8, 4) = 70\) (the groups are labelled). Unlabelled: \(\frac{70}{2} = 35\).
c) \(C(12, 4)\cdot C(8, 4) = 495\cdot 70 = 34\,650\).
Problem 4 At least / at most
a) A box has 6 good and 4 broken bulbs. We take 3. In how many ways if none is broken? If at least 2 are broken?
b) A crew of 4 is chosen from 6 women and 5 men. How many crews have at least one man?
c) A box holds 6 red and 4 green cards. How many groups of 5 cards contain at least 3 red cards?
Show solution
a) None broken: \(C(6, 3) = 20\). At least 2 broken: \(C(4, 2)C(6, 1) + C(4, 3) = 36 + 4 = 40\).
b) All: \(C(11, 4) = 330\). Only women: \(C(6, 4) = 15\). Answer \(315\).
c) \(C(6, 3)C(4, 2) + C(6, 4)C(4, 1) + C(6, 5) = 120 + 60 + 6 = 186\).
Problem 5 Geometry and handshakes
a) How many diagonals does a convex polygon with 12 sides have? Derive the formula for \(n\) sides.
b) 15 people shake hands with each other once. How many handshakes?
c) 10 points lie on a circle. How many triangles and how many quadrilaterals have their vertices among these points?
d) 8 points are given; exactly 4 of them lie on one line and no other 3 are collinear. How many lines pass through at least two of them? How many triangles?
Show solution
a) Segments between vertices: \(C(n, 2)\); minus the \(n\) sides: \(\frac{n(n - 3)}{2}\). For 12 sides: \(54\).
b) \(C(15, 2) = 105\).
c) \(C(10, 3) = 120\) triangles, \(C(10, 4) = 210\) quadrilaterals.
d) Lines: \(C(8, 2) - C(4, 2) + 1 = 28 - 6 + 1 = 23\). Triangles: \(C(8, 3) - C(4, 3) = 56 - 4 = 52\).
Problem 6 Ice cream and sauces
a) A shop has 5 flavours. A cone has 1, 2 or 3 different flavours. How many different cones are possible?
b) How many three-digit numbers \(\overline{abc}\) satisfy \(a > b > c\)?
c) How many subsets does \(\{a, b, c, d, e, f\}\) have? How many have at least 2 elements?
d) How many subsets of \(\{1, 2, \dots, 8\}\) contain 3 or 5 (or both)?
Show solution
a) \(C(5, 1) + C(5, 2) + C(5, 3) = 5 + 10 + 10 = 25\).
b) Choose 3 different digits from 0–9; they can be ordered in only one decreasing way (and the first digit is then not 0): \(C(10, 3) = 120\).
c) \(2^6 = 64\); without the empty set and the 6 one-element sets: \(57\).
d) All: \(2^8 = 256\); without 3 and without 5: \(2^6 = 64\). Answer \(192\).
Problem 7 Votes
A board has 3 permanent and 8 elected members. A decision passes with at least 7 votes in favour, and all permanent members must vote in favour. In how many ways can a decision pass (everyone votes)?
Show solution
The 3 permanent members vote yes; we need at least 4 yes votes among the 8 elected: \(\sum_{k=4}^{8} C(8, k) = 70 + 56 + 28 + 8 + 1 = 163\).
Problem 8 Pascal's rule
a) Prove \(\dbinom{n}{r} = \dbinom{n - 1}{r - 1} + \dbinom{n - 1}{r}\).
b) The number of 4-element subsets of a set equals the number of 7-element subsets. Find the number of 9-element subsets.
Show solution
a) \(\frac{(n - 1)!}{(r - 1)!(n - r)!} + \frac{(n - 1)!}{r!(n - r - 1)!} = \frac{(n - 1)!}{r!(n - r)!}(r + (n - r)) = \frac{n!}{r!(n - r)!}\).
b) \(n = 11\); \(C(11, 9) = 55\).
Problem 9 Positive and non-negative solutions
The number of positive integer solutions of \(x_1 + \dots + x_r = n\) is \(\binom{n - 1}{r - 1}\); of non-negative solutions it is \(\binom{n + r - 1}{r - 1}\).
a) How many positive integer solutions does \(a + b + c + d = 12\) have?
b) In how many ways can 20 identical sweets be shared among 5 children so that each gets at least one?
c) How many non-negative solutions does \(x + y + z + w = 10\) have?
d) How many integer solutions does \(x + y + z = 40\) have with \(x \ge 5\), \(y \ge 8\), \(z \ge 2\)?
Show solution
a) \(\binom{11}{3} = 165\).
b) \(\binom{19}{4} = 3876\).
c) \(\binom{13}{3} = 286\).
d) Put \(x = x' + 5\), \(y = y' + 8\), \(z = z' + 2\): \(x' + y' + z' = 25\), non-negative: \(\binom{27}{2} = 351\).
Problem 10 Distributions
a) 10 identical letters go into 4 mailboxes (some may stay empty). In how many ways?
b) A shop has 12 flavours. How many different servings of 3 scoops (flavours may repeat, order does not matter)?
c) 9 people ride a bus with 5 stops left. The driver writes how many people get off at each stop. How many different lists?
Show solution
a) \(\binom{13}{3} = 286\).
b) \(\binom{14}{3} = 364\).
c) \(\binom{13}{4} = 715\).