Counting Principle

One of the first things you learn in mathematics is how to count. Now we want to count large
collections of things quickly and precisely. For instance:
• In a group of 10 people, if everyone shakes hands with everyone else exactly once, how
many handshakes took place?
• How many ways can you distribute 10 girl scout cookies to 7 boy scouts?
• How many anagrams are there of “anagram”?

Before tackling questions like these, let’s look at the basics of counting.

Consider this rather simple counting problem: at Red Dogs, and Donuts, there are 5 varieties
of donuts, and 6 types of hot dogs. If you want either a donut or a dog, how many options do you
have?

Additive Principle

The additive principle states that if event A can occur in m ways, and event B can occur in n
disjoint ways, then the event “A or B” can occur in m + n ways.

It is important that the events be disjoint: i.e., that there is no way for A and B to both happen
at the same time. For example, a standard deck of 52 cards contains 26 red cards and 12 face cards.
However, the number of ways to select a card which is either red or a face card is not 26 + 12 38.
This is because there are 6 cards which are both red and face cards.

Example:

1. How many two letter “words” start with either A or B? (A word is just a string of letters;
it doesn’t have to be English, or even pronounceable.)

Solution. First, how many two letter words start with A? We just need to select the second
letter, which can be accomplished in 26 ways. So there are 26 words starting with A. There are
also 26 words that start with B. To select a word which starts with either A or B, we can pick the
word from the first 26 or the second 26, for a total of 52 words.

The additive principle also works with more than two events. Say, in addition to your 14
choices for donuts and 16 for dogs, you would also consider eating one of 15 waffles? How many
choices do you have now? You would have 14 + 16 + 15 = 45 options.

2. How many two letter words start with one of the 5 vowels?
Solution. There are 26 two letter words starting with A, another 26 starting with E, and
so on. We will have 5 groups of 26. So we add 26 to itself 5 times. Of course it would be
easier to just multiply 5 · 26. We are really using the additive principle again, just using
multiplication as a shortcut.
 3. Suppose you are going for some fro-yo. You can pick one of 6 yogurt choices, and one of
4 toppings. How many choices do you have?
Solution. Break your choices up into disjoint events: A are the choices with the first
topping, B the choices featuring the second topping, and so on. There are four events;
each can occur in 6 ways (one for each yogurt flavor). The events are disjoint, so the
total number of choices is 6 + 6 + 6 + 6 24.

Note that in both of the previous examples, when using the additive principle on a bunch of
events all the same size, it is quicker to multiply. This really is the same, and not just because 6 + 6 +
6 + 6 4 · 6. We can first select the topping in 4 ways (that is, we first select which of the disjoint
events we will take). For each of those first 4 choices, we now have 6 choices of yogurt.

Multiplicative Principle

The multiplicative principle states that if event A can occur in m ways, and each possibility
for A allows for exactly n ways for event B, then the event “A and B” can occur in m · n ways.

The multiplicative principle generalizes to more than two events as well.

Example:
1. How many license plates can you make out of three letters followed by three numerical
digits?
Solution. Here we have six events: the first letter, the second letter, the third letter, the first
digit, the second digit, and the third digit. The first three events can each happen in 26 ways;
the last three can each happen in 10 ways. So the total number of license plates will be 26 ·
26 · 26 · 10 · 10 · 10, using the multiplicative principle.
Does this make sense? Think about how we would pick a license plate. How many choices
we would have? First, we need to pick the first letter. There are 26 choices. Now for each of
those, there are 26 choices for the second letter: 26 second letters with first letter A, 26
second letters with first letter B, and so on. We add 26 to itself 26 times. Or quicker: there
are 26 · 26 choices for the first two letters.
Now for each choice of the first two letters, we have 26 choices for the third letter. That is,
26 third letters for the first two letters AA, 26 choices for the third letter after starting AB,
and so on. There are 26 · 26 of these 26 third letter choices, for a total of (26 · 26) · 26
choices for the first three letters. And for each of these 26 · 26 · 26 choices of letters, we
have a bunch of choices for the remaining digits.
In fact, there are going to be exactly 1000 choices for the numbers. We can see this because
there are 1000 three-digit numbers (000 through 999). This is 10 choices for the first digit,
10 for the second, and 10 for the third. The multiplicative principle says we multiply: 10 · 10
· 10 = 1000.
 All together, there were 263 choices for the three letters, and 103 choices for the numbers,
so we have a total of 263 · 103 choices of license plates.

Reminder: “and” doesn’t mean “times.” For example, how many playing cards are both red and a
face card? Not 26 · 12. The answer is 6, and we needed to know something about cards to answer
that question.

