Mathematical Statistics

Tools for Counting Sample Points: the mn Rule, Permutations, Combinations and Partitions

Samir Orujov, PhD

ADA University, School of Business

Information Communication Technologies Agency, Statistics Unit

2026-09-13

🎯 Learning Objectives

By the end of this lecture, you will be able to:

  • Apply the \(mn\) rule, and its extension, to count the sample points of a multi-stage experiment

  • Distinguish an ordered selection from an unordered one, and choose \(P^n_r\) or \(\binom{n}{r}\) accordingly

  • Compute the number of partitions of \(n\) objects into \(k\) groups of stated sizes

  • Derive \(\binom{n}{r} = P^n_r / r!\), and explain why the division by \(r!\) is there

  • Calculate \(P(A) = n_a / N\) for an equiprobable sample space without listing a single point

🗺️ Where We Are

Wackerly §2.6

Last time: the sample-point method. Describe, list, assign, collect, sum.

Step 2 is the one that breaks. Five loan files gave ten pairs, which we listed on one slide. Thirty bidders taken three at a time gives 24,360 — and no slide.

Today we replace listing with counting. Four theorems, and one identity that makes them worth having.

💡 The Identity That Does the Work

Equiprobable sample points

If \(S\) contains \(N\) equiprobable sample points and \(A\) contains exactly \(n_a\) of them, then \[P(A) = \frac{n_a}{N}\]

This follows from Axiom 3 alone: sum \(1/N\) over the \(n_a\) points of \(A\).

So the whole probability problem collapses into two counting problems — and we never write down a sample point.

📐 Theorem 2.1: The \(mn\) Rule

Theorem 2.1

With \(m\) elements \(a_1, \ldots, a_m\) and \(n\) elements \(b_1, \ldots, b_n\), it is possible to form \[mn = m \times n\] pairs containing one element from each group.

The proof is a rectangle: \(m\) rows, \(n\) columns, one square per pair.

⛓️ The Extension

Three groups of sizes \(m\), \(n\), \(p\) give \(mnp\) triples — apply Theorem 2.1 twice, treating each \((a_i, b_j)\) pair as a single object.

And so on for any number of stages. If a sample point is built by making \(k\) choices in sequence, multiply the number of options at each stage.

A retail deposit product is specified by 5 maturities, 4 interest-payment frequencies, 2 currencies and 3 early-withdrawal terms: \[5 \times 4 \times 2 \times 3 = 120 \text{ distinct products}\]

📊 Worked Example: Two Rating Agencies

Two agencies each rate a bond on a six-grade scale. A sample point is the ordered pair (first agency’s grade, second agency’s grade).

The first grade can be one of six; so can the second. By Theorem 2.1, \[N = 6 \times 6 = 36\]

Small enough to list, which is exactly why it is worth counting: the rule is verified here, so it can be trusted where listing is impossible.

🔢 Definition 2.7: Permutations

Definition 2.7

An ordered arrangement of \(r\) distinct objects is a permutation. The number of ways of ordering \(n\) distinct objects taken \(r\) at a time is \(P^n_r\).

“Ordered” is the whole content of the definition. \(M_1 G_2\) and \(G_2 M_1\) are two permutations and one subset.

📐 Theorem 2.2

Theorem 2.2

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

Straight from the \(mn\) rule: \(n\) ways to fill the first position, then \(n-1\), then \(n-2\), down to \(n-r+1\) for the last.

🏆 Worked Example: Three Unequal Bonuses

Three names are drawn without replacement from 30 analysts. The first drawn receives 100 manat, the second 50, the third 25.

The prizes differ, so order matters: the sample point is an ordered triple of names. \[P^{30}_3 = \frac{30!}{27!} = 30 \times 29 \times 28 = 24{,}360\]

Make the three bonuses equal and the same draw has only \(\binom{30}{3} = 4{,}060\) outcomes. The prize structure changes the sample space.

🔁 When \(r = n\)

An audit has four stages that may be performed in any sequence. How many sequences?

\[P^4_4 = \frac{4!}{(4-4)!} = \frac{4!}{0!} = 24\]

Recall the convention \(0! = 1\). It is not arbitrary: it is what makes Theorem 2.2 return \(n!\) when every object is used.

🧩 Theorem 2.3: Partitions

Theorem 2.3

The number of ways of partitioning \(n\) distinct objects into \(k\) distinct groups of sizes \(n_1, \ldots, n_k\), with \(\sum_i n_i = n\), is \[N = \binom{n}{n_1\; n_2\; \cdots\; n_k} = \frac{n!}{n_1!\, n_2! \cdots n_k!}\]

