26-03 — Combinations

Phase: Combinatorics | Subject: 26-03 Prerequisites: 26-02-permutations.md Next subject: 26-04-binomial-theorem-combinatorics.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define a combination as an unordered selection of objects
2. Compute $\binom{n}{r} = \frac{n!}{r!(n-r)!}$
3. Explain the relationship between permutations and combinations: $P(n,r) = r! \times \binom{n}{r}$
4. Apply symmetric identity $\binom{n}{r} = \binom{n}{n-r}$
5. Solve combinatorial problems choosing between permutations and combinations

Core Content

Definition

A combination is a selection of objects where the order does NOT matter. ${A, B}$ and ${B, A}$ are the same combination.

Binomial coefficient $\binom{n}{r}$ (read "$n$ choose $r$") is the number of ways to choose $r$ objects from $n$ distinct objects, without regard to order:

$$\binom{n}{r} = \frac{n!}{r! (n-r)!}$$

Derivation from Permutations

A permutation of $r$ objects from $n$ can be thought of as: first choose the $r$ objects ($\binom{n}{r}$ ways), then arrange them ($r!$ ways).

$$P(n, r) = \binom{n}{r} \times r! \quad \Rightarrow \quad \binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r!(n-r)!}$$

Key Identities

1. Symmetry: $\binom{n}{r} = \binom{n}{n-r}$
2. Boundary cases: $\binom{n}{0} = \binom{n}{n} = 1$, $\binom{n}{1} = \binom{n}{n-1} = n$
3. Pascal's Identity: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Permutation vs Combination Decision Tree

Ask: "Does the order matter?"

• YES → Permutation: $P(n, r)$
• NO → Combination: $\binom{n}{r}$

Example 1: Choosing a committee of 3 from 10 people. Order doesn't matter (the committee is a set). → $\binom{10}{3} = 120$.

Example 2: Choosing president, VP, secretary from 10 people. Order matters (positions are distinct). → $P(10, 3) = 720$.

Combinations with Repetition

If you can select an object more than once (order still doesn't matter), the number of ways is:

$$\binom{n + r - 1}{r}$$

This is the "stars and bars" formula for distributing $r$ identical items into $n$ distinct categories.

Example: How many ways to choose 3 scoops of ice cream from 5 flavors (repetition allowed)? $\binom{5 + 3 - 1}{3} = \binom{7}{3} = 35$.

Key Terms

• Combination
• Binomial Coefficient
• Pascal's Identity
• Stars and Bars

Worked Examples

Example 1: Committee Selection

From 8 men and 5 women, form a committee of 3 men and 2 women.

Solution: Choose men: $\binom{8}{3} = 56$. Choose women: $\binom{5}{2} = 10$. By product rule: $56 \times 10 = 560$ committees.

Example 2: Handshakes

At a party of 20 people, everyone shakes hands with everyone else exactly once. How many handshakes?

Solution: Each handshake is an unordered pair of people → $\binom{20}{2} = \frac{20 \times 19}{2} = 190$.

Example 3: Cards

How many 5-card poker hands from a standard 52-card deck?

Solution: Order doesn't matter → $\binom{52}{5} = \frac{52!}{5! 47!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{120} = 2,598,960$.

Quiz

Q1: What does the concept of Binomial coefficient primarily refer to in this subject?

A) A visual representation of Binomial coefficient B) A computational error related to Binomial coefficient C) A historical anecdote about Binomial coefficient D) The definition and application of Binomial coefficient

Correct: D)

• If you chose A: This is incorrect. Binomial coefficient is defined as: the definition and application of binomial coefficient. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Binomial coefficient is defined as: the definition and application of binomial coefficient. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Binomial coefficient is defined as: the definition and application of binomial coefficient. The other options describe different aspects that are not the primary focus.
• If you chose D: Binomial coefficient is defined as: the definition and application of binomial coefficient. The other options describe different aspects that are not the primary focus. Correct!

Q2: Which of the following is the key formula discussed in this subject?

A) A simplified version of \binom{n}{r} = \frac{n!}{r!(... B) The inverse operation of the formula in question C) \binom{n}{r} = \frac{n!}{r!(n-r)!} D) An unrelated formula from a different topic

Correct: C)

• If you chose A: This is incorrect. The formula \binom{n}{r} = \frac{n!}{r!(n-r)!} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: This is incorrect. The formula \binom{n}{r} = \frac{n!}{r!(n-r)!} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: The formula \binom{n}{r} = \frac{n!}{r!(n-r)!} is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose D: This is incorrect. The formula \binom{n}{r} = \frac{n!}{r!(n-r)!} is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Combination?

A) It is used to combination in mathematical analysis B) It is primarily a historical notation system C) It is used only in advanced research contexts D) It replaces all other methods in this domain

Correct: A)

• If you chose A: Combination serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose B: This is incorrect. Combination serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Combination serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Combination serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Stars and Bars is TRUE?

A) Stars and Bars is an advanced topic beyond this subject's scope B) Stars and Bars is not related to this subject C) Stars and Bars is a fundamental concept covered in this subject D) Stars and Bars is mentioned only as a historical footnote

Correct: C)

• If you chose A: This is incorrect. Stars and Bars is a fundamental concept covered in this subject. This subject covers Stars and Bars as part of its core content.
• If you chose B: This is incorrect. Stars and Bars is a fundamental concept covered in this subject. This subject covers Stars and Bars as part of its core content.
• If you chose C: Stars and Bars is a fundamental concept covered in this subject. This subject covers Stars and Bars as part of its core content. Correct!
• If you chose D: This is incorrect. Stars and Bars is a fundamental concept covered in this subject. This subject covers Stars and Bars as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) An unrelated numerical value B) The inverse of the correct answer C) Handshakes D) A different result from a common mistake

