Lecture 30 — Counting Selections

lecture
discrete-math
counting

Selecting \(r\) objects from \(n\): the four cases that come from asking whether order matters and whether repeats are allowed, a formula for each, and counting problems where the selection is restricted. Pre-work: Video 038 (Counting Selections). The four cases and their formulas, the ways of handling restrictions, counting “at least” through the complement, and arrangements of words with repeated letters are all collected in counting-selections. The multiplication, addition and difference rules and the permutations they rest on are in counting-principles. The note starts by finishing the number-plate question from 2026-10-12-introduction-to-counting.

Goals

  1. Understand the different cases for selections of \(r\) objects from \(n\).
  2. Learn how to count selections in each case, and when restrictions are added.
  3. Gain confidence with solving counting problems.

Three questions to keep in mind:

  • How is \(n\) choose \(r\) calculated? The formulas, and why it divides by \(r!\).
  • How many distinct arrangements do the letters of BANANAS have? After BARBARA, which is the same kind of problem.
  • How many ways are there to choose 7 candies from 4 colours? The fourth case, which counts them as strings of X’s and bars.

Finishing the number plates

In a certain state, number plates consist of four, five or six symbols chosen from the 26 letters of the alphabet together with the ten digits \(0, 1, \dots, 9\).
(a) How many distinct number plates are possible if repetition of symbols is allowed?
(b) How many distinct number plates are possible if repetition of symbols is not allowed?
(c) How many distinct number plates contain at least one repeated symbol?
(d) How many distinct number plates contain exactly one digit?

The full working is in 2026-10-12-introduction-to-counting. In short: there are \(26 + 10 = 36\) symbols, a plate is an ordered selection of them, and each part is counted separately for 4, 5 and 6 symbols and then added.

Count Answer
(a) repeats allowed \(36^4 + 36^5 + 36^6\) \(2\,238\,928\,128\)
(b) no repeats \(36 \cdot 35 \cdot 34 \cdot 33 \;+\; 36 \cdot 35 \cdots 32 \;+\; 36 \cdot 35 \cdots 31\) \(1\,449\,063\,000\)
(c) at least one repeat (a) \(-\) (b) \(789\,865\,128\)
(d) exactly one digit \(4 \cdot 10 \cdot 26^3 + 5 \cdot 10 \cdot 26^4 + 6 \cdot 10 \cdot 26^5\) \(736\,434\,400\)

For (d), a \(k\)-symbol plate has \(k\) places the digit can go, 10 choices of digit, and 26 letters for each of the other \(k - 1\) places. For four symbols with the digit first that is \(10 \cdot 26 \cdot 26 \cdot 26 = 10 \cdot 26^3\), and the digit can be in any of the 4 places, so \(4 \cdot 10 \cdot 26^3 = 703\,040\). The five- and six-symbol plates add \(22\,848\,800\) and \(712\,882\,560\).

Two ideas from this question run through the rest of the note. The four-symbol term of (b) is

\[36 \cdot 35 \cdot 34 \cdot 33 = \frac{36!}{32!} = \frac{36!}{(36-4)!},\]

the first of the four formulas. And (c) counts “at least one” as everything minus “none”, which is how the vowel, the digit 5 and two evens questions are done.

Four ways to select

Selecting 2 numbers from \(\{1, 2, 3, 4\}\) gives four different answers, depending on two questions. Does the order matter, so that 12 and 21 are different selections? Can a number be chosen twice, as in 11? Write each selection as the two numbers in the order chosen.

The selections Count
(1) ordered, without repeats 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43 12
(2) ordered, with repeats the twelve above, and 11, 22, 33, 44 16
(3) unordered, without repeats 12, 13, 14, 23, 24, 34 6
(4) unordered, with repeats 11, 12, 13, 14, 22, 23, 24, 33, 34, 44 10

In the unordered cases each selection is written with its smaller number first, since 21 is the same selection as 12.

Figure 1: Every way of picking a first and a second number from \({1, 2, 3, 4}\) is a cell of a 4 by 4 grid, first number down the side and second along the top. Each case of selection keeps a different part of the grid. Ordered with repeats keeps all 16. Ordered without repeats drops the diagonal, the repeats 11, 22, 33, 44, leaving 12. Unordered selections keep one cell of each mirror pair, since 21 is the same selection as 12. Without repeats that is the 6 cells above the diagonal, half of the 12. With repeats the diagonal comes back, and there are \(6 + 4 = 10\).

