3.2 - Permutations

3.2 - Permutations

Example 3-4

How many ways can four people fill four executive positions?

Answer

For the sake of concreteness, let's name the four people Tom, Rick, Harry, and Mary, and the four executive positions President, Vice President, Treasurer and Secretary. I think you'll agree that the Multiplication Principle yields a straightforward solution to this problem. If we fill the President position first, there are 4 possible people (Tom, Rick, Harry, and Mary). Let's suppose Mary is named the President. Then, since Mary can't fill more than one position at a time, when we fill the Vice President position, there are only 3 possible people (Tom, Rick, and Harry). If Tom is named the Vice President, when we fill the Treasurer position, there are only 2 possible people (Rick and Harry). Finally, if Rick is named Treasurer, when we fill the Secretary position, there is only 1 possible person (Harry). Putting all of this together, the Multiplication Principle tells us that there are:

\(4\times 3\times 2\times 1\)

or 24 possible ways to fill the four positions.

Alright, alright now... enough of these kinds of examples, eh?! The main point of this example is not to see yet another application of the Multiplication Principle, but rather to introduce the counting of the number of permutations as a generalization of the Multiplication Principle.

A Generalization of the Multiplication Principle

Suppose there are \(n\) positions to be filled with \(n\) different objects, in which there are:

  • \(n\) choices for the 1st position
  • \(n-1\) choices for the 2nd position
  • \(n-2\) choices for the 3rd position
  • ... and ...
  • 1 choice for the last position

The Multiplication Principle tells us there are then in general:

\(n\times (n-1)\times (n-2)\times \ldots \times 1=n!\)

ways of filling the \(n\) positions. The symbol \(n!\) is read as "\(n\) -factorial," and by definition 0! equals 1.

Permutation of \(n\) objects
an ordered arrangement of the \(n\) objects

We often call such a permutation a “permutation of \(n\) objects taken \(n\) at a time,” and denote it as \(_nP_n\). That is:

\(_nP_n=n\times (n-1)\times (n-2) \times \ldots \times 1=n!\)

Not that it really matters in this situation (since they are the same), but the first subscripted \(n\) represents the number of objects you are wanting to arrange, while the second subscripted \(n\) represents the number of positions you have for the objects to fill.

Example 3-5

plastic toy soldiers

The draft lottery of 1969 for military service ranked all 366 days (Jan 1, Jan 2, ..., Feb 29, ..., Dec 31) of the year. The men who were eligible for service whose birthday was selected first were the first to be drafted. Those whose birthday was selected second were the second to be drafted. And so on. How many possible ways can the 366 days be ranked?

Answer

Well, we have 366 objects (days) and 366 positions (1st spot, 2nd spot, ... , 366th spot) to arrange them. Therefore, there are 366! ("366 factorial" ) ways of ranking the 366 possible birthdays of the eligible men.

What is the probability that your birthday would be ranked first?

The answer, which is 1/366 = 0.0027, can be determined in (at least) two ways.

The simplest way is to recognize that there is only one birthday (yours!) in the event of interest, and that there are 366 birthdays in the sample space. Therefore, the classical approach to assigning probability tells us the probability is 1 divided by 366.

A second way is to recognize that there are 366! ways of ranking the 366 birthdays, and that there are 365! ways of ranking the 366 birthdays to ensure that your birthday is ranked first. Again, the classical approach to assigning probability tells us the probability is 365! divided by 366!, which after simplification is 1/366.

Example 3-6

seven books on a bookshelf

In how many ways can 7 different books be arranged on a shelf?

Answer

We could use the Multiplication Principle to solve this problem. We have seven positions that we can fill with seven books. There are 7 possible books for the first position, 6 possible books for the second position, five possible books for the third position, and so on. The Multiplication Principle tells us therefore that the books can be arranged in:

\(7\times 6\times 5\times 4\times 3\times 2\times 1\)

or 5,040 ways. Alternatively, we can use the simple rule for counting permutations. That is, the number of ways to arrange 7 distinct objects is simply \(_7P_7=7!=5040\).

Example 3-7

With 6 names in a bag, randomly select a name. How many ways can the 6 names be assigned to 6 job assignments? If we assume that each person can only be assigned to one job, then we must select (or sample) the names without replacement. That is, once we select a name, it is set aside and not returned to the bag.

Sampling without replacement
occurs when an object is not replaced after it has been selected

Answer

If we sample without replacement, the problem reduces to simply determining the number of ways the 6 names can be arranged. We have 6 objects taken 6 at a time, and hence the number of ways is 6! = 720 possible job assignments. In this case, each person is assigned to one and only one job.

What if the 6 names were sampled with replacement? That is, once we select a name, it is returned to the bag.

Sampling with replacement
occurs when an object is selected and then replaced before the next object has been selected

Answer

If we sample with replacement, we have 6 choices for each of the 6 jobs. Applying the Multiplication Principle, there are:

\(6\times 6\times 6\times 6\times 6\times 6=46656\)

possible job assignments. In this case, each person is allowed to perform more than one job. There's even the possibility that one (rather unlucky) person gets assigned to all six jobs!

The take-home message from this example is that you'll always want to ask yourself whether or not the problem involves sampling with or without replacement. Incidentally, it's not all that different from asking yourself whether or not replication is allowed. Right?

Example 3-8

three chairs

Okay, let's throw a (small) wrench into our work. How many ways can 4 people fill 3 chairs?

Answer

Again, for the sake of concreteness, let's name the four people Tom, Rick, Harry, and Mary and the chairs Left, Middle, and Right. If we fill the Left chair first, there are 4 possible people (Tom, Rick, Harry, and Mary). Let's suppose Tom is selected for the Left chair. Then, since Tom can't sit in more than one chair at a time when we fill the Middle chair, there are only 3 possible people (Rick, Harry, and Mary). If Rick is selected for the Middle chair, when we fill the Right chair, there are only 2 possible people (Harry and Mary). Putting all of this together, the Multiplication Principle tells us that there are:

\(4\times 3\times 2\)

or 24 possible ways to fill the three chairs.

Okay, okay! The main distinction between this example and the first example on this page is that the first example involves arranging all 4 people, whereas this example involves leaving one person out and arranging just 3 of the 4 people. This example allows us to introduce another generalization of the Multiplication Principle, namely the counting of the number of permutations of \(n\) objects taken \(r\) at a time, where \(r\le n\).

Another Generalization of the Multiplication Principle

Suppose there are \(r\) positions to be filled with \(n\) different objects, in which there are:

  • \(n\) choices for the 1st position
  • \(n-1\) choices for the 2nd position
  • \(n-2\) choices for the 3rd position
  • ... and ...
  • \(n-(r-1)\) choices for the last position

The Multiplication Principle tells us there are in general:

\(n\times (n-1)\times (n-2)\times \ldots \times [n-(r-1)]\)

ways of filling the \(r\) positions. We can easily show that, in general, this quantity equals:

\(\dfrac{n!}{(n-r)!}\)

Here's how it works:

And, formally:

Permutation of \(n\) objects taken \(r\) at a time
ordered arrangement of \(n\) different objects in \(r\) positions. The number of such permutations is:

\(_nP_r=\dfrac{n!}{(n-r)!}\)

The subscripted \(n\) represents the number of objects you are wanting to arrange, while the subscripted \(r\) represents the number of positions you have for the objects to fill.

Example 3-9

An artist has 9 paintings. How many ways can he hang 4 paintings side-by-side on a gallery wall?


Legend
[1]Link
Has Tooltip/Popover
 Toggleable Visibility