Many results in mathematics are answers to “How many …” questions.

“How many subsets does a finite set have?”

“How many handshakes will transpire when \(n\) people first meet?”

“How many functions are there from a set of size \(n\) to a set of size \(m\)?”

The title of this section, “Counting,” is not intended to evoke the usual process of counting sheep, or counting change. What we want is to be able to count some collection in principle so that we will be able to discover a formula for its size.

There are two principles that will be indispensable in counting things. These principles are simple, yet powerful, and they have been named in the most unimaginative way possible. The “multiplication rule” which tells us when we should multiply, and the “addition rule” which tells us when we should add.

Before we describe these principles in detail, we'll have a look at a simpler problem which is most easily described by an example: How many integers are there in the list \((7,8,9,\ldots 44)\)? We could certainly write down all the integers from \(7\) to \(44\) (inclusive) and then count them — although this wouldn't be the best plan if the numbers \(7\) and \(44\) were replaced with (say) \(7,045,356\) and \(22,355,201\). A method that does lead to a generalized ability to count the elements of a finite sequence arises if we think carefully about what exactly a finite sequence is.

Now it is easy to see that there are \(n+1\) elements in the set \(\{0, 1, 2, \ldots , n \}\) so counting the elements of a finite sequence will be easy if we can determine the function involved and figure out what \(n\) is by inverting it (\(n\) is an inverse image for the last element in a listing of the sequence).

In the example that we started with, the function is \(f(x)=x+7\). We can sum up the process that allows us to count the sequence by saying ``there is a one-to-one correspondence between the lists \begin{equation*} (7, 8, 9, \ldots , 44 ) \end{equation*} and \begin{equation*} (0, 1, 2, \ldots , 37 ) \end{equation*} and the later has \(38\) entries.''

More generally, if there is a list of consecutive numbers beginning with \(k\) and ending with \(n\), there will be \(n-k+1\) entries in the list. Lists of consecutive integers represent a relatively simple type of finite sequence. Usually we would have some slightly more interesting function that we'd need to invert.

The following exercise involves inverting the function \((x+5)^2\).

We will have a lot more practice with counting the elements of sequences in the exercises at the end of this section, let's continue on our tour of counting by having a look at the addition rule.

The addition rule says that it is appropriate to add if we can partition a collection into disjoint pieces. In other words, if a set \(S\) is the union of two or more subsets and these subsets are mutually disjoint, we can find the size of \(S\) by adding the sizes of the subsets.

In the game Yahtzee, one rolls 5 dice and (optionally) performs a second roll of some or all of the dice. The object is to achieve several final configurations that are modeled after the hands in Poker. In particular, one configuration, known as a “full house,” is achieved by having two of one number and three of another. (Colloquially, we say “three-of-a-kind plus a pair is a full house.”)

Now, we could use Yahtzee “hands” to provide us with a whole collection of counting problems once we have our basic counting principles, but for the moment we just want to make a simple (and obvious) point about “full houses” — the pair is either smaller or larger than the three-of-a-kind. This means we can partition the set of all possible full houses into two disjoint sets — the full houses consisting of a small pair and a larger three-of-a-kind and those where the pair is larger than the three-of-a-kind. If we can find some way of counting these two cases separately, then the total number of full houses will be the sum of these numbers.

The multiplication rule gives us a way of counting things by thinking about how we might construct them. The numbers that are multiplied are the number of choices we have in the construction process. Surprisingly often, the number of choices we can make in a given stage of constructing some configuration is independent of the choices that have gone before — if this is not the case the multiplication rule may not apply.

If some object can be constructed in \(k\) stages, and if in the first stage we have \(n_1\) choices as to how to proceed, in the second stage we have \(n_2\) choices, et cetera. Then the total number of such objects is the product \(n_1n_2 \cdots n_k\).

A permutation of an \(n\)-set (w.l.o.g. \(\{1,2,\ldots , n\}\)) is an ordered \(n\)-tuple where each entry is a distinct element of the \(n\)-set. Generally, a permutation may be regarded as a bijection from an \(n\)-set to itself. Our first use of the multiplication rule will be to count the total number of permutations of \(\{1, 2, 3, \ldots ,n\}\).

