\( \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\mathbf{#1}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

M01.8 · Counting and combinatorics

A free, illustrated module of 4 lessons and one interactive in M01 Math Foundations: Counting by multiplying and adding; Permutations: arrangements in order; Combinations: choosing without order; Pascal’s triangle and the binomial theorem.

M01.8 L0 · Foundation 4 lessons · about 100 min Live · in review

Part of M01 Math Foundations in the Mathematics track.

How many training runs does a grid of settings need, how many orders can a data set be shuffled into, and how many test sets of two can five examples give? These four lessons count such things without listing them. Choices made in stages multiply and separate cases add; arranging n things in a row gives n factorial orders; choosing without order divides out the orders of each choice, which gives n choose k; and those numbers, laid out as Pascal’s triangle, are the coefficients of (a + b) to the power n.

What you need first. Sets, their size, union and intersection (M01.6.1), whole-number powers (M01.4.1), the product sign and n factorial (M01.7.4), and the sum 1 + 2 + … + n (M01.7.3). The last lesson uses the expansion of (a + b) squared (M01.1.2) and the sum sign (M01.7.2).

Lessons

1. Counting by multiplying and adding M01.8.1 25 min

   Count outcomes without listing them. Choices made in stages multiply, as a tree shows; cases that cannot happen together add; and an overlap is subtracted once. Worked on pairs, strings of bits, the subsets of a set and a grid of training runs.

2. Permutations: arrangements in order M01.8.2 25 min

   Put n different things in a row in n! ways, pick k of them in order in n!/(n - k)! ways, and see why 0! = 1. Worked on five items, with 120 orders and 60 ordered picks of three, and on why no computer can try every order of a shuffled data set.

3. Combinations: choosing without order M01.8.3 25 min

   Count the ways to choose k of n things when order does not matter. Each choice appears k! times among the ordered picks, so the count is n!/(k!(n - k)!), read n choose k. Worked on the 10 ways to hold out 2 of 5 examples as a test set.

4. Pascal’s triangle and the binomial theorem M01.8.4 25 min

   Build Pascal’s triangle by adding, prove Pascal’s rule by asking whether a choice contains the first item, show that row n adds up to 2^n, and multiply out (a + b)^n with the binomial theorem by choosing which brackets give b.

The interactive

M01.8-X1 · Choose-and-arrange explorer. Pick up to five items and up to three places, and switch “order matters” and “repeats allowed” on or off. Every outcome is listed, the orders of one selection are grouped together, and the count is shown beside the formula that gives it. It lives in Combinations: choosing without order.