Combinations with 'At Least' & 'At Most'

Recap: The Core of Combinations

Before we add the new constraints, let's quickly recall the fundamental idea of combinations. A combination is a selection of items where the order of selection is irrelevant. The number of ways to choose $r$ items from a set of $n$ distinct items is given by the formula:

${}^n{C}_r=\frac{n!}{r!(n-r)!}$

For example, choosing a committee of 2 people from 4 (A, B, C, D) can be done in ${}^4{C}_2=\frac{4!}{2!2!}=6$ ways. The committee {A, B} is the same as {B, A}.

1. Tackling "At Least" Conditions

The phrase "at least" implies a minimum quantity. For example, "select at least 2 boys" means you could select 2 boys, or 3 boys, or 4 boys, and so on, up to the maximum possible.

There are two primary methods to solve these problems.

Method 1: Direct Casework (Sum of "OR" Scenarios)

This is the most straightforward method. You identify all the valid cases that satisfy the condition, calculate the combinations for each case, and then add them up. Remember, in combinatorics, the word "OR" translates to addition, and "AND" translates to multiplication.

Let's consider a typical problem: From a group of 6 Indians and 5 Americans, in how many ways can we form a committee of 5 members such that Indians are in the majority?

"Indians are in the majority" means we need at least 3 Indians in a committee of 5. This leads to three possible cases:

• Case 1: 3 Indians AND 2 Americans
• OR
• Case 2: 4 Indians AND 1 American
• OR
• Case 3: 5 Indians AND 0 Americans

Now, we calculate the combinations for each case and add them:

• Ways for Case 1: ${}^6{C}_3{\times }^5{C}_2=20\times 10=200$
• Ways for Case 2: ${}^6{C}_4{\times }^5{C}_1=15\times 5=75$
• Ways for Case 3: ${}^6{C}_5{\times }^5{C}_0=6\times 1=6$

Total ways = $200+75+6=281$.

The following image illustrates this exact process.

Method 2: The Subtraction Principle (Total - Unwanted)

Sometimes, calculating the valid cases directly is tedious. It might be easier to calculate the total number of ways without any restrictions and then subtract the number of unwanted ways.

Ways for "At Least k" = (Total Ways) - (Ways for "Less than k")

Let's try this with a new problem: A box contains 5 red balls and 4 blue balls. In how many ways can you select 3 balls such that at least one is red?

Using direct casework (Method 1):

• Case 1: 1 red AND 2 blue ${\to }^5{C}_1{\times }^4{C}_2=5\times 6=30$
• Case 2: 2 red AND 1 blue ${\to }^5{C}_2{\times }^4{C}_1=10\times 4=40$
• Case 3: 3 red AND 0 blue ${\to }^5{C}_3{\times }^4{C}_0=10\times 1=10$
• Total ways = $30+40+10=80$.

Now, let's use the Subtraction Principle (Method 2):

1. Total ways to select 3 balls from the total of 9: ${}^9{C}_3=\frac{9\times 8\times 7}{3\times 2\times 1}=84$.
2. Unwanted ways: The only unwanted case is selecting "less than one red ball," which means selecting zero red balls. This means all 3 balls must be blue.
   • Ways for 0 red AND 3 blue: ${}^5{C}_0{\times }^4{C}_3=1\times 4=4$.
3. Result: Total ways - Unwanted ways = $84-4=80$.

As you can see, the subtraction method was faster here. Choosing which method to use is a strategic decision: count the number of cases for each method and pick the one that requires less work.

A Special Shortcut: "At Least One"

The "at least one" scenario is so common that it has a very useful shortcut. When selecting from a group of n distinct items, the number of ways to select at least one is:

$\text{Total possible selections}-\text{The one case of selecting none}=(2^n)-1$

Let's see this applied in a more complex problem.

The logic in that problem is:

• Ways to select at least one yellow (from 5) = $2^5-1$
• Ways to select at least one black (from 4) = $2^4-1$
• Ways to select one or more red (from 3) = $2^3$. Note: The problem might have a slight variation. In the provided resource, it says "one or more red balls", but the solution uses $2^3$. Let's assume it means "any number of red balls (including zero)". If it meant "at least one red", it would be $2^3-1$. This highlights the importance of reading the question carefully. Assuming the question implies we can select any number of red balls (0, 1, 2, or 3), the number of ways is ${}^3{C}_0{+}^3{C}_1{+}^3{C}_2{+}^3{C}_3=2^3$.

The total ways are the product: $(2^5-1)(2^4-1)(2^3)$.

2. Tackling "At Most" Conditions

The phrase "at most" implies a maximum quantity. For example, "select at most 2 women" means you could select 0 women, or 1 woman, or 2 women.

For "at most" problems, the direct casework method is almost always the best approach. You simply list the allowed cases and sum their results.

Let's work through an example: From a group of 6 men and 4 women, a committee of 5 is to be formed. In how many ways can this be done if the committee must have at most 2 women?

"At most 2 women" allows for three possible cases:

• Case 1: 2 women AND 3 men
• OR
• Case 2: 1 woman AND 4 men
• OR
• Case 3: 0 women AND 5 men

Let's calculate:

• Ways for Case 1: ${}^4{C}_2{\times }^6{C}_3=6\times 20=120$
• Ways for Case 2: ${}^4{C}_1{\times }^6{C}_4=4\times 15=60$
• Ways for Case 3: ${}^4{C}_0{\times }^6{C}_5=1\times 6=6$

Total ways = $120+60+6=186$.

To see another example of casework, you can review a problem from the following resource.

Conclusion

You have now learned the systematic ways to handle the common constraints of "at least" and "at most" in selection problems. These methods are essential for converting tricky word problems into straightforward calculations on exam day.

Key Takeaways:

• "At Least":
  • Method 1 (Direct Casework): Sum up all valid cases. Use when the number of valid cases is small.
  • Method 2 (Subtraction): Calculate Total - Unwanted. Use when the number of unwanted cases is small.
  • Shortcut: For "at least one" from $n$ items, the answer is often $2^n-1$.
• "At Most":
  • Method (Direct Casework): This is the standard approach. Sum the cases from 0 up to the maximum allowed number.
• Core Logic: Always remember that AND means multiply (within a case) and OR means add (between cases).

Preview of the Next Lesson:
We've now covered the fundamental counting principles for both arrangements and selections. In our next lesson, we will begin our journey into Probability. You will see that the skills you've just honed are the building blocks for calculating probabilities. A probability is simply a ratio: (Number of Favorable Outcomes) / (Total Number of Possible Outcomes). Calculating both the numerator and denominator will often be a combinatorics problem just like the ones we solved today.