1. What counting is

Recall that in SetTheory we formally defined each natural number as the set of all smaller natural numbers, so that n = { 0, 1, 2, ..., n-1 }. Call a set finite if it can be put in one-to-one correspondence with some natural number n. For example, the set S = { Larry, Moe, Curly } is finite because we can map Larry to 0, Moe to 1, and Curly to 2, and get a bijection between S and the set 3 = { 0, 1, 2 }. The size or cardinality of a finite set S, written |S| or #S, is just the natural number it can be put in one-to-one correspondence with; that this is well-defined (gives a unique size for each finite set) follows from the PigeonholePrinciple.

A set that cannot be put in one-to-one correspondence with any natural number is infinite; one of the smallest infinite sets is just the set of all naturals N. Any infinite set also has a cardinality; as for finite sets, the cardinality of an infinite set is defined based on what other sets it can be put into one-to-one correspondence with, and different infinite sets may have different cardinalities (see Cardinal_number for more about this if you are interested).

2. Basic counting techniques

Our goal here is to compute the size of some set of objects, e.g. the number of subsets of a set of size n, the number of ways to put k cats into n boxes so that no box gets more than one cat, etc.

In rare cases we can use the definition of the size of a set directly, by constructing a bijection between the set we care about and some natural number. For example, the set S_n = { x ∈ N | x < n² /\ ∃y: x = y² } has exactly n members, because we can generate it by applying the one-to-one correspondence f(y) = y² to the set { 0, 1, 2, 3, ..., n-1 } = n. But most of the time constructing an explicit one-to-one correspondence is too time-consuming or too hard, so having a few lemmas around that tell us what the size of a set will be can be handy.

2.1. Reducing to a previously-solved case

If we can produce a bijection between a set A whose size we don't know and a set B whose size we do, then we get |A|=|B|. Pretty much all of our proofs of cardinality will end up looking like this.

2.2. Sum rule

The sum rule says

If A∩B=Ø, then |A∪B| = |A| + |B|.

Proof: Let f:A→|A| and g:B→|B| be bijections. Define h:A∪B→(|A|+|B|) by the rule h(x) = f(x) for x∈A, h(x) = |A|+g(x) for x∈B. We need to show that h is a bijection; we will do so by first showing that it is injective, then that it is surjective. Let x and y be distinct elements of A∪B. If x and y are both in A, then h(x) = f(x) ≠ f(y) = h(y); similarly if x and y are both in B, h(x) = |A|+g(x) ≠ |A| + g(y) = h(y). If x is in A and y in B, then h(x) = f(x) < |A|, and h(y) = g(y) + |A| ≥ |A|; it follows that h(x) ≠ h(y). The remaining case is symmetric. To show h is surjective, let m∈(|A|+|B|). If m < |A|, there exists some x∈A such that h(x) = f(x) = m. Otherwise, we have |A| ≤ m < |A|+|B|, so 0 ≤ m - |A| < |B|, and there exists some y∈B such that g(y) = m-|A|. But then h(y) = g(y)+|A| = m-|A|+|A| = m.

Generalizations: If A₁, A₂, A₃ ... A_k are pairwise disjoint (i.e. A_i ∩ A_j = Ø for all i ≠j), then

$\left|\bigcup_{i=1}^{k} A_i\right| = \sum_{i=1}^{k} |A_i|.$

Example: As I was going to Saint Ives, I met a man with 7 wives, 28 children, 56 grandchildren, and 122 great-grandchildren. Assuming these sets do not overlap, how many people did I meet? Answer: 1+7+28+56+122=214.

2.3. Inclusion-exclusion

What if A and B are not disjoint, i.e., if A∩B is not Ø? In this case adding |A| to |B| will count any element that appears in both sets twice. We can get the size of |A∪B| by subtracting off the overcount, obtaining this formula, which works for all A and B:

|A∪B| = |A| + |B| - |A∩B|

To prove that the formula works, we use the sum rule. Observe that A = (A∩B) ∪ (B-A) and that the union in this case is disjoint (recall that A-B is the set of all elements that are in A but not in B). A similar decomposition works for B, so we have

|A| + |B| = |A∩B| + |B-A| + |B∩A| + |A-B| = |A∪B| + |A∩B|.

Here we are again using the sum rule: A∪B is the disjoint union of A-B, B-A, and A∩B. Subtracting the |A∩B| term from both sides gives the formula we originally wanted.