Let's start by counting the permutations of \(\{1, 2, 3\}\). A permutation will be a 3-tuple containing the numbers \(1\), \(2\) and \(3\) in some order. We will think about building such a thing in three stages. First, we must select a number to go in the first position — there are \(3\) choices. Having made that choice, there will only be two possibilities for the number in the second position. Finally there is just one number remaining to put in the third position¹People may say you have “no choice” in this last situation, but what they mean is that you have only one choice.. Thus there are \(3\cdot 2\cdot 1 = 6\) permutations of a \(3\) element set.

The general rule is that there are \(n!\) permutations of \(\{1, 2, \ldots , n\}\).

There are times when configurations that are like permutations (in that they are ordered and have no duplicates) but don't consist of all \(n\) numbers are useful.

There are certain natural limitations on the value of \(k\), for instance \(k\) can't be negative — although (arguably) \(k\) can be 0, it makes more sense to think of \(k\) being at least 1. Also, if \(k\) exceeds \(n\) we won't be able to find any \(k\)-permutations, since it will be impossible to meet the “distinct” requirement. If \(k\) and \(n\) are equal, there is no difference between a \(k\)-permutation and an ordinary permutation. Therefore, we ordinarily restrict \(k\) to lie in the range \(0 \lt k \lt n\).

The notation \(P(n,k)\) is used for the total number of \(k\)-permutations of a set of size \(n\). For example, \(P(4,2)\) is 12, since there are twelve different ordered pairs having distinct entries where the entries come from \(\{1,2,3,4\}\).

Counting \(k\)-permutations using the multiplication rule is easy. We build a \(k\)-permutation in \(k\) stages. In stage 1, we pick the first element in the permutation — there are \(n\) possible choices. In stage 2, we pick the second element — there are now only \(n-1\) choices since we may not repeat the first entry. We keep going like this until we've picked \(k\) entries. The number \(P(n,k)\) is the product of \(k\) numbers beginning with \(n\) and descending down to \(n-k+1\). To verify that \(n-k+1\) is really the right lower limit, check that there are indeed \(k\) entries in the sequence \begin{equation*} (n, n-1, n-2, \ldots n-k+1). \end{equation*}

This verification may be easier if we rewrite the sequence as \begin{equation*} (n-0, n-1, n-2, \ldots n-(k-1) ). \end{equation*}

Let's have a look at another small example — \(P(8,4)\). There will be 8 choices for the first entry in a 4-tuple, 7 choices for the second entry, 6 choices for the third entry and 5 choices for the last entry. (Note that \(5 = 8-4+1\).) Thus \(P(8,4)=8\cdot 7 \cdot 6 \cdot 5 = 1680\).

Finally, we should take note that it is relatively easy to express \(P(n,k)\) using factorials. If we divide a number factorialized by some smaller number factorialized, we will get a descending product just like those above.

The general rule is that \(P(n,k) = \frac{n!}{(n-k)!}\).

If we were playing a card game in which we were dealt 5 cards from a deck of 52, we would receive our cards in the form of \(P(52,5) = 52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 = 311875200\) ordered \(5\)-tuples. Normally, we don't really care about what order the cards came to us in. In a card game one ordinarily begins sorting the cards so as to see what hand one has — this is a sure sign that the order the cards were dealt is actually immaterial. How many different orders can five cards be put in? The answer to this question is \(5! = 120\) since what we are discussing is nothing more than a permutation of a set of size 5. Thus, if we say that there are 311,875,200 different possible hands in 5-card poker, we are over-counting things by quite a bit! Any given hand will appear 120 times in that tabulation, which means the right value is \(311875200/120 = 2598960\).

Okay, so there around 2.6 million different hands in 5-card poker. Unless you plan to become a gambler this isn't really that useful of a piece of information — but if you generalize what we've done in the paragraph above, you'll have found a way to count unordered collections of a given size taken from a set.

