Combinatorics: Permutations and Arrangements

TL;DR

Permutations deal with counting arrangements where order matters, like arranging letters in a word. When items are identical, you adjust your counting method to avoid overcounting. You'll use factorials and division to solve these types of problems.

1. The Mental Model

Imagine you have a set of distinct items, and you want to know all the different ways you can line them up. That's a permutation! When some of those items are identical, it just means you have fewer unique ways to line them up than if they were all different.

2. The Core Material

Permutations are about arrangements where the order matters. Think of assigning seats, forming passwords, or arranging books on a shelf. Each different ordering counts as a unique permutation.

a) Permutations of Distinct Items

Photo by Quang Nguyen Vinh on Pexels

When you have 'n' distinct items and you want to arrange all of them, the number of permutations is given by 'n factorial' (n!).
n! = n × (n-1) × (n-2) × ... × 2 × 1

For example, if you have 3 distinct letters (A, B, C), you can arrange them in 3! = 3 × 2 × 1 = 6 ways:
ABC, ACB, BAC, BCA, CAB, CBA.

If you only want to arrange 'r' items out of 'n' distinct items, the formula is:
P(n, r) = n! / (n-r)!
This is read as "n permute r".

Example: You have 5 different books, and you want to arrange 3 of them on a shelf.
P(5, 3) = 5! / (5-3)! = 5! / 2! = (5 × 4 × 3 × 2 × 1) / (2 × 1) = 5 × 4 × 3 = 60 ways.

b) Permutations with Repetition (Identical Items)

Photo by MART PRODUCTION on Pexels

Sometimes, you're arranging items where some of them are identical. For example, the letters in the word "MISSISSIPPI". If you treat all the 'S's as distinct, you'd get far too many arrangements because swapping two 'S's doesn't create a new arrangement.

To handle identical items, you divide the total number of arrangements (as if all items were distinct) by the factorial of the count of each repeated item.

The formula is: n! / (n1! × n2! × ... × nk!)
Where 'n' is the total number of items, and n1, n2, ..., nk are the counts of each set of identical items.

Example: How many distinct arrangements of the letters in the word "BOOK"?
- Total letters (n) = 4
- Letter 'B': 1 (n_B = 1)
- Letter 'O': 2 (n_O = 2)
- Letter 'K': 1 (n_K = 1)

Number of arrangements = 4! / (1! × 2! × 1!) = 24 / (1 × 2 × 1) = 24 / 2 = 12

Here's how you can think about the process:

graph TD
    A["Identify all items"] --> B["Count total items (n)"]
    B --> C{Are all items distinct?}
    C -- Yes --> D["Calculate n!"]
    C -- No --> E["Identify identical items and their counts (n1, n2, ...)"]
    E --> F["Calculate n! / (n1! * n2! * ...)"]
    D --> G["Result: Number of Permutations"]
    F --> G

c) Permutations with Repetition (Choosing with replacement)

Photo by Insaanu Studio on Pexels

This is a different type of repetition problem where you're selecting items and replacing them, or items can be chosen multiple times. For example, creating a 3-digit number using digits 1, 2, 3 where repetition is allowed.
If you have 'n' distinct items and you choose 'r' of them with replacement, the number of permutations is n^r.

Example: How many 3-digit numbers can you form using the digits 1, 2, 3, 4, 5 if repetition is allowed?
- n = 5 (available digits)
- r = 3 (digits to choose)
Number of arrangements = 5^3 = 5 × 5 × 5 = 125

3. Worked Example

Let's find the number of distinct arrangements of the letters in the word "MATHEMATICS".

1. Count the total number of letters (n):
   M-A-T-H-E-M-A-T-I-C-S = 11 letters. So, n = 11.

2. Identify any repeated letters and count their occurrences:

   • M: appears 2 times
   • A: appears 2 times
   • T: appears 2 times
   • H, E, I, C, S: each appear 1 time

3. Apply the formula for permutations with identical items:
   n! / (n_M! × n_A! × n_T! × n_H! × n_E! × n_I! × n_C! × n_S!)
   This simplifies to: 11! / (2! × 2! × 2! × 1! × 1! × 1! × 1! × 1!)

4. Calculate:
   11! = 39,916,800
2! = 2
   So, 39,916,800 / (2 × 2 × 2) = 39,916,800 / 8 = 4,989,600

There are 4,989,600 distinct arrangements of the letters in the word "MATHEMATICS".

4. Key Takeaways

• Permutations are about counting ordered arrangements. If the order changes, it's a new permutation.
• For distinct items, n! gives the total arrangements of 'n' items, and P(n, r) gives arrangements of 'r' items chosen from 'n'.
• When items are identical, divide by the factorial of the count of each repeated item to correct for overcounting.
• For arrangements with replacement (like passwords with repeating characters), use n^r.
• Understanding when to use each formula is crucial; pay attention to whether items are distinct, if order matters, and if repetition is allowed/present.
• Factorials grow very quickly, so permutation numbers can be quite large.

5. Now Try It

You're decorating a shelf with 7 unique ornaments. However, 3 of them are identical blue vases, and the other 4 are distinct. How many different ways can you arrange these 7 items on the shelf?

What success looks like: Your answer should be a single number, calculated using the correct permutation formula for identical items, clearly showing your steps for identifying total items and repeated items.