A computer does about a billion operations a second, so if we don’t know the answer, can we just try every case? Trying every four-digit password takes no time at all, but trying every way to line up 30 cards would take longer than the age of the universe. Let’s learn how to count the cases before trying them.
With 3 tops and 2 bottoms, there are 3 × 2 = 6 ways to dress. For each top you pick, you can choose from 2 bottoms. Likewise, when you make several choices in a row, multiplying the number of options at each step gives the total. This is called the rule of product.
A four-digit password made only of digits has 10 options for each digit, so there are 10 × 10 × 10 × 10 = 10,000. n bits also have 2 options each, so there are 2n. That’s why 8 bits can represent 256 numbers.
How many ways are there to top a pizza if you can pick any of n toppings? Each topping is either on or off, so there are 2n. Picking none and picking all count too.
A collection of things gathered without order is called a set, and a set made by picking some of them is called a subset. Writing 1 for each topping you pick and 0 for each you don’t pairs each subset with one n-bit string.
Raise the number of toppings one at a time. Faded toppings are the ones left off.
Each time you add a topping, every case splits into one without the new topping and one with it, so the count doubles.
How many ways are there to line up a dog, a cat, and a rabbit? The front has 3 options, the second spot the remaining 2, and the last 1, so 3 × 2 × 1 = 6. For n animals it’s the following, and this number is called n factorial.
Change the number of animals. Orders with the same animal in front are grouped together.
Let’s pick two of five fruits to make a juice. Picking as if lining them up, the first has 5 options and the second 4, so 5 × 4 = 20. But apple then banana and banana then apple make the same juice, so every juice was counted twice. Dividing by 2 gives 10.
Choosing k of n works the same way. Picking as if lining them up counts the same k items once for each of their k! orders, so we divide by k!. Choosing without order like this is called a combination, and the number of ways is written
nCk.
nCk = n × (n − 1) × … × (n − k + 1) / k!
🍎🍌, 🍌🍎: these 2 orders count as one
Checking every case, like trying every password one by one, is called brute-force search. It’s the simplest method, but it’s no use when there are too many cases. Let’s compare times, assuming we check a billion cases a second.
| What we count | Count | At 1 billion per second |
|---|---|---|
| Linear search n | 10 | 10 nanoseconds |
| Selection sort comparisons n(n − 1) / 2 | 45 | 45 nanoseconds |
| All subsets 2n | 1,024 | 1 microsecond |
| All orders n! | 3,628,800 | 3.6 milliseconds |
Raise n to 20, then to 30.
As n grows by one, the number of selection sort comparisons grows a little, but 2n doubles and n! grows n + 1 times. Counting the cases first tells you whether brute-force search is enough before you run anything.
You climb a staircase of 10 steps. Each stride can go up any number of steps, 1 or more, and you stop when you reach the top. Different orders of strides count as different ways (1 step then 2 is different from 2 then 1). How many ways are there to climb? Answer with a number.