Another Reminder: how many ways can you select two cards, so that the first one is a red card and
the second one is a face card? This looks more like the multiplicative principle (you are counting
two separate events) but the answer is not 26 · 12 here either. The problem is that while there
are 26 ways for the first card to be selected, it is not the case that for each of those there are 12
ways to select the second card. If the first card was both red and a face card, then there would be
only 11 choices for the second card. (To solve this problem, you could break it into two cases. First,
count how many ways there are to select the two cards when the first card is a red non-face card.
Second, count how many ways when the first card is a red face card. Doing so makes the events in each
separate case independent, so the multiplicative principle can be applied.)

2. How many functions f : {1, 2, 3, 4, 5} → {a, b, c, d} are there?

Solution. Remember that a function sends each element of the domain to exactly one
element of the codomain. To determine a function, we just need to specify the image of each
element in the domain. Where can we send 1? There are 4 choices. Where can we send 2?
Again, 4 choices. What we have here is 5 “events” (picking the image of an element in the
domain) each of which can happen in 4 ways (the choices for that image). Thus there are
4·4·4·4·4 = 45 functions.
This is more than just an example of how we can use the multiplicative principle in a
particular counting question. What we have here is a general interpretation of certain
applications of the multiplicative principle using rigorously defined mathematical objects:
functions. Whenever we have a counting question that asks for the number of outcomes of a
repeated event, we can interpret that as asking for the number of functions from {1, 2, . . . ,
n} (where n is the number of times the event is repeated) to {1, 2, . . . , k} (where k is the
number of ways that event can occur).

Combinations and Permutations

A permutation is a (possible) rearrangement of objects. For example, there are 6
permutations of the letters a, b, c:
abc, acb, bac, bca, cab, cba.

We know that we have them all listed above —there are 3 choices for which letter we put first, then
2 choices for which letter comes next, which leaves only 1 choice for the last letter. The
multiplicative principle says we multiply 3 · 2 · 1.
Examples:

1. How many permutations are there of the letters a, b, c, d, e, f ?

Solution. We do NOT want to try to list all of these out. However, if we did, we would need
to pick a letter to write down first. There are 6 choices for that letter. For each choice of first
letter, there are 5 choices for the second letter (we cannot repeat the first letter; we are
rearranging letters and only have one of each), and for each of those, there are 4 choices for
the third, 3 choices for the fourth, 2 choices for the fifth and finally only 1 choice for the last
letter. So there are 6 · 5 · 4 · 3 · 2 · 1 = 720 permutations of the 6 letters.

A piece of notation is helpful here: n!, read “n factorial”, is the product of all positive integers
less than or equal to n (for reasons of convenience, we also define 0! to be 1). So the number of
permutation of 6 letters, as seen in the previous example is 6! 6 · 5 · 4 · 3 · 2 · 1. This generalizes:

Permutations of n elements.

There are n! n ·(n -1)·(n -2)· · · · ·2·1 permutations of n (distinct) elements.

2. How many functions f : {1, 2, . . . , 8} → {1, 2, . . . , 8} are bijective?

Solution. Remember what it means for a function to be bijective: each element in the
codomain must be the image of exactly one element of the domain. Using two-line notation,
we could write one of these bijections as:

1 2 3 4 5 6 7 8
𝑓=( )
3 1 5 8 7 6 2 4

What we are really doing is just rearranging the elements of the codomain, so we are
creating a permutation of 8 elements. In fact, “permutation” is another term used to
describe bijective functions from a finite set to itself.

If you believe this, then you see the answer must be 8! 8 · 7 · · · · · 1 = 40320. You can see
this directly as well: for each element of the domain, we must pick a distinct element of the
codomain to map to. There are 8 choices for where to send 1, then 7 choices for where to
send 2, and so on. We multiply using the multiplicative principle.

3. How many 4 letter “words” can you make from the letters a through f, with no repeated
letters?
Solution. This is just like the problem of permuting 4 letters, only now we have more
choices for each letter. For the first letter, there are 6 choices. For each of those, there are 5
choices for the second letter. Then there are 4 choices for the third letter, and 3 choices for
the last letter. The total number of words is 6 · 5 · 4 · 3 = 360. This is not 6! because we
never multiplied by 2 and 1. We could start with 6! and then disregard the 2 and 1, and thus
6!
write
2!
 In general, how many permutations exist of k objects choosing those objects from a larger
collection of n objects. (In the example above, k = 4, and n = 6.) We write this number P(n, k) and
sometimes call it a k-permutation of n elements. From the example above, we see that to compute
P(n, k) we must apply the multiplicative principle to k numbers, starting with n and counting
backwards. For example
P(10, 4) = 10 · 9 · 8 · 7.