A \(k\)-combination from an \(n\)-set is an unordered selection, without repetitions, of \(k\) things out of \(n\). This is the exact same thing as a subset of size \(k\) of a set of size \(n\), and the number of such things is denoted by several different notations — \(C(n,k)\), \(nCk\) and \(\displaystyle\binom{n}{k}\) among them²Watch out for the \(\binom{n}{k}\) notation, it is easy to confuse it with the fraction \(\left(\frac{n}{k}\right)\). They are not the same — the fraction bar is supposed to be missing in \(\binom{n}{k}\).. We can come up with a formula for \(C(n,k)\) by a slightly roundabout argument. Suppose we think of counting the \(k\)-permutations of \(n\) things using the multiplication rule in a different way then we have previously. We'll build a \(k\)-permutation in two stages. First we'll choose \(k\) symbols to put into our permutation — which can be done in \(C(n,k)\) ways. And second, we'll put those \(k\) symbols into a particular order — which can be accomplished in \(k!\) ways. Thus \(P(n,k) = C(n,k) \cdot k!\). Since we already know that \(P(n,k) = \frac{n!}{(n-k)!}\), we can substitute and solve to obtain \begin{equation*} C(n,k) = \frac{n!}{k! \cdot (n-k)!}. \end{equation*}

It is possible to partition many counting problems into 4 “types” based on the answers to two questions:

Is order important in the configurations being counted?

Are we allowed to have repeated elements in a configuration?

Suppose that we are in the general situation of selecting \(k\) things out of a set of size \(n\). It should be possible to write formulas involving \(n\) and \(k\) in the four cells of the following table.

Ordered with repetition