Which case is which

Four questions, one for each case:

  • How many different possibilities are there for first, second and third in a race of 10 people? Ordered, since first and second are different prizes, and without repeats, since nobody finishes twice. Case (1).
  • How many 3-digit passwords are there? Ordered, since 123 and 321 are different passwords, and with repeats, since 112 is allowed. Case (2).
  • How many 3-element subsets of \(\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) are there? A set has no order and no repeated elements. Case (3).
  • How many ways are there to select 3 chocolate bars when there are 10 different kinds to choose from? The bars end up in one pile, so there is no order, but two bars of the same kind are allowed. Case (4).

All four select \(r = 3\) from \(n = 10\). Their answers, 720, 1000, 120 and 220, come from the formulas below.

The formulas

With \(n = 10\) and \(r = 3\) in the right-hand column:

Case Formula Selecting 3 from 10
(1) ordered, without repeats \(\dfrac{n!}{(n-r)!} = \underbrace{n(n-1)\cdots(n-r+1)}_{r \text{ factors}}\) \(10 \cdot 9 \cdot 8 = 720\)
(2) ordered, with repeats \(n^r = \underbrace{n \cdot n \cdots n}_{r \text{ factors}}\) \(10^3 = 10 \cdot 10 \cdot 10 = 1000\)
(3) unordered, without repeats \(\dbinom{n}{r} = \dfrac{n!}{r!\,(n-r)!} = \dfrac{n(n-1)\cdots(n-r+1)}{r(r-1)\cdots 1}\) \(\dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120\)
(4) unordered, with repeats \(\dbinom{n+r-1}{r} = \dfrac{n(n+1)\cdots(n+r-1)}{r(r-1)\cdots 1}\) \(\dfrac{10 \cdot 11 \cdot 12}{3 \cdot 2 \cdot 1} = 220\)

Case (1) is the multiplication rule with one fewer option at each step. Case (2) is the multiplication rule with all \(n\) options every time. Each formula is explained in counting-selections.

Case (4) is extension material. It is not assessable in MATH1061. It is Section 9.6 of Epp, and it is covered in MATH2302.

Calculating \(n\) choose \(r\). \(\binom{n}{r}\) is read “\(n\) choose \(r\)” and also written \(C(n, r)\). It is the number of \(r\)-element subsets of an \(n\)-element set. To work it out, write \(r\) factors counting down from \(n\) over \(r\) factors counting down from \(r\), and cancel:

