Combinatorics path · C03

Before this lesson: Factorials, Basic counting principles

Your goal: Distinguish a selection from an arrangement and justify the overcount factor.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Combinations and binomial coefficients: the key idea

The binomial coefficient C(n,k)=n!/[k!(n−k)!] counts k-element subsets of an n-element set for 0≤k≤n. Order is ignored, so each ordered selection is divided by its k! internal orders. Symmetry C(n,k)=C(n,n−k) comes from taking complements. Pascal’s identity C(n,k)=C(n−1,k−1)+C(n−1,k) splits subsets according to whether one distinguished object is included. For restricted choices, define disjoint cases before applying these formulas.

A worked example

Choose a three-person team from eight students with one specified student required.

Include that student first, then choose two of the remaining seven: C(7,2)=21. No ordering of the team members is counted.

Your turn: change one thing

How many three-person teams from eight exclude one specified student?

Try this on paper before opening the explanation.

Compare your reasoning

Choose all three from the other seven, giving C(7,3)=35. Together with 21 including that student this gives C(8,3)=56.

Pause and check

A trap to avoid: Using a combination formula when order matters.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove Pascal’s identity by counting k-element subsets.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Fix an element e of an n-element set. Subsets containing e choose k−1 elements from the other n−1; those excluding e choose k from the other n−1. The cases are disjoint and cover all subsets, so their counts add to C(n,k).

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. Does order matter in a combination?

Foundation

  1. Only for odd k
  2. Only for large n
  3. No
  4. Yes always
Hint

A combination is a subset.

Answer and reasoning

No. Reordering the same selected objects does not create a new subset.

2. C(n,0) equals what?

Foundation

  1. 1
  2. 0
  3. n
  4. n!
Hint

There is one empty subset.

Answer and reasoning

1. Choosing no elements has exactly one outcome.

3. What is C(6,2)?

Core

  1. 36
  2. 15
  3. 30
  4. 12
Hint

Divide ordered pairs by 2!.

Answer and reasoning

15. 6·5/2=15.

4. Three-person teams from eight including a fixed student?

Core

  1. 42
  2. 21
  3. 56
  4. 35
Hint

Choose two from the other seven.

Answer and reasoning

21. C(7,2)=21.

5. Why does C(n,k)=C(n,n−k)?

Stretch

  1. Both always equal n
  2. Order matters twice
  3. Every subset is empty
  4. Taking complements is a bijection
Hint

Each subset determines its complement uniquely.

Answer and reasoning

Taking complements is a bijection. A k-subset corresponds one-to-one to the unchosen (n−k)-subset.

6. Pascal’s identity partitions subsets by what?

Stretch

  1. Whether n is prime
  2. Their colour only
  3. Whether a fixed element is included
  4. Their alphabetical order
Hint

Use two exhaustive disjoint cases.

Answer and reasoning

Whether a fixed element is included. Including the fixed element leaves k−1 other choices; excluding it leaves k.

7. What does C(n,n) equal?

Foundation

  1. 0
  2. n!
  3. 1
  4. n
Hint

There is one full subset.

Answer and reasoning

1. Selecting all n elements has one outcome.

8. Choose two objects from seven. How many unordered selections?

Core

  1. 49
  2. 21
  3. 42
  4. 14
Hint

Divide ordered pairs by 2.

Answer and reasoning

21. 7·6/2=21.

9. Why divide ordered k-selections by k!?

Stretch

  1. Because k! is always prime
  2. Because order still matters
  3. To exclude empty subsets
  4. Each subset has exactly k! internal orders
Hint

The overcount is constant for every subset.

Answer and reasoning

Each subset has exactly k! internal orders. Every k-element subset can be listed in k! ways.

Choose your next step

Continue to Counting with bijections. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.