This is a special case of the inclusion-exclusion_principle, which can be used to compute the size of the union of many sets using the size of pairwise, triple-wise, etc. intersections of the sets.

2.4. Product rule

The product rule says that for any sets A and B

|A×B| = |A|·|B|.

Recall that A×B is the Cartesian product of A and B, the set of all ordered pairs whose first element comes from A and whose second comes from B.

Proof: Let f:A→|A| and g:B→|B| be bijections. Construct a new function h:|A×B|→(|A|·|B|) by the rule h(<a,b>) = a·|B| + b. Showing that h is a bijection is left as an exercise to the reader (hint: use the DivisionAlgorithm).

The general form is

$\left|\prod_{i=1}^{k} A_i\right| = \prod_{i=1}^{k} |A_i|,$

where the product on the left is a Cartesian product and the product on the right is an ordinary integer product.

Example: As I was going to Saint Ives, I met a man with seven sacks, and every sack had seven cats. How many cats total? Answer: Label the sacks 0,1,2,...,6, and label the cats in each sack 0,1,2,...,6. Then each cat can be specified uniquely by giving a pair <sack number, cat number>, giving a bijection between the set of cats and the set 7×7. Since the |7×7|=7·7=49, we have 49 cats.

Example: Dr Frankenstein's trusty assistant Igor has brought him 6 torsos, 4 brains, 8 pairs of matching arms, and 4 pairs of legs. How many different monsters can Dr Frankenstein build? Answer: there is a one-to-one correspondence between possible monsters and 4-tuples of the form <torso, brain, pair of arms, pair of legs>; the set of such 4-tuples has 6·4·8·4=728 members.

Example: How many different ways can you order n items? Call this quantity n! (i.e., n factorial). With 0 or 1 items, there is only one way; so we have 0!=1!=1. For n > 1, there are n choices for the first item, leaving n-1 items to be ordered. From the product rule we thus have n! = n·(n-1)!, which we could also expand out as

$\prod_{i=1}^{n} i.$

As a generalization of the previous example, we can count the number of ways P(n,k) we can pick an ordered subset of k of n items without replacement, also known as picking a k-permutation. There are n ways to pick the first item, n-1 to pick the second, and so forth, giving a total of

$P(n,k) = \prod_{i=n-k+1}^{n} i = \frac{n!}{(n-k)!}$

such k-permutations by the product rule.

Among combinatorialists, the notation n_(k) (pronounced "n lower-factorial k") is more common than P(n,k) for n·(n-1)·(n-2)·...·(n-k+1). As an extreme case we have n_(n) = n·(n-1)·(n-2)·...·(n-n+1) = n·(n-1)·(n-2)·...·1 = n!.

2.5. Counting the same thing in two different ways

An old farm joke:

Q: How do you count a herd of cattle? A: Count the legs and divide by four.

Sometimes we can compute the size of a set S by using it (as an unknown variable) to compute the size of another set T (as a function of |S|), and then using some other way to count T to find its size, finally solving for |S|. This is known as counting two ways and is surprisingly useful when it works.

Example: Let S be an element set, and consider the set S_k = { A⊆S | |A| = k }. What is |S_k|? Answer: First we'll count the number m of sequences of k elements of S with no repetitions. We can get such a sequence in two ways:

