Applicable Mathematics/Counting Techniques

Factorials

A factorial, symbolized by n! with n being a number between 1 and infinite, is a product of consecutive counting numbers starting at 1 and ending at n. The number 0 is an exception. 0! has a value of 1. Factorials are used in many ways, from their use in equations to solving word problems. Their most useful application is through the calculation of the number of outcomes of an event. For example, it can produce the possible outcomes of the race, and how many combinations of first, second, third, and so forth of the racers.

n Factorial

For any whole number n, it's factorial is the product of the natural numbers that are less than or equal to it. For example:

7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040

The algebra behind factorials looks like this:

n! = n x (n-1) x (n-2) x (n-3) x ... x 1

Permutations

Permutations is all the possible outcomes of a given value. For example, if you were given three colors (red [r], green [g], and yellow [y]) and were asked to find possible arrangements of them, you would find 6 possible arrangements: rgy, ryg, gyr, gry, yrg, ygr.

In a permutation, the order of the objects in the group is important. Using the same example above, we are given three different colors (red [r], green [g], and yellow [y]). If we were just given red [r], then there would be only one way to arrange it: red. However, when green [g] is thrown in the mix, there are now two ways to arrange these two colors: rg or gr. And now, when a third color is thrown in (yellow [y]), then there are now six possible outcomes, as stated above. The amount of permutations of the 3 colors is equal to 3 x 2 x 1, which equals 6. This is also equal to the factorial of 3:

3! = 3 x 2 x 1 = 6

The general formula for a permutation of n items is:

n x (n - 1) x (n - 2) x (n - 3) x ... x 1

As mentioned above, this is also called the n factorial, and is written like this:

n!

But, what if you don't want to order the whole set of things? Let's say that you need to select an order of 3 things from a group of 8. The Fundamental Counting Principle is one way to do just that.

First Thing: 8 possibilities

Second Thing: 7 possibilities

Third Thing: 6 possibilities

The number of permutations in this example is 336. In other words, there are 8 things, and we are choosing 3 of them in order. The 336 comes from the 8 possibilities x 7 possibilities x 6 possibilities.

Factorials, as stated above, can also be used to find permutations. The number of arrangements can be divided by the number of arrangements not used. Using the example above, there are 8 things, 3 arrangements of which do not matter. For large numbers of objects, it is useful to use this generalized formula:

_nP_r = n! / (n-r)!

This algebra, stated in words, reads like this: the number of permutations of n items taken r at a time is ___ .

So, in the example used above, 8 things taken 3 at a time would give us:

₈P₃ = 8! / (8-3)! = 8! / 5! = 336

Permutation Examples

1. How many ways could all the students in a high school vote for the homecoming king and queen from a group of 6 people?

In other words, this question is asking us to select and arrange 2 things from 6 things. So, first thing to do isd to substitute 6 in for n in our _nP_r formula and 2 in for r:

₆P₂ = 6! / (6-2)! = 6! / 4! = (6 x 5 x 4 x 3 x 2 x 1) / (4 x 3 x 2 x 1) = 6 x 5 = 30

So, there are 30 ways to vote for the homecoming king and queen.

2. You have 10 picture frames to hang on your bedroom wall; however, you only have enough space for 5 frames. How many ways can you hang any 5 picture frames on your wall?

₁₀P₅ = 10! / (10-5)! = 10! / 5! = (10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) / (5 x 4 x 3 x 2 x 1) = 10 x 9 x 8 x 7 x 6 = 30,240

So, there are 30,240 ways that you can pick the pictures you want to hang on your wall.

If you notice, in the above two examples, the number of things selected is equal to the number of factors left after dividing the two factorials. For instance, in example 1, there were 2 people we were voting for and, thus, 2 factors that were left after dividing the factorials: 6 x 5.

Combination

When items are grouped and the order in which they are grouped doesn't matter, this is known as a combination. Normally, when order doesn't matter, there are less ways to choose things. Let's say we have 4 different letters: A, B, C, and D. There are 24 different ways to put these 4 letters in order (permutation). However, they are all the same combination for letters.

24 permutations: ABCD, ACDB, ADBC, ACBD, ADCB, ABDC, BACD, BADC, BDCA, BDAC, BCAD, BCDA, CDAB, CDBA, CBAD, CBDA, CABD, CADB, DABC, DACB, DBCA, DBAC, DCAB, DCBA

1 combination: ABCD

The formula previously used for permutations can be changed and used to find the number of combinations:

(ways to arrange all of items) / (ways to arrange items not selected) = number of permutations

To change this formula to find the number of combinations, the number of permutations will be divided by the number of ways to arrange the items selected. This is due to the fact that in combinations, order does not matter.

(ways to arrange all of items) / (ways to arrange items selected) x (ways to arrange items not selected) = number of combinations

So, the algebraic formula for finding combinations of n items taken r at a time is:

_nC_r = n! / r! x (n - r)!

For example, the number of combinations of 8 items taken 4 at a time is:

₈C₄ = 8! / 4!(8-4)! = 70

So, how do you know whether or not to use a permutation versus a combination. The first thing you need to figure out is whether or not order matters. If it does, then permutations are needed to solve the problem. However, if order does not matter, then combination is the method to be used.

Combination Examples

1. Lauren wants to buy 4 puppies for her farm. The puppy store has 12 puppies to choose from. How many ways can she choose 4 puppies?

The first thing to do is decide whether to use the formula for permutation of combination to solve the problem. Since order is not an issue, the combination method is to be used.

The combination method looks like this:

₁₂C₄ = 12! / 4!(12-4)! = 12! / 4!(8!)

= (12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1) / (4 x 3 x 2 x 1)(8 x 7 x 6 x 5 x 4 x 3 x 2 x 1)

= (12 x 11 x 10 x 9) / (4 x 3 x 2 x 1) = 495

So, there are 495 different ways to choose 4 puppies from a given 12 puppies.