Notice again that P(10, 4) starts out looking like 10!, but we stop after 7. Formally account
for this “stopping” by dividing away the part of the factorial we do not want:

10.9.8.7.6.5.4.3.2.1 10!
𝑃(10,4) = =
6.5.4.3.2.1 6!

Reminder: The factorial in the denominator is not 4! but rather (10 - 4)!

k-permutations of n element

P (n, k) is the number of k-permutations of n elements, the number of ways to arrange k

objects chosen from n distinct objects.
𝑛!
𝑃(𝑛, 𝑘 ) = (𝑛−𝑘)! = 𝑛(𝑛 − 1)(𝑛 − 2) … (𝑛 − (𝑘 − 1)).
𝑛!
Note that when n=k, we have P(n,n) = (𝑛−𝑛)! = n! (since 0! Is said to be 1). This makes sense – we
already know n! gives the number of permutations of all n objects.

Example:

How many functions f : {1, 2, 3} → {1, 2, 3, 4, 5, 6, 7, 8} are injective?

Solution. Note that it doesn’t make sense to ask for the number of bijections here, as there are none
(because the codomain is larger than the domain, there are no surjections). But for a function to be
injective, we just can’t use an element of the codomain more than once.
We need to pick an element from the codomain to be the image of 1. There are 8 choices. Then we
need to pick one of the remaining 7 elements to be the image of 2. Finally, one of the remaining 6
elements must be the image of 3. So the total number of functions is 8 · 7 · 6 = P(8, 3).

What this demonstrates in general is that the number of injections f : A → B, where |A| = k and |B| =
n, is P (n, k).
 𝒏
Closed formula for ( )
𝒌

𝑛 𝑛! 𝑛(𝑛 − 1)(𝑛 − 2) … (𝑛 − (𝑘 − 1))

( )= = .
𝑘 (𝑛 − 𝑘 )! 𝑘! 𝑘 (𝑘 − 1)(𝑘 − 2) … 1

𝑛
We say P(n, k) counts permutations, and ( )counts combinations. The formulas for each are
𝑘
𝑛
very similar, there is just an extra k! in the denominator of ( ). That extra k! accounts for the fact
𝑘
𝑛
that ( ) does not distinguish between the different orders that the k objects can appear in. We are
𝑘
just selecting (or choosing) the k objects, not arranging them. Perhaps “combination” is a
misleading label. We don’t mean it like a combination lock (where the order would definitely
matter). Perhaps a better metaphor is a combination of flavors — you just need to decide which
flavors to combine, not the order in which to combine them.

To further illustrate the connection between combinations and permutations, we close with
an example:

You decide to have a dinner party. Even though you are incredibly popular and have 14
different friends, you only have enough chairs to invite 6 of them.
1. How many choices do you have for which 6 friends to invite?
2. What if you need to decide not only which friends to invite but also where to seat them
along your long table? How many choices do you have then?

Solution.

14
1. You must simply choose 6 friends from a group of 14. This can be done in ( ) ways. We
6
14!
can find this number either by using Pascal’s triangle or the closed formula 8!6! = 3003.
2. Here you must count all the ways you can permute 6 friends chosen from a group of 14. So
14!
the answer is P(14, 6), which can be calculated as 8!
= 2162160.
Notice that we can think of this counting problem as a question about counting functions: how
many injective functions are there from your set of 6 chairs to your set of 14 friends (the
functions are injective because you can’t have a single chair go to two of your friends).
14
How are these numbers related? Notice that P(14, 6) is much larger than ( ) . This makes
6
14
sense. ( )picks 6 friends, but P(14, 6) arranges the 6 friends as well as picks them. In fact, we
6
can say exactly how much larger P(14, 6) is. In both counting problems we choose 6 out of 14
friends. For the first one, we stop there, at 3003 ways. But for the second counting problem,
each of those 3003 choices of 6 friends can be arranged in exactly 6! ways. So now we
have 3003 · 6! choices and that is exactly 2162160.
Alternatively, look at the first problem another way. We want to select 6 out of 14 friends, but
we do not care about the order they are selected in. To select 6 out of 14 friends, we might try
this: 14 · 13 · 12 · 11 · 10 · 9.

This is a reasonable guess, since we have 14 choices for the first guest, then 13 for the second,
and so on. But the guess is wrong (in fact, that product is exactly 2162160 = P(14, 6)). It
distinguishes between the different orders in which we could invite the guests. To correct for
this, we could divide by the number of different arrangements of the 6 guests (so that all of
these would count as just one outcome). There are precisely 6! ways to arrange 6 guests,
so the correct answer to the first question is
14.13.12.11.10.9 14!
𝑜𝑟
6! 8! 6!