The proof divides out what we do not want: \(n!\) orders all \(n\) objects, then we divide by \(n_i!\) for each group, because order inside a group does not count.

🏢 Worked Example: Staffing Four Desks

Twenty analysts are assigned at random to four desks needing 6, 4, 5 and 5 people.

\[N = \binom{20}{6\;4\;5\;5} = \frac{20!}{6!\,4!\,5!\,5!}\]

All four members of one small team end up on the least popular desk. Let \(A\) be that event. The remaining 16 fill the remaining places: \[n_a = \binom{16}{2\;4\;5\;5} = \frac{16!}{2!\,4!\,5!\,5!}\]

🏢 The Desks: Was It Random?

\[P(A) = \frac{n_a}{N} = 0.0031\]

Three chances in a thousand. The assignment was announced as random.

This is the gambler’s argument from Wednesday, now with a number attached: we do not conclude that random assignment was impossible, only that the observed outcome is very improbable under it — which is grounds to doubt the claim.

🎯 Definition 2.8: Combinations

Definition 2.8

The number of combinations of \(n\) objects taken \(r\) at a time is the number of subsets of size \(r\), written \(\binom{n}{r}\).

A subset has no internal order, which is the only difference from Definition 2.7 — and it is worth a factor of \(r!\).

📐 Theorem 2.4

Theorem 2.4

\[\binom{n}{r} = \frac{P^n_r}{r!} = \frac{n!}{r!\,(n-r)!}\]

A special case of Theorem 2.3 with \(k = 2\): the \(r\) chosen, and the \(n-r\) left behind.

➗ Why Divide by \(r!\)?

\(P^n_r\) counts ordered selections. Every subset of size \(r\) has been counted once for each of its \(r!\) orderings.

Draw files \(\{M_1, G_2\}\): the permutation count records \(M_1 G_2\) and \(G_2 M_1\) as two outcomes. The audit does not care which was picked up first.

Ask of every problem: would swapping two chosen objects give a different outcome? If yes, permutations. If no, combinations.

📋 Back to the Credit File Audit

Wednesday’s example: five loan files, two misclassified, two drawn. We listed all ten pairs. Now count them: \[N = \binom{5}{2} = \frac{5!}{2!\,3!} = 10\]

Let \(A\) be the event that exactly one of the two misclassified files is drawn. Choose one of the two bad files, and one of the three sound ones: \[n_a = \binom{2}{1}\binom{3}{1} = 2 \times 3 = 6\]

\[P(A) = \frac{6}{10} = 0.6\]

💻 Counting in R

Code 
files <- c("M1", "M2", "G1", "G2", "G3")
pairs <- combn(files, 2)
bad   <- colSums(matrix(startsWith(pairs, "M"), nrow = 2))

data.frame(
  formula     = c("choose(5,2)", "choose(2,1)*choose(3,1)", "P(exactly one bad)"),
  counted     = c(choose(5, 2), choose(2, 1) * choose(3, 1), 0.6),
  enumerated  = c(ncol(pairs), sum(bad == 1), mean(bad == 1))
)
                  formula counted enumerated
1             choose(5,2)    10.0       10.0
2 choose(2,1)*choose(3,1)     6.0        6.0
3      P(exactly one bad)     0.6        0.6

The formula and the enumeration agree. On five files either is fine; the formula is the one that still works on five hundred.

📅 A Problem Listing Cannot Touch

A bank holds 20 bonds, each maturing on one of 365 dates. A sample point is an ordered 20-tuple of dates, so \[N = 365^{20}\]

Let \(A\) be the event that no two mature on the same day. Fill the positions in turn: 365 choices, then 364, then 363, … \[n_a = 365 \times 364 \times \cdots \times 346\]

\[P(A) = \frac{365 \times 364 \times \cdots \times 346}{365^{20}} = 0.5886\]

💻 The Maturity Clash, Computed

Code 
p_all_distinct <- function(n, d = 365) prod((d - seq_len(n) + 1) / d)

data.frame(
  n_bonds      = c(10, 20, 23, 40),
  all_distinct = round(sapply(c(10, 20, 23, 40), p_all_distinct), 4),
  some_clash   = round(1 - sapply(c(10, 20, 23, 40), p_all_distinct), 4)
)
  n_bonds all_distinct some_clash
1      10       0.8831     0.1169
2      20       0.5886     0.4114
3      23       0.4927     0.5073
4      40       0.1088     0.8912

