Combinatorics: Videos & Practice Problems

Understanding permutations and combinations is essential for calculating the number of ways to arrange or select items. Permutations consider the order of selection, while combinations do not. The formulas for these concepts are crucial: for permutations, use $\frac{n}{\mathrm{n-r}}$ and for combinations, $\frac{n}{r}$. Mastering these principles aids in solving problems involving distinct and non-distinct objects, enhancing your mathematical proficiency.

Fundamental Counting Principle

When faced with multiple options for different items, determining the total number of possible combinations can be simplified using the fundamental counting principle. This principle states that if there are m choices for one item and n choices for another, the total number of combinations is simply m × n.

For example, if you have 3 clean shirts and 4 clean pairs of pants, you can find the total number of outfits by multiplying the number of shirts by the number of pants: 3 × 4 = 12. This means there are 12 different possible outfits you can create without having to list them all out.

Consider another scenario where a menu offers 4 appetizers and 6 entrees. To find the total number of meal combinations, you would again apply the fundamental counting principle: 4 (appetizers) × 6 (entrees) = 24 different meal options.

In a different example involving a coin flip and a roll of a 6-sided die, the principle still applies. The coin has 2 possible outcomes (heads or tails), and the die has 6 possible outcomes (1 through 6). Thus, the total outcomes for this scenario would be 2 × 6 = 12.

When considering multiple items, such as 4 shirts, 5 pairs of pants, and 3 pairs of shoes, you would continue to multiply the number of choices for each item: 4 (shirts) × 5 (pants) × 3 (shoes) = 60 different outfit combinations. This demonstrates that the fundamental counting principle can be extended to any number of choices, making it a powerful tool for calculating total outcomes efficiently.

How many possible outcomes are there if you roll 5 dice?

• A. 720
• B. 7776
• C. 5
• D. 6

Answer: (B)

How many options are there for license plates with any three letters (A-Z) followed by any 3 numbers (0-9)?

• A. 260
• B. 2340
• C. 11,232,000
• D. 17,576,000

Answer: (D)

Phone numbers are 10 digits long. How many possible phone numbers are there if the 1^st and 4^th numbers can't be 0?

• A. 10
• B. 90
• C. 8,100,000,000
• D. 10,000,000,000

Answer: (C)

Introduction to Permutations

Understanding permutations is essential when determining the number of ways to arrange items in a specific order, especially when each item can only be used once. For instance, if you have 5 different shirts and want to wear them over 5 days, the total arrangements can be calculated using the concept of factorials. The factorial of a number \( n \), denoted as \( n! \), is the product of all positive integers up to \( n \). In this case, the number of ways to wear the shirts is \( 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \).

However, if you have more shirts than days, such as 8 shirts over 5 days, the calculation changes. Here, you would use the permutations formula, which is defined as:

\[ P(n, r) = \frac{n!}{(n - r)!} \]

In this formula, \( n \) represents the total number of items (shirts), and \( r \) is the number of items to arrange (days). For 8 shirts over 5 days, you would calculate:

\[ P(8, 5) = \frac{8!}{(8 - 5)!} = \frac{8!}{3!} \]

This simplifies to \( \frac{8 \times 7 \times 6 \times 5!}{3!} \), allowing you to cancel out the \( 5! \) and focus on the multiplication of the remaining terms.

To illustrate this further, consider a teacher selecting a line leader and a door holder from a class of 25 students. Here, \( n = 25 \) and \( r = 2 \). The permutations would be calculated as:

\[ P(25, 2) = \frac{25!}{(25 - 2)!} = \frac{25!}{23!} = 25 \times 24 = 600 \]

In another example, if there are 10 fill-in-the-blank questions and a word bank of 14 words, where each word can only be used once, you would set \( n = 14 \) and \( r = 10 \). The calculation would be:

\[ P(14, 10) = \frac{14!}{(14 - 10)!} = \frac{14!}{4!} \]

By simplifying the numerator, you would multiply from 14 down to 5, canceling the \( 4! \) in the denominator, leading to a large number of possible arrangements.

In summary, permutations allow you to calculate the different ways to arrange items when order matters, using the factorial function and the specific permutations formula. This understanding is crucial for solving various combinatorial problems effectively.

A student formed a club at their school. They have 13 members, and need to elect a president, vice president, and treasurer. How many ways are there to fill these officer positions?

• A. 2197
• B. 1716
• C. 13
• D. 6

Answer: (B)

