Permutations

Section 3.3 Permutations

When counting various outcomes the order of things sometimes matters. When the order of a set of elements changes we call the second a permutation (or an arrangement) of the first.

🔗

Theorem 3.3.1. Permutations of everything.

🔗

The number of permutations of n distinct items is n!

🔗

Proof.

Notice that if n=1, then there is only 1 item to arrange and that there is only one possible arrangment.

By induction, assume that any set with n elements has n! arrangments and assume that

\begin{matrix} A = {a_{1}, a_{2}, . . ., a_{n}, a_{n + 1}} . \end{matrix}

Notice that there are n+1 ways to choose 1 element from A and that in doing so leaves a set with n elements. Combining the induction hypothesis with the multiplication principle this gives (n+1)n! = (n+1)! possible outcomes.

🔗

One can interpret successive ordered selections as branching through a "tree" structure. Indeed, starting with the set {A,B,C} one may pick any of the three but then a subsequent selection only has two possibilities for the next selection and so forth. The tree below illustrates that there are six ways to order two items from a group of size three.

🔗

Going one step further, what about ordering the letters in {A, B, C, D}? You can start by picking one of the four letters, say A, and then arranging B, C, and D. Then, start with B and arrange A, C, and D and so on. This gives:

🔗

ABCD, ABDC, ACBD, ACDB, ADBC, ADCB

🔗

BACD, BADC, BCAD, BCAB, BDAC, BDCA

🔗

CBAD, CBDA, CABD, CADB, CDBA, CDAB

🔗

DBCA, DBAC, DCBA, DCAB, DABC, DACB

🔗

which is 24 different options or

4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 .

This can be viewed using a tree structure where each decision creates a new branch.

🔗

Theorem 3.3.2. Permutations of a subset without replacement.

🔗

The number of ways to arrange r items from a set of n distinct items is

_{n} P_{r} = \frac{n!}{(n - r)!}

🔗

This is sometimes denoted also as P(n,r) or

P_{r}^{n} .

🔗

Proof.

r > n

r < 0

then this is not possible and so the result would be no permuatations. Otherwise, apply the multiplication principle r times noting that there are n choices for the first selection, n-1 choices for the second selection, and with n-r+1 choices for the rth selection. This gives

\begin{aligned} _{n} P_{r} & = n (n - 1) . . . (n - r + 1) \\ = n (n - 1) . . . (n - r + 1) \frac{(n - r)!}{(n - r)!} \\ = \frac{n (n - 1) . . . (n - r + 1) (n - r)!}{(n - r)!} \\ = \frac{n!}{(n - r)!} \end{aligned}

🔗

Following the tree idea from above, continue for several steps but then stop once you have gone r steps in. For example, it is easy to see that

_{5} P_{2} = 20

using a tree.

🔗

Checkpoint 3.3.3. WebWork - Permutations.

In how many ways can 4 different novels, 2 different mathematics books, and 1 biology book be arranged on a bookshelf if

(a) the books can be arranged in any order?

Answer:

(b) the mathematics books must be together and the novels must be together?

Answer:

Answer 1.

5040

Answer 2.

288

Answer 3.

576

🔗

Theorem 3.3.4. Permutations of a subset with replacement.

🔗

The number of ways to obtain an arrangement of r choices from a group of size n is

n^{r}

🔗

Proof.

Use the multiplication principle r times and see that for each choice all n objects in the universe remain available. That is,

n \cdot n \cdot n . . . n = n^{r}

🔗

Theorem 3.3.5. Permutations when not all items are distinguishable (Multinomial Coefficients).

🔗

If n items belong to s categories,

n_{1}

in first,

n_{2}

in second, ... ,

n_{s}

in the last, the number of ways to pick all is

\frac{n!}{n_{1}! \cdot n_{2}! . . . n_{s}!}

🔗

Proof.

Enumerate all of the n data items individually with the

n_{1}!

identical values first and the remaining groups in like manner to get the enumerated list

{x_{1, 1}, . . ., x_{1, n_{1}}, x_{2, 1}, . . ., x_{2, n_{2}}, . . ., x_{s, 1}, . . ., x_{s, n_{s}}}

In this order, there are

n_{1}!

ways to arrange the first group,

n_{2}!

ways to arrange the second, etc. There are

n_{1}! \times n_{2}! \times . . . \times \n_{s}!

ways to arrange all of the categories together with groups in this order but none of those group reorders does anything since those data values are all the same. Dividing out those from the

n!

original permutations of all items leaves one with the multinomial coefficient.

🔗

Checkpoint 3.3.6. WebWork - Permutations with not all items distinguishable.

How many anagrams can be created from the word ’metamorphosis’ if the new words do not need to be meaningful?

Answer.

7.78378 \times 10^{8}

Essentials of Mathematical Probability and Statistics

Search Results:

Section 3.3 Permutations

Theorem 3.3.1. Permutations of everything.

Proof.

Theorem 3.3.2. Permutations of a subset without replacement.

Proof.

Checkpoint 3.3.3. WebWork - Permutations.

Theorem 3.3.4. Permutations of a subset with replacement.

Proof.

Theorem 3.3.5. Permutations when not all items are distinguishable (Multinomial Coefficients).

Proof.

Checkpoint 3.3.6. WebWork - Permutations with not all items distinguishable.