Permutation and Combination
Enroll to start learning
You’ve not yet enrolled in this course. Please enroll for free to listen to audio lessons, classroom podcasts and take practice test.
Interactive Audio Lesson
Listen to a student-teacher conversation explaining the topic in a relatable way.
Understanding Permutations
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Today, we're diving into permutations! Can anyone tell me what a permutation is?
Isn't it just an arrangement of items where the order matters?
Exactly! For example, if we have three people, A, B, and C, how many ways can we arrange two of them?
I think it would be AB, AC, BA, BC, CA, and CB. That’s six arrangements!
Great job! We can calculate this using the permutation formula P(n, r) = n! / (n - r)!. Here, n is the total items, and r is how many we pick.
So what's n!?
Good question! n! stands for 'n factorial,' which is the product of all positive integers up to n. Let's say n = 3, then 3! = 3 × 2 × 1 = 6.
So for our case, it would be 3! / (3 - 2)! = 6 / 1 = 6. It all makes sense!
Wonderful! To remember, think of the phrase: 'P is for Position' to recall that order matters in permutations.
So, what’s the formula for permutations?
P(n, r) = n! / (n - r)!.
Combinations Defined
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Now let's shift gears to combinations. Who can explain what this means?
It’s when the order doesn’t matter! Like choosing 2 fruits from an assortment.
Exactly! Can you provide an example with three fruits, say, apple, banana, and cherry?
Sure! The pairs would just be AB, AC, or BC. The order wouldn’t count, right?
Well done! We denote this by the combination formula C(n, r) = n! / (r! * (n - r)!).
Is n! still the factorial of n?
Yes! And r! is the number of ways to arrange the r selected objects. This accounts for order not being important.
So it’s the total arrangements divided by arrangements of what's selected?
Precisely! A helpful mnemonic for combinations could be 'C is for Choose,' as you are just selecting.
Can anyone remind me of the combination formula?
C(n, r) = n! / (r! * (n - r)!).
Permutations with Repetition
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Let's explore what happens when we allow repetitions in permutations. What would be an example?
If we have three flavors of ice cream, can we pick two scoops where a flavor can repeat?
Exactly! If we have flavors A, B, and C, how would we calculate the number of different combinations for two scoops?
Umm, wouldn’t that just be 3 options for the first scoop and 3 for the second?
Great observation! Therefore, it would be 3^2 = 9 possible arrangements. The formula would be n^r for this case.
So, it's like multiplying choices for each slot!
Exactly! To remember, think of 'Repetition equals multiplication.' In worksheets, we approach problems considering whether repetition is allowed or not.
So how do we express our findings?
For permutations with repetition, n^r!
Combinations with Repetition
🔒 Unlock Audio Lesson
Sign up and enroll to listen to this audio lesson
Now let’s examine combinations where repetitions are allowed. Can someone give an application of this?
How about choosing donuts? We can choose any number of the same type!
Exactly! For example, if you can select three donuts from four types, how would you visualize this?
I guess we’d picture the choices laid out with dividers between types of donuts?
Very well put! This method leads us to the formula for combinations with repetition, C(n + r - 1, r).
Could you clarify the ‘-1’ part in the formula?
Absolutely! In this case, we represent each chosen object with one cross and separate object types with a line, linking the cross and the total choices together.
What’s the overall significance of these tools in combinatorics?
These tools allow us to approach countless practical problems. Just remember, 'Combinations choose, permutations order.' That's an important takeaway!
Introduction & Overview
Read summaries of the section's main ideas at different levels of detail.
Quick Overview
Standard
This section covers permutations, where order matters in arrangements of selections from sets, and combinations, where order does not matter. Key formulas and examples are provided to illustrate how to calculate permutations and combinations, including scenarios with and without repetitions allowed.
Detailed
Permutation and Combination
This section explores the fundamental concepts of permutations and combinations, essential tools in combinatorial mathematics.
Key Concepts:
- Permutations are defined as ordered arrangements of objects. The number of permutations of selecting r elements from a set of n distinct elements is denoted by P(n, r) and calculated using the formula:
P(n, r) = n! / (n - r)!
- Combinations refer to selections where the order does not matter; for instance, choosing items from a menu or selecting people from a group. The formula for combinations is:
C(n, r) = n! / (r! * (n - r)!)
Additionally, this section presents examples, such as selecting 2 out of 3 people and exploring permutations with repetition allowed. A significant takeaway is understanding the distinction between permutations and combinations and various scenarios affecting their calculations.
Youtube Videos
Audio Book
Dive deep into the subject with an immersive audiobook experience.
Introduction to Permutations
Chapter 1 of 6
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
So to begin with, what is a permutation of a set of objects? As the name suggests, it is an ordered arrangements of objects and when I say the ordered arrangement of the objects, that means the ordering of the objects matter here.
Detailed Explanation
A permutation refers to the different ways in which a set of objects can be arranged in order. The main point to understand is that the specific sequence in which the elements appear makes a difference. For example, if we have two people, person 1 and person 2, the arrangement 'Person 1 followed by Person 2' is different from 'Person 2 followed by Person 1'. This concept is crucial when it comes to permutations because it relates to the order of selection.
Examples & Analogies
Imagine you have two distinct flavored ice creams, vanilla and chocolate. If you put vanilla in a cone first and then chocolate, that’s different from putting chocolate first and then vanilla. The order of scoops matters—just like in permutations!
Definition of 'r-Permutation'
Chapter 2 of 6
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
We define what we call as r-permutation and an r-permutation is nothing but an ordered selection of r elements from a set.
Detailed Explanation
An 'r-permutation' refers specifically to the selection of r elements out of a larger set of n distinct elements, with the order of the selection being important. To denote the number of r-permutations of n elements, we use the notation P(n, r). This formula calculates how many ways we can arrange r selected items from a group of n distinct items.
Examples & Analogies
Consider a race with three runners: Alice, Bob, and Charlie. If we want to find out in how many different ways they can finish in 2nd and 3rd place—their placements matter. The arrangements can be: 'Alice finishes 2nd, Bob finishes 3rd', or 'Bob finishes 2nd, Alice finishes 3rd', resulting in distinct outcomes.
Calculating r-Permutations
Chapter 3 of 6
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
The number of such r-permutations from a set consisting of n distinct elements is denoted by the permutation function P(n, r).
Detailed Explanation
The calculation involves the product rule, which is used to derive the formula for P(n, r): P(n, r) = n × (n-1) × (n-2) × ... × (n-r+1). This formula accounts for the fact that once an element has been chosen, it cannot be selected again. This is why the choices reduce as we fill each successive position.
Examples & Analogies
Imagine you have 4 medals and you want to award them to only 3 athletes. For the 1st medal, you have 4 choices. After handing over that medal, you only have 3 left for the 2nd medal, and 2 remaining options for the last one. Thus, the ways you can award these medals follow the permutation formula.
Special Case of 0 Permutations
Chapter 4 of 6
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
We define P(n, 0) = 1, namely, no way of permuting 0 objects.
Detailed Explanation
When we talk about permutations, if you have a set of n objects but decide not to choose any (0 objects), there is exactly one way to do that: by simply not choosing anything at all. This principle helps in establishing the foundation of the permutation function.
Examples & Analogies
Think about choosing toppings for a pizza. If you decide to have no toppings (0 toppings), there is only one way to do that: just order the plain pizza. You’re not adding anything, so only one way exists!
Transitioning to Combinations
Chapter 5 of 6
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
Now, we can define C(n, r), which represents unordered selections.
Detailed Explanation
While permutations focus on the order of arrangement, combinations concern themselves with whether elements are selected together without regard to order. C(n, r) marks the number of ways to choose r objects from n distinct objects when the order does not matter, ensuring the focus is on the selection rather than arrangement.
Examples & Analogies
Consider a fruit salad. If your basket includes apples, bananas, and oranges, selecting an apple and a banana counts as the same choice as choosing a banana and then an apple. Here, only the chosen fruits matter, not the order in which they are picked.
Relating Permutations to Combinations
Chapter 6 of 6
🔒 Unlock Audio Chapter
Sign up and enroll to access the full audio experience
Chapter Content
The relation between the permutation and combination functions is C(n, r) = P(n, r) / r!.
Detailed Explanation
This relationship arises because every combination can appear in multiple arrangements. Thus, the number of permutations of r chosen items (P(n, r)) would be divided by the number of ways to arrange these same r items (r!), providing the combination count. This illustrates the connection and the mathematical relation between the two concepts of arrangement.
Examples & Analogies
Think of creating a team from a group. If you can choose 3 out of 10 players to form a basketball team, selecting 'Player A, Player B, Player C' is the same as 'Player B, Player C, Player A'. When counting teams, we only list unique combinations, not the rearrangements.
Key Concepts
-
Permutations are defined as ordered arrangements of objects. The number of permutations of selecting r elements from a set of n distinct elements is denoted by P(n, r) and calculated using the formula:
-
P(n, r) = n! / (n - r)!
-
Combinations refer to selections where the order does not matter; for instance, choosing items from a menu or selecting people from a group. The formula for combinations is:
-
C(n, r) = n! / (r! * (n - r)!)
-
Additionally, this section presents examples, such as selecting 2 out of 3 people and exploring permutations with repetition allowed. A significant takeaway is understanding the distinction between permutations and combinations and various scenarios affecting their calculations.
Examples & Applications
If you have four books and want to know how many ways to arrange three of them, use permutations: P(4, 3) = 4!/(4-3)! = 24 ways.
For a committee of 3 people chosen from 5 candidates, use combinations: C(5, 3) = 5!/(3! * (5-3)!) = 10 ways.
Memory Aids
Interactive tools to help you remember key concepts
Rhymes
To permute is to arrange, in every way there's no change. Combinations mean simply select, without worry, just connect.
Stories
Imagine a chef deciding how to present dishes. Each arrangement alters their impact, defining permutations, whereas combinations focus on the selected flavors.
Memory Tools
Remember 'P for Position' in permutations and 'C for Choose' in combinations!
Acronyms
P = Permutation (Order matters), C = Combination (Order doesn't matter).
Flash Cards
Glossary
- Permutation
An ordered arrangement of elements.
- Combination
A selection of elements where order does not matter.
- n Factorial (n!)
The product of all positive integers up to n.
- Distinct Elements
Unique items in a set without duplication.
- Repetition
Allowing elements to be selected more than once.
Reference links
Supplementary resources to enhance your learning experience.