In this lesson, we are going to talk about counting. With this, we are starting a new section; and at first, it might seem that counting is a simple thing, but it actually turns out that it is extremely important in math. The formal study of counting is called combinatorics, and this course will barely scratch the surface of combinatorics. First, we are going to define the idea of an event; an event is simply something happening. In this lesson, we will learn some principles, like the addition principle and the multiplication principle, which is also known as the fundamental counting principle.
A permutation is a way to order some set of objects. A combination is a way to choose some group of objects from a larger set of objects. In this case, we don't care about order, just which objects are selected.
Multiplying successive positive integers is shown by factorial notation. The symbol `!' is the symbol for factorial, and it works like this (where n ∈ ℕ):
n! = (n)(n−1)(n−2)…(3)(2)(1).
That is, it multiplies the number by every positive integer below the number. [We say `n!' as "n factorial".] To make certain math formulas easier to work with in the future, we define 0! = 1.
The number of permutations of n objects (in other words, how many different orders the objects can be put in) is equal to
n! = (n)(n−1)(n−2)…(3)(2)(1).
The number of ways to order r objects out of a set of n objects total is
This comes up often enough to have its own symbols: nPr or P(n,r).
If we're permuting a set where some of the objects are not distinguishable from one another (like the letters of a word), the number of distinguishable permutations is
where n is the total number of objects in the set and n1, …, nk, are the numbers of each object "type".
Given some set of n objects that we are going to choose r from (with no consideration for order), the number of possible combinations is
This comes up often enough to have its own symbols: nCr, (n || r), C(n,r).
Permutations & Combinations
A classroom has 30 students and 30 desks arranged in a rectangular grid pattern. How many ways can the teacher assign the students to the desks?
This is fundamentally a question about how to arrange the students. Since it's a question about how the students will be arranged, we will use permutations.
At first, this might be a little confusing. We use permutations to see how many ways there are to arrange objects in a line. But for this problem, we're arranging the "objects" (the students) in a rectangular grid. So how can we treat them as if we're simply arranging them in a line?
We can do this because we can arbitrarily designate place numbers to each desk. For example, we call the top-left desk #1, then the next to the right #2, and so on. Thus, even though the arrangement is actually in a rectangular grid, we can treat it as if it were just a linear arrangement of #1 up to #30. Arranging the students in a line then having them sit down according to their number is equivalent to directly assigning them to the desk.
From the lesson, we saw that for n objects, there are n! ways of arranging them. Thus, since we have 30 students that we are going to arrange, we have 30! ways of arranging them.
Remember, 30! is read as "30 factorial", where a factorial is the number written multiplied by the number one less, then the next number one less, and so on up until 1:
30! = 30 ·29 ·28 ·27 ·26 ·25 ·…·3 ·2 ·1
Most calculators will have some way to directly calculate factorials: either a `!' button or some entry in a menu somewhere that allows you to compute the factorial. [If you don't see a `!' button, try looking under a menu called something like "probability", "counting", or "combinatorics".] That way you don't have to enter in all those multiplications by hand.
30! ≈ 2.65 ·1032
You are the lead engineer at a factory that is building a product. To assemble the product, ten different processes must occur, but each process can be done in any order. Assembling the product in certain orders causes it to be built faster, while other orders causes it be built slower. There exists some optimal order to build the product which allows it to be built the fastest and cause the factory to make the most units per day. The problem is that this optimal order is currently unknown.
Someone in upper management decides that this optimal order must be found, and that every single possible order to assemble the product will be tested. Once every order has been tried out, the best one will be chosen and used from then on.
As the lead engineer, it is your job to supervise this testing. It will take one hour to test each possible order. As soon as you are given this job, you know it is a bad idea. You know this because it will take an absurdly long time to complete the testing process. How long will it take?
The hardest part about this problem is the amount of reading involved. If you found it easy to understand, great! Skip on to the next step.
However, if you got confused, focus on the things you need to know to do the problem. Skim through the problem and catch the important stuff. We see A) there is something that can be done in multiple orders, B) it is made up of ten steps that can be rearranged, and C) trying a new order takes one hour of time. Finally, the question asks us how long it will take to try each order. If we know those three bits of information (A, B, and C), we know enough to do the problem.
If you regularly have difficulty with long word problems like this, approach them the same way you would approach a tough reading passage. Read through it and start by figuring out what the question is. Once you know what you're being asked, read through it again and look for specific information that might connect to answering that question. Underline those pieces of info or write a short note for each one. Once you've found all the info, then start setting up the math.
We want to find out how long it will take to test each possible order, so we start by figuring out how many possible orders there are. The problem says there are 10 processes that can be rearranged in any way, so the number of orders is all the possible ways to rearrange 10 things:
10! = 3 628 800
Next, the problem said testing each ordering takes an hour. Thus it will take
10! = 3 628 800 hours
to test out each possible order. Of course, that's a really big number, so it's hard to get a sense for how much time that is. Let's convert it into a more comfortable unit:
3 628 800
= 151 200 days
That's still a big number, so let's convert it into years:
≈ 414 years
Wow! No wonder it is such a bad idea to test every single order!
[This problem goes to show why working something out by brute force is often a bad idea. Solving by brute force means trying every single possible way of doing something until you stumble on the answer. For some things, this works alright. But when there are even a reasonable number of different combinations, it quickly becomes very time-consuming to use brute force.
In this problem, upper management wanted to find the optimal order by brute force: try every possibility. But if you understand how counting works, you realize that trying every single order for even ten objects will wind up taking a long time! It's just not a good idea.]
10! hours = 3 628 800 hours ≈ 414 years
Simplify the below ratio of factorials.
While it would be possible to use a calculator to find 47!, then divide that by 45! with a calculator, it's actually easier to start off by hand.
Remember, a factorial (shown by the `!' symbol) is the number multiplied by the number below, then the number below, and so on until you get down to 1. For example,
47! = 47 ·46 ·45 ·44 ·…·2 ·1
Try expanding both the top and bottom of the fraction in this manner to help you see what's going on.
Expanding the top and bottom factorials, we see we have
47 ·46 ·45 ·44 ·…·2 ·1
45 ·44 ·43 ·42 ·…·2 ·1
Notice that the top has every number from 45 down to 1 multiplied together, which is exactly what the bottom is. Thus, we can cancel the factors that appear on the top and bottom to simplify to
47 ·46 = 2162
47 ·46 = 2162
Simplify the below ratio of factorials.
This time it's impossible to simplify the expression using a calculator because there's a variable. Instead, we need to rely on the definition of a factorial. Remember, a factorial is a number multiplied by itself, then the next number down, then the next, and so on until 1. For example,
5! = 5 ·4 ·3 ·2 ·1
Notice that all we're doing each time is taking the number and subtracting 1. Thus we can do this for variables as well. For example,
n! = n ·(n−1) ·(n−2) ·(n−3) ·…·2 ·1
Furthermore, notice that we can wrap up the "tail" of any of these into a factorial from a different starting place. Two examples below:
5! = 5 ·4 ·3 ·2 ·1 = 5 ·
4 ·3 ·2 ·1
= 5 ·4!
n! = n ·(n−1) ·(n−2) ·(n−3) ·…·2 ·1 = n ·(n−1) ·(n−2)!
These two examples show that we can "pull out" numbers from the "top" of a factorial, but still leave a factorial (although now starting at a lower value).
We can apply this to our problem: pull out (3x+1) and (3x) from the factorial at the top of the fraction:
(3x+1) ·(3x) ·(3x−1)!
At this point, we now have (3x−1)! on both the top and bottom of the fraction, so we can cancel them out to get
(3x+1) ·(3x) = 9x2 + 3x
9x2 + 3x
In a marathon of 100 competitors, the first five people to finish the race will all win prize money. First will win the most money, second wins less, and so on until fifth wins the least money of all five positions.
How many different ways are there for the competitors to place in first through fifth?
We care about the order that the competitors come in, but we're only interested in looking at the first 5 places.
From the lesson, we know that nPr gives all the ways to order r objects out of a group of n objects. We calculate this as
For this problem, we're interested in all the ways to order five objects (the runners who place in the first five spots) out of a group of 100 objects (all the runners in the marathon).
With this in mind, we see we want to know 100P5: all the ways to order 5 things from a selection of 100.
By the way that factorial works, we can "pull out" the top numbers and have a factorial that starts at a lower value:
100 ·99 ·98 ·97 ·96 ·95!
= 100 ·99 ·98 ·97 ·96
[Notice that this makes a lot of sense: we could also see this as the number of ways to select first, multiplied by the number of ways to then select second, and so on until fifth place.]
100 ·99 ·98 ·97 ·96 = 9 034 502 400
There are two bags containing the 26 letters of the alphabet. In the first bag, the first 13 letters (A-M) are contained, each letter on a single tile. In the second bag are the other 13 letters (N-Z), each letter on a single tile.
Three letters are pulled out of the first bag, one at a time, and placed down in the order they are pulled out. Then two letters are pulled from the second bag, and placed in the order they are pulled out, but put after the first three letters already placed down. This creates a five letter "word" (it will probably be nonsense, but we'll call it a word anyway).
How many distinct words could be created in this fashion?
Begin by noticing that the order the tiles are pulled out of each bag will affect the "word" that is ultimately produced. We care about the order of the tiles that come out of each bag.
Since we care about the order that the tiles are pulled in, this is based on a permutation. For the first bag, 3 tiles are pulled out of a total of 13 tiles, so we have
Similarly for the second bag, the only difference is that now 2 tiles are pulled out:
Finally, notice that if we get a different pull from either of the bags, the "word" will wind up different as well. Thus we care about the outcome from each bag. Furthermore, since what we pull from the first bag has no effect on the second bag, we can use the multiplication principle (from the previous lesson) to find the total number of ways:
(13P3) ·(13P2) =
Simplify to find the value:
13 ·12 ·11 ·10!
= 13 ·12 ·11 ·13 ·12
(13 ·12 ·11) ·(13 ·12) = 267 696
How many distinguishable ways are there to arrange the below letters?
At first glance, we might try counting up the number of letters in the word (9), then guess that it would be equal to the number of ways we could arrange that many objects (9!).
However!, this misses the fact that each letter is indistinguishable from all the other letters of the same type. For example, if we leave everything else alone but swap the location of the first `S' and the second `S', we haven't created a new, distinguishable arrangement of the letters. We have to take into account the fact that some of the objects are exact copies of the others.
Work toward this by first counting up each type of object:
S: 4, A: 3, F: 1, R: 1
Also note what the total number of objects on the whole is:
To find all the distinguishable arrangements for some group of objects, begin by finding all the possible permutations for the total number, then, for each object type, divide it by the permutations for things in that type.
For this problem, we have 9 total objects, so we have a 9! on the top of the fraction. Below that, we will divide it by the permutations possible amongst each object. For example, since `S' has 4 letters, it has 4! permutations.
4!·3! ·1! ·1!
[The above makes sense by the following logic: we begin by figuring out the possible ways to arrange all of the letters. But since we don't care about the order for each letter type, we divide out all the ways to arrange each specific type of letter. Thus we're left with the arrangements that are actually distinguishable from one another.]
4!·3! ·1! ·1!
9 ·8 ·7 ·6 ·5 ·4!
4! ·(3·2 ·1)
Cancel out and continue to simplify:
9 ·8 ·7 ·6 ·5
= 9 ·8 ·7 ·5 = 2520
At a certain school, some of the senior students are elected to a student governance committee. If there are 247 seniors at the school and five spots on the committee, how many different committees can be created?
Notice that a committee is only different from another committee if one or more of the members are different. Unlike previous problems where we've cared about the order of things, we have no interest in the order of the election: we are only interested in who makes it on to the committee.
When we are looking for the number of ways to choose objects out of a collection and have no interest in the order, we are talking about a combination. If we want to know the number of ways that r objects can be chosen from a set of n (and we have no interest in the order), that is
[You will often also see nCr written as \binomnr. Both are common, and some teachers prefer one to the other.]
Thus, we want to know the total number of ways that 5 students can be selected from a group of 247:
Simplify from there:
247 ·246 ·245 ·244 ·243
Which we can then use a calculator to find the value of, obtaining
7 355 513 529
[Alternatively, most graphing calculators have a menu dedicated to probability and counting, where you can find a combination function. It might appear as nCr or something else. Once you know the appropriate function to use, just use the calculator to find the value.]
7 355 513 529
Fifteen friends are going to a concert. Three of those fifteen friends own cars that everybody will ride in. Each person who owns a car will be driving that car and each car has precisely five seats.
How many ways can the friends divide themselves amongst the three cars for the trip? (Assume that we don't care which seat each passenger gets, just which car they are in.)
Begin by noticing that this question does not care about ordering and specific placement, simply how the people will be grouped together. That means this question is based around combinations.
The drivers have no effect on the selection. Each driver is already locked to their car, so they don't take part in the process of figuring out who goes where. That means that we only have to consider how 12 of the friends (the non-drivers) are divided up amongst the three cars.
Furthermore, since each car already has a driver in it, that means each car can only seat four passengers.
Arbitrarily assign statuses of "first car", "second car", and "third car" to the three cars so we can start figuring out who goes where. Working on the "first car", we have 12 friends to select from, and four seats. Thus we have
Next, for the second car, there are only 8 friends left for selection so we have
Finally, that leaves us with the last car, but at this point we only have 4 friends left, so there's only 1 possible way to select the passengers:
#ofwaystoassignpassengerstothirdcar:4C4 = 1
We're not quite done yet, though. We now need to figure out the total number of ways over all three cars. Notice that no matter how the first four passengers are selected, we will still have the same number of options for selecting the next four. While the specific people involved will change, the numbers of choices are unaffected.
Thus, since the number of choices does not change based on each selection event, we can use the multiplication principle from the previous lesson. Multiply each of the possible ways from each step to figure out the total possible number of ways:
(12C4) ·(8C4) ·(4C4) =
Simplify from there (and remember, 0! is defined to equal 1):
12 ·11 ·10 ·9 ·8 ·7 ·6 ·5
Finish simplifying and then use a calculator to get 34 650.
A classroom has 25 students and 30 desks arranged in a rectangular grid pattern. How many ways can the teacher assign the students to the desks?
Notice that this problem is very similar to the first problem given in this section, but with a significant difference. While the number of desks is still 30, the number of students is different at 25. This means we have to approach the problem differently.
In this problem we need to not just figure out how the students are arranged, but also figure out which desks will be used.
One way to approach this problem is to break it into two steps: first consider all the ways of choosing which desks will be used (30C25), then find all the ways to arrange the students upon the 25 desks that will be used (25!). Since these two decisions do not numerically affect each other, we multiply them together to find the total number of ways:
From there, simplify to find the answer:
At this point we've found the total number of ways and we're done. However, there is also an alternative way to approach the problem...
Instead of thinking about assigning students to desks, we can think of assigning desks to students. If we imagine the students lining up, we then match desks to them based on their location in that line. Thus, we care about the order of the desks we select, so we use permutation. Furthermore, since we're only using 25 out of the 30 desks, that gives us 30P25. Expanding that, we have
Notice that this gives the exact same result as the above method, which is good, because the two methods double-check each other.
*These practice questions are only helpful when you work on them offline on a piece of paper and then use the solution steps function to check your answer.
Permutations & Combinations
Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.