By picking a size-k subset A and then choosing one of k! ways to order the elements. This gives m = |S_k|·k!.
By choosing the first element in one of n ways, the second in one of n-1, the third in one of n-2 ways, and so on until the k-th element, which can be chosen in one of n-k+1 ways. This gives m = n_(k) = n·(n-1)·(n-2)·...(n-k+1), which can be written as n!/(n-k)!. (Here we are using the factors in (n-k)! to cancel out the factors in n! that we don't want.)

So we have m = |S_k|·k! = n!/(n-k)!, from which we get

$|S_k| = \frac{n!}{k!\cdot(n-k)!}.$

This quantity turns out to be so useful that it has a special notation:

${n \choose k} \stackrel{\mbox{\scriptsize def}}{=} \frac{n!}{k!\cdot(n-k)!}.$

where the left-hand side is known as a binomial coefficient and is pronounced "n choose k." We discuss BinomialCoefficients at length on their own page. The secret of why it's called a binomial coefficient will be revealed when we talk about GeneratingFunctions.

Example: Here's a generalization of binomial coefficients: let the multinomial coefficient

${n \choose n_1 \; n_2 \; \ldots \; n_k}$

be the number of different ways to distribute n items among k bins where the i-th bin gets exactly n_i of the items and we don't care what order the items appear in each bin. (Obviously this only makes sense if n₁+n₂+...+n_k=n.) Can we find a simple formula for the multinomial coefficient?

Here are two ways to count the number of permutations of the n-element set:

Pick the first element, then the second, etc. to get n! permuations.
Generate a permutation in three steps:
1. Pick a partition of the n elements into groups of size n₁, n₂, ... n_k.
2. Order the elements of each group.
3. Paste the groups together into a single ordered list.

There are

${n \choose n_1 \; n_2 \; \ldots \; n_k}$

ways to pick the partition and

$n_1! \cdot n_2! \cdots n_k!$

ways to order the elements of all the groups, so we have

$n! = {n \choose n_1 \; n_2 \; \ldots \; n_k} \cdot n_1! \cdot n_2! \cdots n_k!$

which we can solve to get

${n \choose n_1 \; n_2 \; \ldots \; n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

This also gives another way to derive the formula for a binomial coefficient, since

${n \choose k} = {n \choose k \;\; (n-k)} = \frac{n!}{k!\cdot (n-k)!}$

3. Applying the rules

If you're given some strange set to count, look at the structure of its description:

If it's given by a rule of the form x is in S if either P(x) or Q(x) is true, use the sum rule (if P and Q are mutually exclusive) or inclusion-exclusion. This includes sets given by recursive definitions, e.g. x is a tree of depth at most k if it is either (a) a single leaf node (provided k > 0) or (b) a root node with two subtrees of depth at most k-1. The two classes are disjoint so we have T(k) = 1 + T(k-1)² with T(0) = 0.¹
For objects made out of many small components or resulting from many small decisions, try to reduce the description of the object to something previously known, e.g. (a) a word of length k of letters from an alphabet of size n allowing repetition (there are n^k of them, by the product rule); (b) a word of length k not allowing repetition (there are n_(k) of them---or n! if n = k); (c) a subset of k distinct things from a set of size n, where we don't care about the order (there are (n choose k) of them); any subset of a set of n things (there are 2ⁿ of them---this is a special case of (a), where the alphabet encodes non-membership as 0 and membership as 1, and the position in the word specifies the element). Some examples:
- The number of games of Tic-Tac-Toe assuming both players keep playing until the board is filled is obtained by observing that each such game can be specified by listing which of the 9 squares are filled in order, giving 9! = 362,880 distinct games. Note that we don't have to worry about which of the 9 moves are made by X and which by O, since the rules of the game enforce it. (If we only consider games that end when one player wins, this doesn't work: probably the easiest way to count such games is to send a computer off to generate all of them.)
- The number of completely-filled-in Tic-Tac-Toe boards can be obtained by observing that any such board has 5 X's and 4 O's. So there are (9 choose 5) = 126 such positions.

Sometime reducing to a previous case requires creativity. For example, suppose you win n identical cars on a game show and want to divide them among your k greedy relatives. Assuming that you don't care about fairness, how many ways are there to do this?

If it's ok if some people don't get a car at all, then you can imagine putting n cars and k-1 dividers in a line, where relative 1 gets all the cars up to the first divider, relative 2 gets all the cars between the first and second dividers, and so forth up to relative k who gets all the cars after the (k-1)th divider. Assume that each car---and each divider---takes one parking space. Then you have n+k-1 parking spaces with k-1 dividers in them (and cars in the rest). There are exactly (n+k-1 choose k-1) ways to do this.
Alternatively, suppose each relative demands at least 1 car. Then you can just hand out one car to each relative to start with, leaving n-k cars to divide as in the previous case. There are ((n-k)+k-1 choose k-1) = (n-1 choose k-1) ways to do this.

Finding such correspondences is a central part of enumerative combinatorics, the branch of mathematics that deals with counting things.

4. Further reading

RosenBook does basic counting in chapter 5 and more advanced counting (including SolvingRecurrences and using GeneratingFunctions) in chapter 7. BiggsBook chapters 6 and 10 give a basic introduction to counting, with more esoteric topics in chapters 11 and 12. ConcreteMathematics has quite a bit on counting various things.

CategoryMathNotes

Of course, just setting up a recurrence doesn't mean it's going to be easy to actually solve it. (1)