Neural Sync Active

Combinations — Selecting Items Without Order

Registry Synced

Combinations — Selecting Items Without Order

2112 words

11 min read

Reading compass

Now · 🎯 Learning Objectives

Combinations — Selecting Items Without Order

🎯 Learning Objectives

After completing this topic, you will be able to:

Calculate the number of combinations of n items taken r at a time
Understand the binomial coefficient ${n \choose r}$ and its properties
Distinguish between permutations and combinations
Apply combinations to probability problems
Use Pascal's triangle to find binomial coefficients

📋 Prerequisites

Permutations (09-permutations) — understanding when order matters
Counting Fundamentals (08-counting-fundamentals) — factorial notation
Basic algebra

📖 Core Content

11.1 Intuition: When Order Doesn't Matter

A combination counts selections where order does not matter. Key distinction:

Permutation: Pick 3 people for 1st, 2nd, 3rd prizes → ABC ≠ ACB → order matters
Combination: Pick 3 people for a committee → {A,B,C} = {C,A,B} → order doesn't matter

Everyday analogy: Choosing 3 toppings for a pizza: {mushrooms, pepperoni, olives} is the same pizza no matter what order you name the toppings. That's a combination. 🔑 Key Insight: Every permutation is a combination plus an ordering. So:

$P(n, r) = C(n, r) \times r!$

To go from combinations to permutations, multiply by $r!$ (the ways to order the r selected items).

11.2 The Combination Formula

11.2.1 Derivation

Since

P(n,r) = C(n,r) \times r!

, we have:

C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{(n-r)! \times r!}

11.2.2 Notation

The number of combinations is denoted as:

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

The symbol

{n \choose r}

is called the binomial coefficient (pronounced "n choose r").

11.2.3 Example

How many ways to choose 3 students from a class of 10?

C(10, 3) = {10 \choose 3} = \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120

Compare:

P(10,3) = 720

(6 times larger, because for each combination of 3 items, there are

3! = 6

orderings).

11.3 Properties of Combinations

Symmetry

{n \choose r} = {n \choose n-r}

Choosing r items is the same as choosing the n-r items to leave behind. Example:

{10 \choose 7} = {10 \choose 3} = 120

Special Values

Expression	Value	Intuition
${n \choose 0}$	1	One way to choose nothing
${n \choose 1}$	n	Choose 1 item from n
${n \choose n}$	1	One way to choose all items
${n \choose n-1}$	n	Choose all but one

Recurrence Relation (Pascal's Rule)

{n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}

This is the basis of Pascal's triangle.

11.4 Pascal's Triangle

Pascal's triangle is a triangular array of binomial coefficients:


pseudo
          1                     ${0 \choose 0}$
        1   1                   ${1 \choose 0}$ ${1 \choose 1}$
      1   2   1                 ${2 \choose 0}$ ${2 \choose 1}$ ${2 \choose 2}$
    1   3   3   1               ${3 \choose 0}$ ${3 \choose 1}$ ${3 \choose 2}$ ${3 \choose 3}$
  1   4   6   4   1             ${4 \choose 0}$ ${4 \choose 1}$ ${4 \choose 2}$ ${4 \choose 3}$ ${4 \choose 4}$
1   5  10  10   5   1           etc.

Construction: Each number is the sum of the two numbers above it (Pascal's rule). Uses:

Find binomial coefficients quickly
Expand binomials $(a + b)^n$ (the $n^{th}$ row gives coefficients)
Solve combination problems without formulas

11.5 Combinations with Repetition

When we can choose the same item multiple times (e.g., choosing 3 scoops of ice cream from 5 flavors, where flavors can repeat):

{n + r - 1 \choose r} = {n + r - 1 \choose n - 1}

Example: How many ways to choose 3 scoops from 5 flavors (repetition allowed)?

{5 + 3 - 1 \choose 3} = {7 \choose 3} = 35

Note: This is more advanced and less commonly tested in BSMA1002. Focus on combinations without repetition first.

11.6 Decision Flowchart

(Diagram)

11.7 Worked Examples

Example 1: Basic Combination (Easy)

Scenario: A pizza shop has 8 toppings. How many different 3-topping pizzas can you order? (No repeat toppings, order doesn't matter.) Solution:

C(8, 3) = {8 \choose 3} = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56

Interpretation: There are 56 different 3-topping combinations.

Example 2: Probability Using Combinations (Medium)

Scenario: A bag contains 5 red and 4 blue marbles. You draw 3 marbles without replacement. What's the probability of getting exactly 2 red and 1 blue? Solution: Total ways to draw 3 marbles from 9:

C(9, 3) = 84

Ways to get 2 red (from 5) and 1 blue (from 4):

C(5, 2) \times C(4, 1) = 10 \times 4 = 40

Probability:

P(2R, 1B) = \frac{40}{84} = \frac{10}{21} \approx 0.476

Example 3: Committee Problems (Harder)

Scenario: A committee of 5 must be formed from 6 men and 4 women. a) How many total committees? b) How many committees with exactly 3 men and 2 women? c) How many committees with at least 3 women? Solution: a) Total:

