Last weekend my dad asked me about my blog, and the last entry was about factorials of large numbers. Clicking on this link will take you there. On our way to classic car auto shop in Orange, CA; my dad and I talked about the factorials as I tried to come up with a way of finding applications using factorials. Last weekend became the inspiration for my blog entry. Love you, Dad.
Note: This blog entry will cover factorials of non-zero integers, that is n = 0, 1, 2, 3...
Factorials
The factorial of a non-negative integer, written with an exclamation mark after the number, is defined as:
n! = n × (n - 1) × (n - 2) × (n - 3) × ... × 3 × 2 × 1
Start by multiplying n by n less 1, then multiplying the product by n less 2, and repeat until you get to 1.
Examples
5! = 5 × 4 × 3 × 2 × 1 = 120
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320
What about 0! ?
By definition, 0! = 1. Dr. James Tanton, Ph. D (www.jamestaton.com) gives an explanation why mathematicians choose to in video: Link to Video
Simply put, 0! = 1 is just defined this way.
Arrangements
In this section, we consider three common arrangement problems. The task is to find the number of possible permutations a group of objects can be arranged. A permutation is an arrangement where the order of which the objects are placed is important.
In this section, we are going to arrange all the objects.
Arrangement of Unique Objects
Consider a bookshelf that has room for five books. For simplicity, let's call the books A, B, C, D, and E (and not "Combinatorics", "The Irrationals", "Euclid's Number", "Programming", and "Making Soup for Dummies" like I originally planned.)
The for the first slot there are five choices. The second slot provides four choices. Whatever is available for the second slot depends on what book was put in the first slot. For example, if I choose to put book A in the first slot, the books B, C, D, and E are available for the second slot. Instead, if I choose to put book C in the first slot, then A, B, D, and E are available.
For each choice I make on the first slot, I get four choices for the second. Considering the first two slots alone, this gives me a total of 5 × 4 = 20 arrangements.
Continuing in this way, there are three choices for the third slot, two choices for the fourth slot, and whatever is left over gets the fifth slot.
So, the total number of arrangements of five books is:
5 × 4 × 3 × 2 × 1 = 5! = 120
Yes, 120 different arrangements. Since order is important, the arrangement is considered a permutation.
In general, working with n objects and n slots:
There are n objects for the first slot,
there are n - 1 objects for the second slot,
there are n - 2 objects for the third slot,
and so on,
until we reach 1 slot left for the last object.
Hence, the number of arrangements are:
n × (n - 1) × (n - 2) × ... × 1 = n!
Number of Permutations of n Unique Objects = n!
Arrangement of Unique Slots, Limited Spaces Available
Let's go back to our problem of arranging five books (A, B, C, D, and E) but this time, we only have three slots available.
For the first slot, I have 5 books available to choose from. Depending on what I choose, I will have 4 books for the second slot. Each of those 4 books present a choice of the 3 books for the last slot. Whatever is left either goes somewhere else in the house or gets donated.
The number of arrangements that are available to me has decreased due to the fact I only have three slots available. Hence, 5 × 4 × 3 = 60.
Observe if we multiply 5 × 4 × 3 by (2 × 1)/(2 × 1) we get:
5 × 4 × 3
= (5 × 4 × 3 × 2 × 1) / (2 × 1)
= 5! / (2 × 1)
= 5! / (5 - 3)!
Basically we are taking all of the ways 5 books can be arranged, and then dividing that number by all the ways the 2 books that are not going to be used can be arranged.
Doing the above in the general case is how we arrive at the formula for permutations:
nPk = n! / (n - k)!
where we have n objects and k slots to fill.
Permutations: nPk = n! / (n - k)! where n ≥ k. Order is important.
Until next time, have a great day!
Eddie
This blog is property of Edward Shore, 2012.
Tuesday, October 23, 2012
Factorials and Arrangements of Unique Objects