Selecting a PIN number³The phrase “PIN number” is redundant. The `N' in PIN stands for “number.” Anyway, a PIN is a four digit (secret) number used to help ensure that automated banking (such as withdrawing your life's savings) is only done by an authorized individual. for your bank account is a good example of the kind of problem that is dealt with in the lower left part of the table. Obviously, the order in which you key-in the digits of your PIN is important. If one's number is 1356, it won't do to put in 6531! Also there is no reason that we couldn't have repeated digits in a PIN. (Although someone who chooses a PIN like 3333 is taking a bit of a security risk! A bad guy looking over your shoulder may easily discern what your PIN is.) A PIN is an ordered selection of 4 things out of 10, where repetition is allowed. There are \(10^4\) possible PINs. We can determine this by thinking of the multiplication principle — there are 10 choices for the first digit of our PIN, since repetition is okay there are still 10 choices for our second digit, then (still) 10 choices for the third digit as well as the fourth digit.

In general, when selecting \(k\) things out of \(n\) possibilities, where order counts and repetition is allowed, there are \(n^k\) possible selections.

Ordered without repetition

Suppose that one wishes to come up with a password for a computer account. There are 52 letters (both upper and lower case) 10 numerals and 32 symbols and punctuation marks — for a total of 94 different characters that may be used. Some system administrators can be very paranoid about passwords that might be guessable — for instance no password that appears in a dictionary should ever be used on a system where security is a concern. Suppose that your system administrator will reject any password that has repeated symbols, and that passwords must have 8 characters. How many passwords are possible?

This is an instance of a counting problem where we are selecting 8 things out of a set of size 94 — clearly order is important and the system administrator's restriction means that we may not have repeats. The multiplication rule tells us that there are \(94\cdot 93\cdot 92\cdot 91\cdot 90\cdot 89\cdot 88\cdot 87 = 4488223369069440\) different passwords. And in the general case (selecting \(k\) things out of a set of size \(n\), without repetition, and with order counting) there will be \(n!/(n-k)!\) possibilities. This is the number we have denoted previously by \(P(n,k)\).

Unordered without repetition

This is also a case that we've considered previously. If we are choosing \(k\) things out of \(n\) and order is unimportant and there can be no repetitions, then what we are describing is a \(k\)-subset of the \(n\)-set. There are \(C(n,k) = \frac{n!}{k!(n-k)!}\) distinct subsets. Here, we'll give an example that doesn't sound like we're talking about counting subsets of a particular size. (Although we really are!)

How many different sequences of 6 strictly increasing numbers can we choose from \(\{1, 2, 3, \ldots 20\}\)?

Obviously, listing all such sequences would be an arduous task. We might start with \((1,2,3,4,5,6)\) and try to proceed in some orderly fashion to \((15,16,17,18,19,20)\), but unfortunately there are 38,760 such sequences so unless we enlist the aid of a computer we are unlikely to finish this job in a reasonable time. The number we've just given (38,760) is \(C(20,6)\) and so it would seem that we're claiming that this problem is really unordered selection without repetition of 6 things out of 20. Well, actually, some parts of this are clearly right — we are selecting 6 things from a set of size 20, and because our sequences are supposed to be strictly increasing there will be no repetitions — but, a strictly increasing sequence is clearly ordered and the formula we are using is for unordered collections.

By specifying a particular ordering (strictly increasing) on the sequences we are counting above, we are actually removing the importance of order. Put another way: if order really mattered, the symbols \(1\) through \(6\) could be put into \(720\) different orders — but we only want to count one of those possibilities. Put another other way: there is a one-to-one correspondence between a \(6\)-subset of \(\{1,2,3, \ldots 20\}\) and a strictly increasing sequence. Just make sure the subset is written in increasing order!

Okay, at this point we have filled-in three out of the four cells in our table.

What kinds of things are we counting in the lower right part of the table? Unordered selections of \(k\) things out of \(n\) possibilities where there may (or may not!) be repetitions. The game Yahtzee provides a nice example of this type of configuration. When we roll 5 dice, we do not do so one-at-a-time, rather, we roll them as a group — the dice are indistinguishable so there is no way to order our set of 5 outcomes. In fact, it would be quite reasonable to, after one's roll, arrange the die in (say) increasing order. We'll repeat a bit of advice that was given previously: if one is free to rearrange a configuration to suit one's needs, that is a clue that order is not important in the configurations under consideration. Finally, are repetitions allowed? The outcomes in Yahtzee are 5 numbers from the set \(\{1,2,3,4,5,6\}\), and while it is possible to have no repetitions, that is a pretty special outcome! In general, the same number can appear on two, or several, or even all 5 of the die⁴When this happens you are supposed to jump in the air and yell “Yahtzee!”.

So, how many different outcomes are there when one rolls five dice? To answer this question it will be helpful to think about how we might express such an outcome. Since order is unimportant, we can choose to put the numbers that appear on the individual die in whatever order we like. We may as well place them in increasing order. There will be 5 numbers and each number is between 1 and 6. We can list the outcomes systematically by starting with an all-ones Yahtzee:

Whew … err, I mean, Yahtzee!

You can describe a generic element of the above listing by saying “It starts with some number of 1's (which may be zero), then there are some 2's (again, it might be that there are zero 2's), then some (possibly none) 3's, then some 4's (or maybe not), then some 5's (I think you probably get the idea) and finally some 6's (sorry for all the parenthetical remarks).”

We could, of course, actually count the outcomes as listed above (there are 252) but that would be pretty dull — and it wouldn't get us any closer to solving such problems in general. To count things like Yahtzee rolls it will turn out that we can count something related but much simpler — blank-comma arrangements. For the Yahtzee problem we count arrangements of 5 blanks and 5 commas. That is, things like { \rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt},\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt},,\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt},\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt},} and { \rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt},,,,,} and { ,,,\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt},,}. These arrangements of blanks and commas correspond uniquely to Yahtzee rolls — the commas serve to separate different numerical values and the blanks are where we would write-in the 5 outcomes on the die.

Convince yourself that there really is a one-to-one correspondence between Yahtzee outcomes and arrangements of 5 blanks and 5 commas by doing the following

It may seem at first that this blank-comma thing is okay, but that we're still no closer to answering the question we started with. It may seem that way until you realize how easy it is to count these blank-comma arrangements! You see, there are 10 symbols in one of these blank-comma arrangements and if we choose positions for (say) the commas, the blanks will have to go into the other positions — thus every 5-subset of \(\{1,2,3,4,5,6,7,8,9,10\}\) gives us a blank-comma arrangement and every one of them gives us a Yahtzee outcome. That is why there are \(C(10, 5) = 252\) outcomes listed in the giant tabulation above.

In general, when we are selecting \(k\) things from a set of size \(n\) (with repetition and without order) we will need to consider blank-comma arrangements having \(k\) blanks and \(n-1\) commas. As an aid to memory, consider that when you actually write-out the elements of a set it takes one fewer commas than there are elements — for example \(\{1,2,3,4\}\) has 4 elements but we only need 3 commas to separate them. The general answer to our problem is either \(C(k+n-1,k)\) or \(C(k+n-1, n-1)\), depending on whether you want to think about selecting positions for the \(k\) blanks or for the \(n-1\) commas. It turns out that these binomial coefficients are equal so there's no problem with the apparent ambiguity.

So, finally, our table of counting formulas is complete. We'll produce it here one more time and, while we're at it, ditch the \(C(n,k)\) notation in favor of the more usual “binomial coefficient” notation \(\binom{n}{k}\).