C(10, 5) = 252

b) Exactly 3 men and 2 women:

C(6, 3) \times C(4, 2) = 20 \times 6 = 120

c) At least 3 women: Cases:

3 women, 2 men: $C(4, 3) \times C(6, 2) = 4 \times 15 = 60$
4 women, 1 man: $C(4, 4) \times C(6, 1) = 1 \times 6 = 6$ Total with at least 3 women: $60 + 6 = 66$

11.8 Edge Cases & Gotchas

When r > n

{n \choose r} = 0

when

r > n

— you can't choose more items than available.

When r is Negative

The standard binomial coefficient

{n \choose r}

is defined only for

0 \leq r \leq n

(with non-negative integers). For negative r, it's undefined.

The Sum of Combinations

{n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n

This means the total number of all possible subsets of an n-element set is

2^n

11.9 Why This Matters

Combinations are everywhere in statistics:

Binomial distribution (Week 11): $P(X = k) = {n \choose k} p^k (1-p)^{n-k}$
Hypergeometric distribution: Sampling without replacement
Machine learning: Feature selection (which subset of features?)
Lottery design: How many possible lottery tickets?

📐 Key Formulas / Concepts

Concept	Formula	Example
Combinations (no repetition)	${n \choose r} = \frac{n!}{r!(n-r)!}$	${10 \choose 3} = 120$
Symmetry	${n \choose r} = {n \choose n-r}$	${10 \choose 7} = {10 \choose 3}$
Sum of combinations	$\sum_{r=0}^n {n \choose r} = 2^n$	For n=5: 32 total subsets
Combinations with repetition	${n+r-1 \choose r}$	3 scoops from 5 flavors: 35

⚠️ Common Pitfalls

Pitfall 1: Confusing Permutations and Combinations

The mistake: Using

C(n,r)

when order matters, or

P(n,r)

when it doesn't. Why it happens: The words "choose," "select," and "pick" are used in both contexts. How to avoid: Ask "Does the outcome ABC equal CBA?" If yes → combination. If no → permutation. Memory trick:

Permutation = Position matters
Combination = Choose (order doesn't matter)

Pitfall 2: Forgetting to Multiply Cases

The mistake: When computing "exactly 2 red and 1 blue," computing only one part. Why it happens: Students compute

C(5,2)

and stop, forgetting the blue marbles contribute to the count too. Correction: ALWAYS multiply the choices for each group:

C(\text{group 1}) \times C(\text{group 2}) \times \cdots

Pitfall 3: Using Combinations When Items Are Distinct but Repetition Is Allowed

The mistake: Using the standard

{n \choose r}

formula when repetition is allowed. Why it happens: The problem says "choose" and order doesn't matter, so students default to combinations. Correction: With repetition, use

{n+r-1 \choose r}

. Without repetition, use

{n \choose r}

📝 Practice Questions

Q1: Basic Combination

Compute ${8 \choose 3}$ .
<details> Solution
${8 \choose 3} = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$

$\boxed{56}$

</details> > **Q2: Committee Formation** > > > > How many ways to choose a committee of 4 from 15 people? > > <details> Solution > > $C(15, 4) = \frac{15!}{4!11!} = \frac{15 \times 14 \times 13 \times 12}{4 \times 3 \times 2 \times 1} = \frac{32760}{24} = 1365$ > > $\boxed{1,365}$ </details> > **Q3: Compare P and C** > > > > Compute both $P(8,3)$ and $C(8,3)$. How are they related? > > <details> Solution > > $P(8,3) = 8 \times 7 \times 6 = 336$ $C(8,3) = \frac{8!}{3!5!} = 56$ > > Relationship: $P(8,3) = C(8,3) \times 3! = 56 \times 6 = 336$ ✅ > > Each combination of 3 items can be ordered in 3! = 6 ways. </details> > **Q4: Lottery Probability** > > > > In a lottery, you choose 6 numbers from 1-49. How many possible tickets? > > <details> Solution > > $C(49, 6) = \frac{49!}{6!43!} = \frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{10,068,347,520}{720} = 13,983,816$ > > So there's a 1 in 13,983,816 chance of winning with one ticket. > > $\boxed{13,983,816}$ </details> > **Q5: Probability with Combinations** > > > > A bag has 7 red and 3 blue marbles. Draw 4 without replacement. Probability of exactly 2 red? > > <details> Solution > > **Total ways:** $C(10, 4) = 210$ > > **Ways to get 2 red and 2 blue:** $C(7, 2) \times C(3, 2) = 21 \times 3 = 63$ > > **Probability:** $63/210 = 3/10 = 0.3$ > > $\boxed{0.3}$ </details> > **Q6: Symmetry Property** > > > > Verify: ${7 \choose 4} = {7 \choose 3}$ > > <details> Solution > > ${7 \choose 4} = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5 \times 4}{4 \times 3 \times 2 \times 1} = \frac{840}{24} = 35$ > > ${7 \choose 3} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = \frac{210}{6} = 35$ > > ✅ They're equal. Choosing 4 items leaves behind 3 items. </details> > **Q7: "At Least" Problem** > > > > A group of 12 people — 7 men and 5 women. Choose a committee of 5. How many ways to get at least 4 men? > > <details> Solution > > **Case 1: 4 men, 1 woman** $C(7, 4) \times C(5, 1) = 35 \times 5 = 175$ > > **Case 2: 5 men, 0 women** $C(7, 5) \times C(5, 0) = 21 \times 1 = 21$ > > **Total:** $175 + 21 = 196$ > > $\boxed{196}$ </details> > **Q8: Poker Hand** > > > > A standard deck has 52 cards. How many 5-card poker hands are possible? How many are "flushes" (all 5 same suit)? > > <details> Solution > > **Total hands:** $C(52, 5) = 2,598,960$ > > **Flushes:** Choose 1 suit (4 choices), then choose 5 cards from that suit (13 cards): $4 \times C(13, 5) = 4 \times 1,287 = 5,148$ > > $\boxed{2,598,960 \text{ total},\ 5,148 \text{ flushes}}$ </details> > **Q9: Application — Quality Control** > > > > A batch of 20 items has 4 defective. You inspect 5 at random. Probability of finding exactly 1 defective? > > <details> Solution > > **Total ways to inspect 5 from 20:** $C(20, 5)$ > > **Ways to get 1 defective (from 4) and 4 good (from 16):** $C(4,1) \times C(16,4)$ > > $P = \frac{C(4,1) \times C(16,4)}{C(20,5)} = \frac{4 \times 1820}{15504} = \frac{7280}{15504} \approx 0.4695$ > > $\boxed{P \approx 0.47}$ </details> > **Q10: Prove Pascal's Rule** > > > > Verify Pascal's rule for n = 6, r = 3: ${6 \choose 3} = {5 \choose 3} + {5 \choose 2}$ > > <details> Solution > > ${6 \choose 3} = \frac{6!}{3!3!} = \frac{720}{36} = 20$ > > ${5 \choose 3} = \frac{5!}{3!2!} = \frac{120}{12} = 10$ > > ${5 \choose 2} = \frac{5!}{2!3!} = \frac{120}{12} = 10$ > > $10 + 10 = 20 = {6 \choose 3}$ ✅ > > The rule holds: each Pascal's triangle entry is the sum of the two above it. </details> * * * ## 🔗 Cross-References - **Next topic:** [Probability — Basic Concepts](/notes/01-foundation-bsma1002-stats-1-week07-11-probability-intro) — applying counting to probability calculations - **Previous:** [Permutations](/notes/01-foundation-bsma1002-stats-1-week06-09-permutations) — understanding the permutation-combination relationship - **Week 11 (Bernoulli & Binomial):** The binomial coefficient in $P(X=k)$ - **BSMA1001-maths-1:** The binomial theorem $(a+b)^n$ - **BSMA1004 (Stats 2):** Combinations in sampling distributions [Join Discord](https://discord.gg/gE2m4Qrdqv) [Previous**Permutations**](/notes/01-foundation-bsma1002-stats-1-week06-09-permutations)[Next**Probability Basics**](/notes/01-foundation-bsma1002-stats-1-week07-11-probability-intro)