Counting Selections

definitions
discrete-math
counting

Choosing \(r\) objects from a pool of \(n\) can be counted four ways, depending on two questions: does the order of the choices matter, and can the same object be chosen more than once? Each pair of answers has its own formula. This note collects the four, how to tell which one a problem needs, and the standard ways of handling a restriction: forcing part of the selection, splitting the pool into categories, and counting “at least” through the complement. It ends with arrangements of a word that has repeated letters, which are counted by choosing positions. The rules all of this is built from, the multiplication, addition and difference rules, and permutations, are in counting-principles. First met in 2026-10-13-counting-selections.

The two questions

A selection of \(r\) objects from \(n\) is a choice of \(r\) objects, made one after another, from a set of \(n\) distinct objects. Before counting, settle two things.

  • Ordered or unordered? In an ordered selection, the same objects chosen in a different order make a different selection: the password cat is not the password cta. In an unordered selection only which objects are chosen counts: the subset \(\{1, 2, 3\}\) is the subset \(\{3, 1, 2\}\). The test is to swap two of the chosen objects. If that changes the outcome, the selection is ordered.
  • With or without repeats? With repeats, an object that has been chosen can be chosen again, as a letter can appear twice in a password. Without repeats, each object is used at most once, as each runner finishes a race in one place only.
without repeats with repeats
ordered \(\dfrac{n!}{(n-r)!} = n(n-1)\cdots(n-r+1)\) \(n^r\)
unordered \(\dbinom{n}{r} = \dfrac{n!}{r!\,(n-r)!}\) \(\dbinom{n+r-1}{r}\) (extension)

Figure 1: How the four cases are related, with the count for \(n = 10\) and \(r = 3\) in each. Moving right allows an object to be chosen again, which adds the selections that use some object more than once: \(1000 - 720 = 280\) ordered ones and \(220 - 120 = 100\) unordered ones. Moving down forgets the order. Without repeats, each subset was counted once for each of its \(3! = 6\) orders, so the count divides by \(3!\). With repeats that fails, because a selection with a repeated object has fewer orders: 1, 1, 2 has only 3. There \(1000 \div 6\) is not even a whole number. The bottom-right case is extension material.

Ordered, without repeats

There are \(n\) choices for the first object and \(n - 1\) for the second, because the first cannot be used again. Each choice has one fewer option than the one before, and the \(r\)th has \(n - r + 1\). By the multiplication rule (counting-principles) the number of ordered selections without repeats is

\[n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}.\]

The product has exactly \(r\) factors. The fraction is the same number written another way: \(n! = n(n-1)\cdots 1\), and dividing by \((n-r)!\) cancels every factor from \(n - r\) down to 1, leaving the top \(r\). For example \(36 \cdot 35 \cdot 34 \cdot 33 = \frac{36!}{32!} = \frac{36!}{(36-4)!}\). These are the \(r\)-permutations of counting-principles, and with \(r = n\) they are the \(n!\) arrangements of all \(n\) objects.

Example. First, second and third place in a race of 10 people: \(10 \cdot 9 \cdot 8 = 720\).

Compute with the product, which never needs a large factorial. The fraction is the compact form for writing the answer down.

Ordered, with repeats

Every one of the \(r\) choices has all \(n\) objects available, so there are

\[n \cdot n \cdots n = n^r\]

ordered selections with repeats. Example. 3-digit passwords: \(10^3 = 1000\), the strings 000 to 999.

The base is the number of objects to choose from and the exponent is the number of choices made. An 8-letter password from a 26-letter alphabet has \(26^8\) possibilities, not \(8^{26}\).

Unordered, without repeats: \(n\) choose \(r\)

An unordered selection without repeats is a subset.

The number of \(r\)-element subsets of an \(n\)-element set is written \(\dbinom{n}{r}\), read “\(n\) choose \(r\)”, and also written \(C(n, r)\): \[\binom{n}{r} = \frac{n!}{r!\,(n-r)!} = \frac{n(n-1)\cdots(n-r+1)}{r(r-1)\cdots 1}.\]