Emily is organizing her closet. She has 15 shirts left to hang but has space in one section for 6 shirts. How many ways could she hang shirts in that section?

• A. 3,603,600
• B. 90
• C. 9
• D. 362,880

Answer: (A)

Evaluate the given expression. ${}_9{P}_4$

• A. 24
• B. 3024
• C. 15,120
• D. 362,880

Answer: (B)

Permutations of Non-Distinct Objects

When dealing with permutations of distinct objects, such as selecting different shirts or marbles, the process is straightforward. However, when the objects are not distinct, like having multiple identical marbles, the approach changes slightly. In these cases, we need to adjust our permutation formula to account for the repeated items.

The general formula for permutations of n objects, where some objects are identical, is given by:

\[ P = \frac{n!}{r_1! \times r_2! \times \ldots \times r_k!} \]

Here, n is the total number of objects, and r_1, r_2, ..., r_k are the counts of each type of identical object. For example, if you have 4 blue marbles and 2 red marbles, the total number of permutations would be:

\[ P = \frac{6!}{4! \times 2!} \]

To illustrate this, consider the example of creating 8-digit codes using 5 zeros and 3 ones. Here, n is 8, r_1 (the number of zeros) is 5, and r_2 (the number of ones) is 3. The formula becomes:

\[ P = \frac{8!}{5! \times 3!} \]

By simplifying, we can rewrite the numerator to cancel out the factorials in the denominator:

\[ P = \frac{8 \times 7 \times 6 \times 5!}{5! \times 3!} \]

This simplifies to:

\[ P = \frac{8 \times 7 \times 6}{3!} \]

Calculating this gives us 56 different 8-digit codes.

Another example involves arranging the letters in the word "banana." The total number of letters, n, is 6. The counts of identical letters are: 1 'b', 3 'a's, and 2 'n's. Thus, we have:

\[ P = \frac{6!}{1! \times 3! \times 2!} \]

Rewriting the numerator to cancel the factorials gives:

\[ P = \frac{6 \times 5 \times 4 \times 3!}{1! \times 3! \times 2!} \]

After cancellation, we find:

\[ P = \frac{6 \times 5 \times 4}{2!} \]

Calculating this results in 60 different arrangements of the letters in "banana."

Understanding how to adjust the permutation formula for non-distinct objects is crucial for solving problems involving repeated items effectively. Practice with various examples will help solidify this concept.

You want to arrange the books on your bookshelf by color. How many different ways could you arrange 12 books if 4 of them have a blue cover, 3 are yellow, and 5 are white?

• A. 120
• B. 11,880
• C. 27,720
• D. 479,001,600

Answer: (C)

How many ways are there to arrange the letters in the word CALCULUS?

• A. 40,320
• B. 5040
• C. 720
• D. 6

Answer: (B)

Permutations vs. Combinations

In mathematics, understanding the difference between permutations and combinations is essential for organizing and selecting objects. The key distinction lies in whether the order of the objects matters. When dealing with permutations, the arrangement of objects is crucial; different orders represent different permutations. For example, when selecting two letters from the set {a, b, c}, the pairs (a, b) and (b, a) are considered distinct permutations because their order is different.

On the other hand, combinations focus on grouping objects without regard to order. Using the same set {a, b, c}, the pairs (a, b) and (b, a) represent the same combination, as the order does not affect the grouping.

To illustrate this concept, consider the scenario of selecting flavors for a milkshake from 32 different options. If you choose chocolate and vanilla, it is the same combination as vanilla and chocolate, indicating that the order does not matter. Thus, this situation is classified as a combination.

In contrast, if a photographer is arranging a family of five for a photo, the order in which the family members are positioned significantly impacts the outcome. Changing the arrangement alters the photo, making this a permutation scenario.

Lastly, when forming teams from a group of nine people, selecting four individuals does not depend on the order in which they are chosen. The team remains the same regardless of the selection sequence, confirming that this is also a combination.

In summary, the distinction between permutations and combinations hinges on the importance of order: permutations require consideration of order, while combinations do not. This understanding is crucial for solving various mathematical problems involving selection and arrangement.

Combinations

When exploring the concepts of permutations and combinations, it's essential to understand how they differ, particularly in terms of order. Permutations consider the arrangement of items, while combinations focus on the selection without regard to order. For example, when selecting 2 letters from a set of 3, the permutations yield 6 distinct arrangements, whereas the combinations result in only 3 unique selections.

The formula for permutations of selecting r items from n total items is given by:

