Permutations (Without Repitition)

Permutations (Without Repitition)

In the prior lesson, we stated that a permutation is an arrangement of items where the specific sequence is important. In these types of permutations, we assume no repetition. This means once an item is placed in a position, it cannot be selected again. The formula is:

Where:

• P: Represents Permutations (the count of possible arrangements).
• n: The total number of distinct items available to choose from.
• r: The number of items being selected and arranged. 

Note that P(n,r) is also often written as nPr

It is important to 

To understand this formula, we will first look at it's underlying concepts. 

I. Fundamental Counting Principle

The fundamental principle of counting (aka, Rule of Products) is a basic concept used to determine the total number of possible outcomes in a situation where there are multiple independent events. It allows us to count a large number of possibilities without needing to list each one individually.

The fundamental Counting Principle states that if there are a ways (choices) of doing something and b ways (choices) of doing another thing, then there are a x b ways (choices) of performing both actions.

Example: The Ice Cream Shop

You can choose a cone: Waffle or Sugar (2 options).

You can choose a flavor: Vanilla, Chocolate, or Strawberry (3 options).

How many distinct ice cream cones can you make?

2 x 3 = 6 possibilities

II. From Counting to Factorials (n!)

Now let's apply that same counting principle to arranging objects.

Example: Arranging Books
Imagine you have 3 different books (A, B, and C) and you want to put them in order on a shelf. How many different ways can you arrange them?

1. Slot 1: How many choices do you have for the first spot? 3 (A, B, or C).
2. Slot 2: You put one book down. How many are left for the second spot? 2.
3. Slot 3: You put the second book down. How many are left? 1.

According to the Fundamental Counting Principle, we multiply these choices:

3 x 2 x 1 = 6 arrangements

In mathematics, we arrange items so often that we created a shorthand symbol for "multiplying a number by every integer smaller than it down to 1." This is the Factorial (!).

5! = 5 x 4 x 3 x 2 x 1

3! = 3 x 2 x 1

1! = 1

Note the special case of the factorial of 0 = 1

0! = 1 

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

Key Takeaway: Factorials (n!) calculate the number of ways to arrange ALL items in a set.

III. Deriving the Permutations Formula

This is where many students get lost. What if we don't want to arrange all the books? What if we have a big group, but we only want to arrange a few of them?

This is called a Permutation.

• n = Total items available.

• r = Number of items we are actually choosing and arranging.

The Logic (Without the Formula)

Let's use the Fundamental Counting Principle again.

Scenario: Eight runners are in a race (n=8). We need to award Gold, Silver, and Bronze medals (r=3). We are not arranging all 8 runners, just the top 3.

1. Gold Medal: Any of the 8 runners can win.

2. Silver Medal: The winner can't win twice, so 7 runners are left.

3. Bronze Medal: The top two are occupied, so 6 runners are left.

Using the Counting Principle:

8 x 7 x 6 - 366 ways

Finding the Formula 
How do we represent that "partial factorial" mathematically?

We calculated: 8 x 7 x 6.

We know that the full factorial is: 8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

We want to mathematically "remove" the bold part we didn't use. In multiplication, we "remove" things by dividing.

The part we want to remove (5 x 4 x 3 x 2 x 1) is actually just 5!.

So, we can write our calculation as:

Where did the 5 come from? The 5 is the number of people who lost (did not get a medal).

Losers = Total Runners - Winners 

5 = 8 - 3

So the formula is actually

This leads us directly to the formula for permutations (nPr)

Note:

In practice, when solving these problems you will likely just use a shorthand method for what the formula formally represents. That is, you will:

1. Look at r to find how many numbers will be in your multiplication chain.

2. Then start with n as the first number in your chain.

3. Multiply by decreasing integers (n - 1, n - 2, etc)

4. Stop when you have reached r numbers.

I'll call this the countdown method

V. Solving Permutations

Example:

Solve for P(6, 3)

Step1: We look at r (which here is 3). This means you need to multiply 3 numbers.

Step 2: Start with n (for this problem is 6)

Step 3: Multiply downward until you have 3 numbers in your chain:

6 x 5 x 4 = 120

Now I'll solve using the formula:

P(6, 3) = 6 x 5 x 4 x 3 x 2 x 1/ 3 x 2 x 1

P(6, 3) = 720/6 = 120

Gemini AI

CK-12: Permutations and Combinations Compared

https://www.geeksforgeeks.org/maths/fundamental-principle-of-counting/

https://www.mathsisfun.com/data/basic-counting-principle.html

https://en.wikipedia.org/wiki/Rule_of_product