With 20 bonds a clash is already about as likely as not; with 23 it is the favourite. Nobody guesses this, which is the point of Wednesday’s motivation slide.

🔬 Interactive: How Fast the Clash Arrives

🧠 Think-Pair-Share

A fund must fill three roles from eight candidates.

Three minutes, in pairs:

  1. The three roles are Chief Analyst, Deputy and Trainee. How many outcomes?

  2. Instead, the three simply join an equal-standing committee. How many now?

  3. The second number is the first divided by what, and why exactly that?

✅ Think-Pair-Share: Solution

  1. Distinct roles, so the outcome is an ordered triple: \[P^8_3 = 8 \times 7 \times 6 = 336\]

  2. An equal-standing committee is a subset: \[\binom{8}{3} = \frac{8!}{3!\,5!} = 56\]

  1. \(336 / 56 = 6 = 3!\) — the number of ways to order any one committee of three. Each committee was counted \(3!\) times when the roles were distinct.

✅ Think-Pair-Share: The Habit

The arithmetic is easy; choosing between \(336\) and \(56\) is the whole question, and it is settled before any formula is written.

Test: name two of the chosen objects and swap them. If the outcome you are counting has changed, order matters.

Swap the Deputy and the Trainee: a different appointment. Swap two committee members: the same committee.

📝 Quiz #1: Which Rule?

A portfolio manager must pick 4 stocks out of 25 for an equally weighted basket. How many baskets are possible?

  • \(\binom{25}{4} = 12{,}650\)
  • \(P^{25}_4 = 303{,}600\)
  • \(25^4 = 390{,}625\)
  • \(4! \times 25 = 600\)

📝 Quiz #2: The \(mn\) Rule

A loan application passes three independent checks, with 4, 3 and 5 possible outcomes respectively. How many outcome sequences are there?

  • \(4 \times 3 \times 5 = 60\)
  • \(4 + 3 + 5 = 12\)
  • \(\binom{12}{3} = 220\)
  • \(12! / 3! = 79{,}833{,}600\)

📝 Quiz #3: Partitions

Nine auditors are split into three named teams of 3, 3 and 3. How many splits are there?

  • \(\dfrac{9!}{3!\,3!\,3!} = 1680\)
  • \(\binom{9}{3} = 84\)
  • \(9! = 362{,}880\)
  • \(3^9 = 19{,}683\)

📝 Quiz #4: Order or Not?

In which of these does order matter?

  • Awarding a gold, a silver and a bronze prize among six competing desks
  • Choosing three desks to audit this quarter
  • Choosing a two-stock hedge from a list of twenty
  • Selecting five files from a drawer for review

📋 Key Formulas

Counts Formula
\(mn\) rule sequences of choices \(m \times n \times p \cdots\)
\(P^n_r\) ordered selections \(\dfrac{n!}{(n-r)!}\)
\(\binom{n}{r}\) subsets \(\dfrac{n!}{r!\,(n-r)!}\)
\(\binom{n}{n_1 \cdots n_k}\) partitions into named groups \(\dfrac{n!}{n_1! \cdots n_k!}\)

And the one that turns any of them into a probability: \(P(A) = n_a/N\).

📋 Summary

  • Counting replaces listing once \(S\) is large; the sample-point method is otherwise unchanged

  • The \(mn\) rule handles anything built as a sequence of choices

  • Permutations count ordered selections, combinations count subsets, and \(\binom{n}{r} = P^n_r/r!\)

  • Theorem 2.3 is the general result: permutations and combinations are both special cases

  • For an equiprobable \(S\), every probability is a ratio of two counts

📚 Practice Problems

Wackerly, 7th edition

  • Exercises at the end of §2.6 — start with 2.35 – 2.40, then 2.44 and 2.49

  • Redo Wednesday’s Exercise 2.7 by counting rather than listing, and check that the two agree

Problem Set 1 closes 26 September at 23:59 on WeBWorK, covering Chapter 1 and §§2.1 – 2.8. A tutorial runs that week, before the deadline.

Next class: conditional probability and the independence of events — and why independence is not mutual exclusivity.

🙏 Thank You

Dr. Samir Orujov

📧 sorujov@ada.edu.az 🏢 Building D, Room D325 🕓 Office hours: Wednesday, 16:00 – 18:00

Slides and readings: sorujov.net/teaching

❓ Questions

  • Why does \(\binom{n}{r} = \binom{n}{n-r}\), without computing either side?

  • The four desks had named jobs. What changes if the four groups are interchangeable?

  • The maturity-clash probability passes 0.5 at 23 bonds out of 365 dates. Why so few?