\[ P(n, r) = \frac{n!}{(n - r)!} \]

In contrast, the combinations formula, which accounts for the fact that order does not matter, is derived from the permutations formula by dividing by r!:

\[ C(n, r) = \frac{n!}{r!(n - r)!} \]

In this formula, n represents the total number of items, and r is the number of items being chosen. A helpful mnemonic to remember the order of these variables is to think of it as n, n, r, r.

For practical application, consider an ice cream shop with 32 flavors where you want to choose 2 flavors for a milkshake. Since the order of flavors does not matter, this is a combinations problem. Here, n is 32 and r is 2, leading to:

\[ C(32, 2) = \frac{32!}{2!(32 - 2)!} = \frac{32!}{2! \cdot 30!} \]

By simplifying, we rewrite the numerator:

\[ 32! = 32 \times 31 \times 30! \]

Thus, the expression simplifies to:

\[ \frac{32 \times 31}{2!} = \frac{32 \times 31}{2} = 496 \]

This means there are 496 different ways to select 2 flavors.

In another example, if you need to form a team of 4 people from a group of 9, you again use the combinations formula. Here, n is 9 and r is 4:

\[ C(9, 4) = \frac{9!}{4!(9 - 4)!} = \frac{9!}{4! \cdot 5!} \]

Rewriting the numerator gives:

\[ 9! = 9 \times 8 \times 7 \times 6 \times 5! \]

After canceling the 5! in the denominator, we have:

\[ \frac{9 \times 8 \times 7 \times 6}{4!} = \frac{9 \times 8 \times 7 \times 6}{24} = 126 \]

This indicates that there are 126 different teams of 4 people that can be formed from a group of 9.

Understanding these formulas and their applications allows for effective problem-solving in scenarios involving selections and arrangements.

From a class of 28 students, in how many ways could a teacher select 4 students to lead the class discussion?

• A. 491,400
• B. 24
• C. 11,793,600
• D. 20,475

Answer: (D)

Evaluate the given expression. ${}_{11}{C}_7$

• A. 330
• B. 120
• C. 5040
• D. 7920

Answer: (A)

Here’s what students ask on this topic:

How do you calculate the number of possible outfits from multiple clothing items using the fundamental counting principle?

To calculate the number of possible outfits using the fundamental counting principle, you simply multiply the number of choices for each clothing item. For example, if you have 3 shirts and 4 pairs of pants, you multiply the number of shirts by the number of pants: $3\times 4=12$. This means you have 12 possible outfits. If you add another item, like 2 pairs of shoes, you multiply again: $3\times 4\times 2=24$. This gives you 24 possible outfits.

What is the difference between permutations and combinations?

The main difference between permutations and combinations is whether the order of the items matters. In permutations, the order matters. For example, the permutations of the letters A, B, and C taken two at a time are AB, BA, AC, CA, BC, and CB. In combinations, the order does not matter. For the same letters, the combinations taken two at a time are AB, AC, and BC. The formulas also differ: permutations use $\frac{n!}{(n-r)!}$, while combinations use $\frac{n!}{(n-r)!r!}$.

How do you calculate permutations of non-distinct objects?

To calculate permutations of non-distinct objects, you modify the standard permutation formula to account for repeated items. The formula is $\frac{n!}{r!s!}$, where $n$ is the total number of items, and $r$ and $s$ are the factorials of the counts of each type of repeated item. For example, for the word 'banana', which has 6 letters (n=6), 3 'a's (r=3), and 2 'n's (s=2), the formula is $\frac{6!}{3!2!}$, which simplifies to $60$.

How do you calculate combinations using the combinations formula?

To calculate combinations, use the formula $\frac{n!}{(n-r)!r!}$, where $n$ is the total number of items and $r$ is the number of items to choose. For example, if you have 9 people and want to form teams of 4, $(9c4)$ is calculated as $\frac{9!}{(9-4)!4!}$, which simplifies to $\frac{9!}{5!4!}$. This further simplifies to $126$ different teams.

What is the fundamental counting principle and how is it used in combinatorics?

The fundamental counting principle states that if there are $m$ ways to do one thing and $n$ ways to do another, then there are $m\times n$ ways to do both. This principle is used in combinatorics to calculate the total number of outcomes for multiple events. For example, if you have 3 shirts and 4 pairs of pants, you can calculate the total number of outfits by multiplying: $3\times 4=12$. This principle can be extended to more events by continuing to multiply the number of choices for each event.