Correct: C)

• If you chose A: This is incorrect. The worked examples show that the result is Handshakes. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Handshakes. The other options represent common errors.
• If you chose C: The worked examples show that the result is Handshakes. The other options represent common errors. Correct!
• If you chose D: This is incorrect. The worked examples show that the result is Handshakes. The other options represent common errors.

Q6: How are Stars and Bars and Definition related?

A) Stars and Bars and Definition are completely unrelated topics B) Stars and Bars is the inverse of Definition C) Stars and Bars is a special case of Definition D) Stars and Bars and Definition are closely related concepts

Correct: D)

• If you chose A: This is incorrect. Both Stars and Bars and Definition are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both Stars and Bars and Definition are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Stars and Bars and Definition are covered in this subject as interconnected topics.
• If you chose D: Both Stars and Bars and Definition are covered in this subject as interconnected topics. Correct!

Q7: What is a common pitfall when working with Derivation From Permutations?

A) Derivation From Permutations is always computed the same way in all contexts B) A common mistake is confusing Derivation From Permutations with a similar concept C) The main error with Derivation From Permutations is using it when it is not needed D) Derivation From Permutations has no common misconceptions

Correct: B)

• If you chose A: This is incorrect. Students often confuse Derivation From Permutations with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: Students often confuse Derivation From Permutations with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose C: This is incorrect. Students often confuse Derivation From Permutations with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse Derivation From Permutations with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Key Identities?

A) Avoid Key Identities unless explicitly instructed B) Key Identities is not practically useful C) Use Key Identities only in pure mathematics contexts D) Apply Key Identities to solve problems in this subject's domain

Correct: D)

• If you chose A: This is incorrect. Key Identities is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. Key Identities is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. Key Identities is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: Key Identities is a practical tool used throughout this subject to solve relevant problems. Correct!

Practice Problems

1. Compute $\binom{8}{3}$.
   

   Click for answer

   $\binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$.

2. From 12 books, how many ways to choose 4 for a reading list (order irrelevant)?
   

   Click for answer

   $\binom{12}{4} = 495$.

3. How many ways to form a pizza with 2 toppings from 10 available toppings?
   

   Click for answer

   $\binom{10}{2} = 45$.

4. A test has 15 questions; students must answer any 10. How many choices?
   

   Click for answer

   $\binom{15}{10} = \binom{15}{5} = 3003$.

5. How many 7-card hands contain exactly 3 spades?
   

   Click for answer

   3 spades from 13: $\binom{13}{3} = 286$. 4 non-spades from 39: $\binom{39}{4} = 82,251$. Total: $286 \times 82,251 = 23,523,786$.

Summary

Key takeaways:

• Combinations count unordered selections: $\binom{n}{r} = n!/(r!(n-r)!)$
• Permutation = Combination × $r!$: choose, then arrange
• Symmetry: $\binom{n}{r} = \binom{n}{n-r}$
• Key question: Does order matter?
• Combinations with repetition: $\binom{n+r-1}{r}$ (stars and bars)

Pitfalls

• Confusing combinations with permutations when the problem mentions "select," "choose," or "pick": These words don't automatically mean combinations. "Select 3 books from a shelf" — if you're just identifying which books, it's a combination. If you're also deciding the order to read them, it's a permutation. Always determine whether the outcome is a set (order irrelevant) or a sequence (order matters). When in doubt, describe two specific outcomes and ask: are these the same result or different?
• Forgetting the symmetry identity $\binom{n}{r} = \binom{n}{n-r}$ for easier computation: Computing $\binom{100}{98}$ directly requires multiplying 98 terms — but $\binom{100}{98} = \binom{100}{2} = 100 \times 99 / 2 = 4950$. Always check whether $r$ or $n-r$ is smaller and use the smaller one. This also helps with algebraic simplification and identity proofs.
• Misapplying the stars-and-bars formula: $\binom{n+r-1}{r}$ counts selections of $r$ items from $n$ types WITH repetition and WITHOUT regard to order. If order matters (e.g., sequences with repetition), the count is $n^r$, not $\binom{n+r-1}{r}$. Also, stars-and-bars counts nonnegative integer solutions to $x_1 + \cdots + x_n = r$ — adjust to $\binom{r-1}{n-1}$ if each $x_i \geq 1$ (positive solutions). Always check: (a) is repetition allowed? (b) does order matter?
• Double-counting when combining selections from different groups: "Choose 3 men from 8 AND 2 women from 5" correctly multiplies: $\binom{8}{3} \times \binom{5}{2}$. But "Choose 5 people from a group of 8 men and 5 women with at least 2 women" requires casework or complement counting — you cannot simply apply one product. Multiplying selections that are not independent stages produces garbage counts.
• Treating $\binom{n}{r}$ as defined for $r > n$ without checking: $\binom{n}{r} = 0$ for $r > n$ by convention (there are zero ways to choose more items than exist). However, the factorial formula $n!/(r!(n-r)!)$ is undefined when $r > n$ due to negative factorial arguments. In algebraic derivations, treat $\binom{n}{r}$ as zero for $r > n$ and verify that identities hold under this convention. This is especially important in infinite sums and generating function manipulations.

Next Steps

Next up: 26-04-binomial-theorem-combinatorics.md — the binomial theorem via combinatorial reasoning.