Why divide by \(r!\). Count the ordered selections first: \(n(n-1)\cdots(n-r+1)\). Every \(r\)-element subset appears among them \(r!\) times, once for each order its \(r\) elements can be listed in. So the number of ordered selections is \(r!\) times the number of subsets. For 3 objects from \(\{1, 2, 3, 4\}\) there are \(4 \cdot 3 \cdot 2 = 24\) ordered selections, each subset accounts for \(3! = 6\) of them, and \(\binom43 = \frac{24}{6} = 4\). It is drawn in 2026-10-13-counting-selections.

How to calculate it. Use the second form: \(r\) factors counting down from \(n\) on top, \(r\) factors counting down from \(r\) underneath, and cancel before multiplying.

\[\binom{6}{3} = \frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20, \qquad \binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120, \qquad \binom{21}{7} = \frac{21 \cdot 20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 116\,280.\]

The answer is always a whole number, because it counts something. A fraction left over means a slip.

Three facts worth knowing.

  • \(\binom{n}{r} = \binom{n}{n-r}\). Choosing the \(r\) objects to take is the same as choosing the \(n - r\) to leave behind: each \(r\)-element subset pairs off with its complement, the \(n - r\) elements not in it. So \(\binom{10}{7} = \binom{10}{3} = 120\), and \(\binom{11}{7} = \binom{11}{4} = \frac{11 \cdot 10 \cdot 9 \cdot 8}{4 \cdot 3 \cdot 2 \cdot 1} = 330\). Use whichever has the smaller bottom number. The pairing is drawn in binomial-coefficients, along with the other identities binomial coefficients satisfy.
  • \(\binom{n}{n} = \binom{n}{0} = 1\), using \(0! = 1\). For instance \(\binom{2}{2} = \frac{2!}{2!\,0!} = 1\): there is one way to take everything.
  • \(\binom{n}{1} = n\).

Unordered, with repeats

Extension material: not assessable in MATH1061. It is Section 9.6 of Epp, and it is covered in MATH2302.

The number of unordered selections of \(r\) objects from \(n\) with repeats allowed is

\[\binom{n+r-1}{r} = \frac{n(n+1)\cdots(n+r-1)}{r(r-1)\cdots 1}.\]

The top now counts up from \(n\), still for \(r\) factors.

Why: stars and bars. Choose 7 candies from 4 colours, red, blue, yellow and pink, where candies of the same colour are identical and a colour can be taken any number of times, including not at all. A selection is settled by how many of each colour are taken. Write an X for each candy, colour by colour, with a bar \(|\) between one colour and the next. Four colours need three bars. Two red, one blue, four yellow and no pink is

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

Every string of 7 X’s and 3 bars describes exactly one selection, and every selection gives exactly one such string. So the selections can be counted as strings: 10 positions, of which 3 are bars, and \(\binom{10}{3} = 120\) ways to choose them. In general there are \(r\) X’s and \(n - 1\) bars, \(n + r - 1\) positions in all, and the selection is fixed by which \(r\) of them hold X’s.

Figure 2: Choosing 7 candies from 4 colours, written as strings of 7 X’s and 3 bars. The bars cut the string into four stretches, and the stretches, from left to right, are the red, blue, yellow and pink candies. Top: two red, one blue, four yellow and no pink, so the last stretch is empty. Bottom: two red, two blue, one yellow and two pink. A selection is decided by which 3 of the 10 positions hold the bars, so there are \(\binom{10}{3} = 120\) selections.

Example. Choosing 3 chocolate bars when there are 10 kinds: 3 X’s and 9 bars, so

\[\binom{12}{3} = \frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = \frac{10 \cdot 11 \cdot 12}{3 \cdot 2 \cdot 1} = 220.\]

Why not \(n^r / r!\)? Dividing by \(r!\) works only when every selection has \(r!\) different orderings, and a selection with a repeat has fewer: \(\{1, 1\}\) has one ordering, not two. For 2 objects from \(\{1, 2, 3, 4\}\), \(4^2 / 2! = 8\), but the true count is \(\binom{5}{2} = 10\).

Which case?

The same \(n = 10\), \(r = 3\) in four questions, one for each case:

Question Ordered? Repeats? Count
First, second and third in a race of 10 people yes no \(10 \cdot 9 \cdot 8 = 720\)
3-digit passwords yes yes \(10^3 = 1000\)
3-element subsets of \(\{1, 2, \dots, 10\}\) no no \(\binom{10}{3} = 120\)
3 chocolate bars from 10 kinds no yes \(\binom{12}{3} = 220\)

Wording that usually settles it:

  • Subset, committee, hand of cards, “choose 5 of the 11 questions”: unordered, without repeats.
  • Password, string, number plate, sequence of digits: ordered, and with repeats unless the problem rules them out.
  • First, second and third, or “arrange”: ordered, without repeats.

When the wording is unclear, use the swap test from the two questions and ask whether anything stops an object being picked twice.

Restrictions

A restriction narrows down which selections count. Three moves handle most of them.

Force the restricted part, then fill in the rest. Decide the restricted part first and count the ways it can go, then count the ways to fill whatever is left, and multiply. Ordered selections of 4 from \(\{1, 2, \dots, 10\}\) in which 5 is immediately followed by 6: the block “5 then 6” starts in position 1, 2 or 3 (not 4, where the 6 would have no room), and the two free positions take two of the other 8 numbers in order, \(8 \cdot 7\) ways. So there are \(3 \cdot 8 \cdot 7 = 168\) (2026-10-13-counting-selections). Number plates with exactly one digit go the same way: a \(k\)-symbol plate has \(k\) places for the digit, 10 digits to put there, and 26 letters for each of the other \(k - 1\) places, \(k \cdot 10 \cdot 26^{k-1}\) in all.

Split the pool into categories and choose from each. 5-element subsets of \(\{1, 2, \dots, 11\}\) with 3 even numbers and 2 odd: there are 5 evens and 6 odds, and the two choices are independent, so

\[\binom{5}{3}\binom{6}{2} = 10 \cdot 15 = 150.\]

The binomials are multiplied because every choice of evens goes with every choice of odds.

Split into cases and add. When the count depends on a case, such as the length of a number plate, count each case on its own and add, by the addition rule (counting-principles). The cases must not overlap.

“At least”: count the complement

Counting “at least one” directly means adding up exactly one, exactly two, and so on. The opposite, “none”, is usually a single product. So

\[\#(\text{at least one}) = \#(\text{all}) - \#(\text{none}),\]

which is counting the complement, the difference rule of counting-principles.

How many … All The opposite At least one
8-letter passwords contain a vowel? \(26^8\) no vowel: \(21^8\) \(26^8 - 21^8 = 171\,004\,205\,215\)
integers from 0 to 9999 contain the digit 5? \(10^4\) no 5: \(9^4\) \(10^4 - 9^4 = 3439\)
number plates of 4, 5 or 6 symbols repeat a symbol? \(36^4 + 36^5 + 36^6\) no repeat: \(\frac{36!}{32!} + \frac{36!}{31!} + \frac{36!}{30!}\) \(789\,865\,128\)

At least two. Take away both “none” and “exactly one”. For 7-element subsets of \(\{1, 2, \dots, 21\}\) with at least two even numbers (10 evens, 11 odds):

\[\binom{21}{7} - \binom{11}{7} - \binom{11}{6}\binom{10}{1} = 116\,280 - 330 - 4620 = 111\,330.\]

“Exactly one even” is itself a categories count: one even from the 10, which is \(\binom{10}{1} = 10\) ways, and six odds from the 11.

Checking with a direct count. The long way gives the same answer and is a good check. Integers from 0 to 9999 with exactly \(k\) fives: choose the \(k\) places for the fives and fill the others from the 9 other digits, \(\binom4k 9^{4-k}\). Then

\[\binom41 9^3 + \binom42 9^2 + \binom43 9 + \binom44 = 2916 + 486 + 36 + 1 = 3439.\]

Fixing one doesn’t work. “Put a vowel in one of the 8 places, then anything anywhere else” gives \(8 \cdot 5 \cdot 26^7 = 321\,272\,407\,040\), which is more than the \(26^8 = 208\,827\,064\,576\) passwords there are. A password with two vowels is counted once for each vowel that could be “the” vowel.

Arrangements of a word with repeated letters

An arrangement uses every letter of the word exactly once, so a word of \(n\) different letters has \(n!\) arrangements. Repeated letters spoil this. Swapping the two B’s of BARBARA gives the same string, so \(7! = 5040\) counts every arrangement more than once.

Count by choosing positions. Place one kind of letter at a time. BARBARA has 7 positions.

  1. The two B’s go in 2 of the 7 positions: \(\binom72 = 21\) ways. This is a choice of positions, not an ordered selection, because the B’s are identical: once two positions are chosen it makes no difference which B goes in which.
  2. The three A’s go in 3 of the 5 positions left: \(\binom53 = 10\) ways.
  3. The two R’s fill the last 2 positions: \(\binom22 = 1\) way.

\[\binom72\binom53\binom22 = 21 \cdot 10 \cdot 1 = 210.\]

Figure 3: Building one arrangement of BARBARA by choosing positions. First the two B’s take 2 of the 7 positions, here 3 and 6, in one of \(\binom72 = 21\) ways. Then the three A’s take 3 of the 5 positions still free, here 1, 4 and 5, in one of \(\binom53 = 10\) ways. The two R’s must take the last two positions, so there is \(\binom22 = 1\) way. Positions already taken are greyed. The result is ARBAABR, one of \(21 \cdot 10 \cdot 1 = 210\) arrangements.

The general formula. Writing the binomials out as factorials, almost everything cancels:

\[\binom72\binom53\binom22 = \frac{7!}{2!\,5!} \cdot \frac{5!}{3!\,2!} \cdot \frac{2!}{2!\,0!} = \frac{7!}{2!\,3!\,2!} = \frac{5040}{24} = 210.\]

In general, a word of \(n\) letters made of \(k\) different letters, appearing \(n_1, n_2, \dots, n_k\) times (so \(n_1 + n_2 + \cdots + n_k = n\)), has

\[\frac{n!}{n_1!\,n_2!\cdots n_k!}\]

distinct arrangements. It also explains the division. Tag the copies so that every letter is different, \(\mathrm{B}_1\mathrm{A}_1\mathrm{R}_1\mathrm{B}_2\mathrm{A}_2\mathrm{R}_2\mathrm{A}_3\), and there are \(7!\) arrangements. Removing the tags merges \(2!\,3!\,2! = 24\) of them into one word, because the tags can be shuffled among the B’s, among the A’s and among the R’s without changing the word.

The order the letters are placed in doesn’t matter. Placing the A’s first gives \(\binom73\binom42\binom22 = 35 \cdot 6 \cdot 1 = 210\) again.

Example: BANANAS. Seven letters: one B, three A’s, two N’s and one S.

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

A letter that appears once contributes \(1! = 1\) and can be left out of the denominator.

Restrictions on arrangements use the same moves as before. Letters fixed at the ends are placed first, and the rest of the word is arranged in the positions between. Letters that must sit together are glued into a single tile, which is then arranged along with the other letters. The practice set’s INDOOROOPILLY and WOOLLOONGABBA questions use both moves, and “not next to each other” is counted as all arrangements minus those with the pair glued together.

Common mistakes

  • Ordering a subset. \(6 \cdot 5 \cdot 4 = 120\) is the number of ordered selections of 3 from 6. Each 3-element subset is counted \(3! = 6\) times in it, and the number of subsets is \(\binom63 = 20\).
  • Dividing by the wrong thing. The divisor for a subset is \(r!\), the number of orders of the \(r\) chosen objects. It is not \(r\), and not 2.
  • Swapping \(n\) and \(r\) in \(n^r\). The exponent is the number of choices made: \(26^8\) eight-letter passwords, not \(8^{26}\).
  • “Exactly one” without choosing which one. Exactly one even number in a 7-element subset of \(\{1, \dots, 21\}\) is \(\binom{11}{6}\binom{10}{1} = 4620\), not \(\binom{11}{6} = 462\). Leaving out the \(\binom{10}{1}\) gives \(115\,488\) for “at least two evens” in place of the correct \(111\,330\).
  • Counting “at least one” by fixing one. It counts selections with several of the wanted objects several times. The complement avoids this.
  • A position that cannot be used. A block of two inside four positions has 3 starting places, not 4.
  • Numbers of different lengths. To count the integers from 0 to 9999 digit by digit, write every one with four digits, so 7 is 0007. The added zeros never contain a 5, so the count is unchanged, and now every position has 10 choices.
  • Treating repeated letters as different. \(7!\) for BARBARA counts each word \(2!\,3!\,2! = 24\) times.
  • Using \(n^r / r!\) for unordered selections with repeats. It fails because a selection with a repeat has fewer than \(r!\) orderings.

See also