Permutations/Combinations

For today, I will answer the questions from yesterday’s post. But before I do that, I will need to present some mathematical concepts.

The first concept is a simple one. It is the Multiplication Principle. Let’s say there are five apples on a table. How many ways is it possible for me to choose three apples? Well, for my first apple, I have five choices. For my second, I now have four, since I took one away for my first apple. For my third, I am left with three choices. Thus, I multiply 5x4x3 to get the total possibilities of choosing three apples. In textbook terms,  when listing out all the possibilities for k items, the total number of entries in this list is given by n1 ⋅n2⋅n3 ⋅ ⋅ ⋅ nk , where nk is the number of possibilities for the kth item. For example, n3 is the number of possibilities for the third item.

Another important concept is the factorial, symbolized by “!” A factorial is the product of all whole numbers starting from the number indicated all the way down to 1. For example, 5! or five factorial is 5x4x3x2x1, as 3! is 3x2x1.

So what is a permutation? A permutation is an arrangement of objects from a group where no object can be used more than once and the order of selection matters. For example, let’s say I have to make a 5-letter code without replacement (meaning I can’t use a letter more than once). Using the Multiplication Principle, I have a total of 26x25x24x23x22 choices. This is a permutation because no letter can be used more than once, and the order of selection matters because placing a letter Z as the first letter is different from placing the letter Z as the last letter. You will see this type of situation happening a lot and there is a formula for it. It states that the total number of permutations P of k objects from a group containing n objects is given by the formula

I can derive this formula, but since this is a blog post, I will not do so. Perhaps for a later time.

We of course need to know what combinations are. Combinations are arrangements of objects from a group where no object can be used more than once and the order of selection does not matter. One example would be choosing four candidates out of ten for a committee. Say the four candidates were Joe, Moe, Steve, and Larry. First, one candidate cannot be selected for a position more than once. Second, it wouldn’t matter if the order was Joe, Moe, Steve, and Larry or Moe, Steve, Joe and Larry or any other order. It is still the same committee, and thus the order of selection does not matter. By definition, this is a combination. Just like permutation, there is also a combinations formula. The total combinations C of k objects from a group containing n objects is given by the formula

Figure 2. Combinations formula

 Notice the middle part of the formula above, which has a parentheses  This is a notation for combinations and is read as “n choose k.”

I gave you the concepts; now let’s used them to solve our questions. The first question being:

At the beginning of math class every day, Mr. Smith selects students to write up homework problems on the board. These problems can be discussed as a class. There are 26 students in Mr. Smith’s math class, and he randomly selects with replacement a student to write up each of the first five problems. How many different ways can students be assigned to the problems?

Note that permutations and combinations occur without replacement. In this case it is not, so none of these situations occur. So what do we use? The Multiplication Principle, that is. To select the first student, Mr. Smith has 26 choices since he has 26 students. For the 2nd, he also has 26 choices because of the words “with replacement.” He also has 26 choices for the 3rd, 4th, and 5th students. Therefore, the equation is 26x26x26x26x26 or 26^5, which equals 11881376 different ways.

First question solved. Just remember that when permutations or combinations can’t be applied, always start off with the Multiplication Principle. Now onto the second question:

A regular polygon is a polygon with equal angle measures and equal side lengths. A diagonal of a polygon connects two non-adjacent vertices. How many diagonals are there in a regular heptadecagon (17-sided polygon)?

Instead of taking this in terms of geometry, let us take it in terms of what we are learning. Since there are 17 angles, let each angle be A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, and Q. A diagonal is connecting two non-adjacent angles, so we are trying to find all the possible ways two angles can be selected. Notice that this is a combination, because no pair can be made more than once and that order of selection also doesn’t matter, since AC and CA are the same diagonal. Now, in order to use the combination formula, we first have to know what n and k is. N is the total no. of objects, which in this case is 17 angles. K is how much we select from these 17 angles, which in this case is 2, because two angles make up a diagonal. So let’s plug it in.

17!/(17-2)!2!=(17*16)/2=136

 Wala! The answer is 136. Just kidding. It is in fact not. Why? Because we forgot to take into account that this only works when each angle has 16 diagonals, or in other words, when any two angles can form a “diagonal”. However, this is restricted by the fact that diagonals are only formed by non-adjacent angles. Meaning only each angle has 14 diagonals, in fact. So what do we do in this case? Well, we don’t want those “diagonals” formed between adjacent angles, so why not subtract them. Note that these “diagonals” are in fact the sides of the polygon. Using this fact, we do the equation 136-17 which equals 119 diagonals in a heptadecagon. (If you don’t get this, contact me on what you don’t understand.)

Now, the last question: George is traveling to New York City and has created a list of ten different possible sightseeing activities in which he is interested. He will be in New York City for three days, but will only have time for two different activities each day. How many different sightseeing plans can George create? (Assume each day is treated separately, and clearly George will not want to complete each activity more than once.)

The first thing to notice is that this is a permutation, because one activity cannot be done more than once, and whether Activity Y is the first on the agenda or second can result in different plans, and thus order of selection matters. Now, we must know what n and k is. N in this case is the total no. of events, which is 10. However, George can choose only 6 events, with 2 events/day for 3 days. So, let’s plug n and k into the permutations formula:

10!/(10-6)!= 151200

 Therefore, there are 151,200 different possible sightseeing plans.

Well, this is just a basic overview over permutation/combinations. To see more in-depth, I advise you to continue researching on this amazingly complex subject. Somewhere soon into the future, we will step off of what we learned today and begin to learn about series.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s