Unit 3 — Counting
Unit 3 · Volume 2

Counting (Combinatorics)

Systematic ways to count outcomes: the addition and multiplication principles, arrangements, permutations, and combinations.

Recall
  • Factorial: \(n! = n\cdot(n-1)\cdots 2\cdot 1\), with \(0! = 1\).
  • A set is unordered; a sequence/tuple is ordered.

3.1 General principles of counting

Addition principle

If a task can be done in one of two mutually exclusive ways — \(m\) ways or \(n\) ways — then there are \(m + n\) possibilities. (Use it for "OR".)

Multiplication principle

If a task consists of successive stages with \(m\) choices for the first and \(n\) for the second, then there are \(m \times n\) total outcomes. (Use it for "AND"/"then".)

Worked example

A menu has 3 starters and 4 mains. A meal (one starter and one main) can be chosen in \(3 \times 4 = 12\) ways. If instead you may pick either a starter or a main as a single dish, that is \(3 + 4 = 7\) ways.

3.2 Arrangements (ordered selections)

Arrangements with repetition

Ordered selections of \(k\) items from \(n\), where repetition is allowed:

\[ n'^{k} = n^{k}. \]
Arrangements without repetition (simple arrangements)

Ordered selections of \(k\) distinct items from \(n\):

\[ {}^{n}A_{k} = \frac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1). \]
Worked example

How many 3-letter "codes" from \(\{A,B,C,D,E\}\)?

  • With repetition: \(5^3 = 125\).
  • Without repetition: \({}^{5}A_{3} = \dfrac{5!}{2!} = 60\).

3.3 Permutations

Definition

A permutation is an ordering of all \(n\) distinct objects. The number of permutations is

\[ P_n = n!. \]
Worked example

The number of ways to arrange 5 books on a shelf is \(5! = 120\).

3.4 Combinations (unordered selections)

Combinations

The number of ways to choose \(k\) items from \(n\) without regard to order:

\[ {}^{n}C_{k} = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}. \]
Arrangement vs. combination

Use arrangements when order matters (podium positions, passwords) and combinations when it does not (a committee, a hand of cards). Note \(\binom{n}{k} = \dfrac{{}^{n}A_{k}}{k!}\).

Worked example

From 10 students, choose a committee of 3: \(\binom{10}{3} = \dfrac{10!}{3!\,7!} = 120\) ways. If instead we choose a president, secretary, treasurer (ordered), that is \({}^{10}A_{3} = 720\).

Useful identities
\[ \binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}. \]

Practice problems

  1. How many 4-digit PINs are possible (digits 0–9, repetition allowed)?
    Show solution
    \(10^4 = 10000\).
  2. In how many ways can 6 people line up for a photo?
    Show solution
    \(6! = 720\).
  3. A lottery draws 6 numbers from 49 (order irrelevant). How many possible draws?
    Show solution
    \(\binom{49}{6} = 13\,983\,816\).
  4. From 7 men and 5 women, choose a team of 4 with exactly 2 women.
    Show solution
    Choose 2 women and 2 men: \(\binom{5}{2}\binom{7}{2} = 10\times 21 = 210\).

Summary

  • Addition principle for "OR"; multiplication principle for "AND/then".
  • Order matters → arrangements: \(n^k\) (with repetition), \({}^{n}A_k = \tfrac{n!}{(n-k)!}\) (without).
  • All \(n\) objects ordered → permutations \(P_n = n!\).
  • Order irrelevant → combinations \(\binom{n}{k} = \tfrac{n!}{k!(n-k)!}\).
Final test (quick check)
  1. Compute \(\binom{8}{2}\).
  2. How many ways to award gold/silver/bronze among 8 runners?
Show answers
(1) \(28\).   (2) \({}^{8}A_3 = 336\).