\[\binom{10}{3} = \frac{10!}{3!\,7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = \frac{720}{6} = 120.\]

The \(7!\) in \(10!\) cancels against the \(7!\) underneath, which is why only three factors are left on top. Case (4) is the same except that the top counts up from \(n\).

Worked: choosing candies

How many ways are there to choose 7 candies when there are 4 colours, red, blue, yellow and pink, any colour can be taken any number of times, and candies of the same colour are identical?

The candies are not ordered and colours can repeat, so this is case (4), with \(n = 4\) colours and \(r = 7\) candies.

A selection is settled by how many of each colour are taken. Write an X for each candy, the red ones first, then blue, yellow and pink, and put a bar \(|\) between one colour and the next. Two red, one blue, four yellow and no pink is

\[\mathrm{XX}\,|\,\mathrm{X}\,|\,\mathrm{XXXX}\,|\]

and two red, two blue, one yellow and two pink is

\[\mathrm{XX}\,|\,\mathrm{XX}\,|\,\mathrm{X}\,|\,\mathrm{XX}.\]

Each selection corresponds to an arrangement of 7 X’s and 3 bars, and each such arrangement is one selection. An arrangement is fixed by choosing which 3 of the 10 positions hold the bars, so there are

\[\binom{10}{3} = \frac{10!}{3!\,7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120\]

selections. The formula agrees: \(\binom{n+r-1}{r} = \binom{4+7-1}{7} = \binom{10}{7} = \binom{10}{3} = 120\). The two selections are drawn in counting-selections.

Ordered and unordered: dividing by \(r!\)

Cases (1) and (3) are linked. Take the selections of 3 objects from \(\{1, 2, 3, 4\}\) without repeats.

Ordered, there are \(4 \cdot 3 \cdot 2 = 24\):

123 124 134 234
132 142 143 243
213 214 314 324
231 241 341 342
312 412 413 423
321 421 431 432

Unordered, there are 4: 123, 124, 134, 234.

Each column of the table holds the same three numbers in all \(3 \cdot 2 \cdot 1 = 3! = 6\) possible orders, and forgetting the order collapses the whole column to one subset. So

\[\binom43 = \frac{24}{3!} = \frac{4 \cdot 3 \cdot 2}{3 \cdot 2 \cdot 1} = 4.\]

Figure 2: The 24 ordered selections of 3 objects from \({1, 2, 3, 4}\), sorted by which three numbers they use. Each column holds one set of three numbers in all \(3! = 6\) of its orders. Ignoring order merges each column into a single subset, so there are \(24 \div 3! = 4\) subsets. In general each \(r\)-element subset accounts for \(r!\) of the ordered selections, which is why \(\binom{n}{r}\) is the ordered count divided by \(r!\).

The same thing happens for any \(n\) and \(r\). Every \(r\)-element subset turns up \(r!\) times among the ordered selections, once in each order, so

\[\binom{n}{r} = \frac{1}{r!} \cdot \frac{n!}{(n-r)!} = \frac{n!}{r!\,(n-r)!}.\]

Worked: 8-letter passwords

A certain website requires users to choose a password consisting of 8 lower-case letters of the 26-letter alphabet \(a, b, c, d, \dots, x, y, z\). How many different passwords are there?
A. \(26!\)
B. \(8!\)
C. \(26 \times 25 \times 24 \times 23 \times 22 \times 21 \times 20 \times 19\)
D. \(8^{26}\)
E. \(26^8\)

Answer: E, \(26^8 = 208\,827\,064\,576\).

A password is ordered: cat and cta are different passwords. And it allows repeats: nothing stops a letter being used twice. So it is case (2) with \(n = 26\) letters and \(r = 8\) positions, and each of the 8 positions has 26 choices.

The other options:

  • A, \(26!\), counts the ways to put all 26 letters in a row, each used once.
  • B, \(8!\), counts the orders of 8 letters already chosen.
  • C, \(26 \cdot 25 \cdots 19\), counts 8-letter passwords with no letter repeated, which is case (1).
  • D, \(8^{26}\), has \(n\) and \(r\) the wrong way round. It would count 26 positions with 8 choices each.

Worked: passwords with a vowel

How many of the passwords from the question above contain a vowel? (There are 5 vowels: \(a, e, i, o, u\).)

“Contain a vowel” means at least one vowel. It could be 1, 2, 3, up to 8 vowels. Counting those cases one by one is long. Their opposite, no vowel at all, is one product: each of the 8 positions is one of the \(26 - 5 = 21\) consonants.

\[\#(\text{passwords with no vowel}) = 21^8.\]

Every password either contains a vowel or does not, so

\[\begin{aligned} \#(\text{passwords with at least one vowel}) &= \#(\text{all passwords}) - \#(\text{passwords with no vowel}) \\ &= 26^8 - 21^8 \\ &= 208\,827\,064\,576 - 37\,822\,859\,361 \\ &= 171\,004\,205\,215. \end{aligned}\]

Worked: integers containing a 5

How many of the integers from 0 to 9999 contain the digit 5?

Make every number four digits long by writing leading zeros: 0 is 0000, 1 is 0001, 42 is 0042. The added zeros never contain a 5, so this does not change which numbers contain a 5. Now the integers from 0 to 9999 are exactly the strings of 4 digits, and each of the 4 positions has 10 choices:

\[\#(\text{integers from 0 to 9999}) = 10 \cdot 10 \cdot 10 \cdot 10 = 10^4.\]

A number with no 5 has 9 choices in each position, \(\{0, 1, 2, 3, 4, 6, 7, 8, 9\}\):

\[\#(\text{those with no 5}) = 9^4 = 6561.\]

So

\[\#(\text{those containing at least one 5}) = 10^4 - 9^4 = 10\,000 - 6561 = 3439.\]

The long way, as a check. Count by the exact number of 5s and add. For exactly \(k\) fives, choose which \(k\) of the 4 positions hold them, \(\binom4k\) ways, and fill each of the others with one of the 9 other digits:

\[\begin{aligned} &\#(\text{one 5}) + \#(\text{two 5s}) + \#(\text{three 5s}) + \#(\text{four 5s}) \\ &\quad= \binom41 9^3 + \binom42 9^2 + \binom43 9 + \binom44 \\ &\quad= 2916 + 486 + 36 + 1 = 3439. \end{aligned}\]

Same answer, four terms instead of two.

Worked: 5 immediately followed by 6

  1. How many ordered selections without repetition of 4 elements are there from the set \(\{1, 2, \dots, 10\}\)?
  2. How many ordered selections without repetition of 4 elements from the set \(\{1, 2, \dots, 10\}\) have 5 immediately followed by 6?

(a) Case (1) with \(n = 10\) and \(r = 4\):

\[\frac{n!}{(n-r)!} = \frac{10!}{(10-4)!} = 10 \cdot 9 \cdot 8 \cdot 7 = 5040.\]

Four positions, with 10, 9, 8 and 7 numbers left for them in turn.

(b) Place the restricted part first. “5 immediately followed by 6” is a block of two neighbouring positions, 5 then 6. In 4 positions the block can start at position 1, 2 or 3. It cannot start at position 4, because the 6 would have nowhere to go. Wherever the block is, the two positions it leaves are filled, in order, from the 8 numbers other than 5 and 6: 8 choices for the first and 7 for the second.

\[\#(\text{choices}) = 3\,(1 \cdot 1 \cdot 8 \cdot 7) = 3 \cdot 8 \cdot 7 = 21 \cdot 8 = 168.\]

The 1s are the positions of 5 and 6, which have no choice once the block is placed.

Figure 3: The ordered selections of 4 from \({1, \dots, 10}\) with 5 immediately followed by 6, counted one position at a time. Each box holds the number of choices for its position. The block 5 then 6, shaded, takes two neighbouring positions, and once it is placed those positions have 1 choice each; the value forced into each is written above it. The block fits in three places. Wherever it goes, the two positions left over take two of the other 8 numbers in order, 8 choices and then 7. A fourth placement would put the 5 last, leaving no room for the 6. So there are \(3,(1 \cdot 1 \cdot 8 \cdot 7) = 168\) selections.

Worked: 3-element subsets of a 6-element set

How many 3-element subsets of \(\{1, 2, 3, 4, 5, 6\}\) are there?
A. 18
B. 20
C. 60
D. 120

Answer: B, 20.

A subset is unordered and has no repeated elements, so this is case (3):

\[\binom63 = \frac{6!}{3!\,3!} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20.\]

The other options:

  • D, 120, is \(6 \cdot 5 \cdot 4\), the number of ordered selections. Each subset is counted \(3! = 6\) times in it.
  • C, 60, is \(120 \div 2\). It divides by 2 where it should divide by \(3! = 6\).
  • A, 18, is \(6 \cdot 3\), which doesn’t count any kind of selection.

Worked: three even and two odd

How many 5-element subsets of \(\{1, 2, \dots, 11\}\) contain 3 even numbers and 2 odd numbers?

Split the set into its evens and its odds:

\[E = \{2, 4, 6, 8, 10\},\ |E| = 5, \qquad O = \{1, 3, 5, 7, 9, 11\},\ |O| = 6.\]

A subset of the required kind is a choice of 3 elements of \(E\) together with a choice of 2 elements of \(O\). The two choices are independent, and every pair of them gives a different subset, so by the multiplication rule

\[\begin{aligned} \#(\text{subsets}) &= \#(\text{ways to choose 3 evens}) \cdot \#(\text{ways to choose 2 odds}) \\ &= \binom53 \binom62 = \frac{5!}{3!\,2!} \cdot \frac{6!}{2!\,4!} = \frac{5 \cdot 4}{2} \cdot \frac{6 \cdot 5}{2} = 10 \cdot 15 = 150. \end{aligned}\]

Figure 4: The 5-element subsets of \({1, \dots, 11}\) with 3 even and 2 odd numbers. The set splits into its evens \(E\) and its odds \(O\), and a subset of this kind is 3 elements taken from \(E\) together with 2 taken from \(O\). One of them, \({2, 3, 6, 7, 10}\), is shaded. The two choices are made separately, and whichever 3 evens are taken, any 2 odds can go with them, so the numbers of ways multiply: \(\binom53 \binom62 = 10 \cdot 15 = 150\).

Worked: at least two even numbers

How many 7-element subsets of \(\{1, 2, \dots, 21\}\) contain at least two even numbers?

Let \(N = \{1, 2, \dots, 21\}\), so \(|N| = 21\). Its evens are \(E = \{2, 4, \dots, 20\}\) with \(|E| = 10\), and its odds are \(O = \{1, 3, \dots, 21\}\) with \(|O| = 11\).

“At least two” could be 2, 3, 4, 5, 6 or 7 evens. Its opposite is “no evens” or “exactly one even”, two cases instead of six. So

\[\#(\text{at least 2 evens}) = \#(\text{all}) - \#(\text{no evens}) - \#(\text{exactly 1 even}).\]

  • All. Any 7 of the 21 numbers: \(\binom{21}{7} = 116\,280\).
  • No evens. All 7 come from the 11 odds: \(\binom{11}{7} = \binom{11}{4} = 330\).
  • Exactly one even. Choose the one even from 10 and the other six numbers from the 11 odds: \(\binom{10}{1}\binom{11}{6} = 10 \cdot 462 = 4620\).

Therefore

\[\begin{aligned} \#(\text{subsets with at least 2 evens}) &= \binom{21}{7} - \binom{11}{7} - \binom{11}{6}\binom{10}{1} \\ &= \frac{21!}{14!\,7!} - \frac{11!}{7!\,4!} - \frac{11!}{6!\,5!} \cdot 10 \\ &= 116\,280 - 330 - 4620 \\ &= 111\,330. \end{aligned}\]

The factor of 10 is easy to drop. Without it the answer comes out at \(115\,488\), which is wrong: there are 10 different evens that could be the one even. A direct count over 2 to 7 evens, \(\sum_{k=2}^{7} \binom{10}{k}\binom{11}{7-k}\), gives \(20\,790 + 39\,600 + 34\,650 + 13\,860 + 2310 + 120 = 111\,330\), the same answer.

Figure 5: The 7-element subsets of \({1, \dots, 21}\), split by how many even numbers they contain. Every subset has none, exactly one, or at least two, and no subset is in two of these parts. So the count wanted, shaded, is the total minus the other two parts. Exactly one even is a choice of the even, 10 ways, times a choice of six odds. The widths are not to scale.

Worked: arranging BARBARA

How many distinct arrangements of the letters in the word BARBARA are there?

The letters are B, A and R: two B’s, three A’s and two R’s, 7 letters in all. An arrangement puts one letter in each of 7 positions. It is ordered, since ARBAABR and BARBARA are different words, and it has no repeats, since each position gets exactly one letter. If the 7 letters were all different that would make \(7!\) arrangements. They are not, so count it instead by choosing positions for one kind of letter at a time.

  • Place the two B’s: choose 2 of the 7 positions, \(\binom72\) ways. It is a choice, not an ordered selection: once the positions are chosen, the two B’s look identical, so it doesn’t matter which B goes in which of the chosen positions.
  • Place the three A’s: choose 3 of the 5 positions left, \(\binom53\) ways.
  • Place the two R’s: they go in the 2 positions left, \(\binom22 = \frac{2!}{2!} = 1\) way.

For example, B’s in positions 3 and 6, A’s in 1, 4 and 5, and R’s in 2 and 7 give ARBAABR. By the multiplication rule,

\[\begin{aligned} \#(\text{arrangements}) &= \binom72 \binom53 \binom22 = \frac{7!}{2!\,5!} \cdot \frac{5!}{3!\,2!} \cdot \frac{2!}{2!} \\ &= \frac{7 \cdot 6}{2} \cdot \frac{5 \cdot 4}{2} \cdot 1 = 7 \cdot 6 \cdot 5 = 210. \end{aligned}\]

The \(5!\)s cancel, leaving \(\frac{7!}{2!\,3!\,2!}\): the factorial of the length over the factorial of the number of copies of each letter. The stages are drawn, and the general formula derived, in counting-selections. The same formula comes out a second way, by tagging the copies so that all seven letters differ and dividing out the orders of the copies, in 2026-10-19-probability-binomial-coefficients.

Worked: arranging BANANAS

How many distinct arrangements of the letters in the word BANANAS are there?

BANANAS has 7 letters: one B, three A’s, two N’s and one S. Choosing positions as for BARBARA:

\[\binom71\binom63\binom32\binom11 = 7 \cdot 20 \cdot 3 \cdot 1 = 420,\]

placing the B, then the A’s, then the N’s, then the S. The factorial form gives the same:

\[\frac{7!}{1!\,3!\,2!\,1!} = \frac{5040}{6 \cdot 2} = 420.\]

See also