Counting without listing

Every counting question is really a question about how many answers a decision procedure has. You already know how to answer such questions one way: write a loop, enumerate, look at the output. That works until the output is large, and then it stops working completely, not gradually. This lesson is about getting the number without ever producing the list.

/* multiplication rule */

  3 starters * 4 mains * 2 desserts  =  24

  plate: 4 letters, 3 digits
  26^4          = 456976
  26^4 * 10^3   = 456976000

  /* addition rule */
  12 routes + 7 routes  =  19 routes

The multiplication rule is the foundation, and it is genuinely this simple: if a choice can be made in a ways and, after that, a second choice in b ways, the pair can be made in a times b ways. Two rules of thumb keep it honest. Multiply when the choices happen in sequence, add when they are alternatives that never occur together. Almost every counting error is one of these two rules used where the other belonged.

/* ordered choice: pile of 10 people, 3 different prizes */

10 choices, then 9, then 8

  P(10, 3)  =  10 * 9 * 8
            =  720

  P(n, r)   =  n! / (n - r)!

Ten people and three distinct prizes gives one thousand, no, seven hundred and twenty ways, and the multiplication rule alone gets you there: ten choices for gold, nine remaining for silver, eight for bronze. This is an ordered selection, written P of n comma r, and the formula is a falling product that stops after r factors, which is n factorial divided by n minus r factorial. The count is only large because order counts as information.

/* unordered choice: same 10 people, 3 identical seats */

  C(n, r)   =  P(n, r) / r!

  C(10, 3)  =  720 / (3 * 2 * 1)
            =  720 / 6
            =  120

Now drop the order. The same three people standing on the podium in a different arrangement are not a different outcome when the prizes are identical, they are one group. Each group of three was counted three factorial times, once per ordering, so dividing by three factorial corrects exactly the overcount. That is the entire reason the divisor is r factorial and not some other correction: it is the number of orderings you just decided not to care about. C of 10 comma 3 is 120, six times smaller than the ordered answer, and the rule to remember is that combinations are permutations with the order divided out.

The pigeonhole principle is the first counting argument that gives a guaranteed answer rather than a likely one. If n items go into m boxes and n is greater than m, some box holds at least two. That is all it says, and it is obvious, and it is nevertheless one of the most useful tools in algorithm analysis, because it produces certainty from counting alone. A real application: a hash table has more possible keys than buckets, so collisions are not a sign of a bad hash function, they are a mathematical certainty. What a good hash does is spread them evenly, not remove them. Any argument that your system will not see collisions because the hash is good is wrong before it starts.

The pigeonhole principle is also why the question how many people are needed for two of them to share a birthday is not the question everyone answers first. People compare the number of people to the number of days and say a hundred and eighty. But the pigeonholes are not people against days, they are pairs of people against days, and the number of pairs grows quadratically while the number of people grows linearly. At twenty-three people there are two hundred and fifty-three pairs and the chance of at least one match is already about one half. This is the same shape as the collision argument above, and it is the reason a random identifier of sixty-four bits is fine while a random identifier of sixteen bits is a production incident.

birthday problem, 365 days

  two people differ:  364 / 365

  23 people:

  C(23, 2)  =  23 * 22 / 2  =  253 pairs

  (364 / 365)^253  =  0.4995
  1 - 0.4995       =  0.5005

  70 people:  1 - (364 / 365)^2415  >  0.999

Read the birthday numbers as a warning about intuition rather than a party trick. Sixty people produce one thousand seven hundred and seventy pairs, and the chance of a shared birthday passes ninety-nine percent. Nothing about that is subtle arithmetic; the surprise comes entirely from the fact that we estimate pairwise events as if they were independent, and they are not. The practical version for a software engineer is that the space of collisions is quadratic in the number of objects, so the birthday bound is always much lower than the naive one.

/* brute force, 10^9 steps per second */

n = 1    2!        =  2
n = 10   10!       =  3.6 * 10^6
n = 13   13!       =  6.2 * 10^9    6 seconds
n = 15   15!       =  1.3 * 10^12   22 minutes
n = 18   18!       =  6.4 * 10^15   74 days
n = 20   20!       =  2.4 * 10^18   77 years
n = 25   25!       =  1.6 * 10^25   5 * 10^8 years

Finally, this is why counting matters for algorithms. A permutation search over twenty items is not twenty times slower than a search over one item, it is twenty factorial, which exceeds the number of seconds the universe has existed by a wide margin. The jumps between the lines below are not a smooth curve, they are a cliff, and the cliff is why an algorithm that is correct on small inputs can be completely unusable on real ones. When someone says a problem is hard, they usually mean the brute-force solution is a permutation count, and no amount of hardware changes that.