Combinatorics path · C14

Before this lesson: Combinations with repetition, Dividing objects into fixed-size groups, Inclusion–exclusion

Your goal: Choose the model from distinguishability and occupancy conditions.

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.

Names you may know: balls into boxes; distribution problems.

Distributing Objects into Boxes: the key idea

Before counting distributions, decide whether the objects and boxes are distinct and whether empty boxes are allowed. Distinct objects in k labelled boxes give knk^{n} assignments. Identical objects in labelled boxes give stars and bars. Distinct objects in unlabelled nonempty boxes give set partitions; do not divide knk^{n} by k! when empty boxes or symmetries cause unequal multiplicities. Identical objects in unlabelled boxes give integer partitions, described by nonincreasing occupancy sizes. “At least one in each box” changes all four models.

A worked example

Put four distinct balls into two labelled boxes, with neither box empty.

There are 2⁴=16 assignments. Exclude the two assignments with all balls in one box, leaving 14.

Your turn: change one thing

Put four identical balls into two labelled nonempty boxes.

Try this on paper before opening the explanation.

Compare your reasoning

The positive counts x+y=4 are (1,3),(2,2),(3,1), so there are 3 distributions. If boxes are unlabelled, (1,3) and (3,1) coincide, leaving 2.

Pause and check

A trap to avoid: Using one formula for all combinations of identical and distinct objects or boxes.

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

Count partitions of a nonempty n-element set into at most two unlabelled nonempty blocks.

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

Label two boxes temporarily, allowing one empty. There are 2n2^{n} assignments. Exchanging labels has no fixed assignment when the underlying set is nonempty, so every unlabelled partition into one or two blocks is counted twice. The result is 2n−12^{n-1}. Exactly two blocks gives 2n−1−12^{n-1}-1.

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. n distinct objects in k labelled boxes, empties allowed: count?

Foundation

  1. k!
  2. knk^{n}
  3. C(n+k−1,k−1) always
  4. n!
Hint

Each object independently chooses a box.

Answer and reasoning

knk^{n}. There are k choices for each of n distinct objects.

2. Identical objects in labelled boxes are described by what?

Foundation

  1. Only the largest box
  2. Occupancy counts
  3. Permutations of the objects
  4. Names for each object
Hint

Object identities do not matter.

Answer and reasoning

Occupancy counts. A vector of nonnegative counts completely describes the distribution.

3. Four distinct balls into two labelled nonempty boxes: count?

Core

  1. 7
  2. 3
  3. 14
  4. 16
Hint

Remove the two all-in-one-box assignments.

Answer and reasoning

14. 2⁴−2=14.

4. Four identical balls into two labelled nonempty boxes: count?

Core

  1. 14
  2. 2
  3. 4
  4. 3
Hint

List positive count pairs summing to 4.

Answer and reasoning

3. (1,3),(2,2),(3,1) give three.

5. Four identical balls into two unlabelled nonempty boxes: count?

Stretch

  1. 2
  2. 3
  3. 7
  4. 14
Hint

Ignore the order of occupancy sizes.

Answer and reasoning

2. The possibilities are {1,3} and {2,2}.

6. Why must object and box labels be specified?

Stretch

  1. They affect only the diagram
  2. They never affect the answer
  3. They force all boxes nonempty
  4. They determine which outcomes are considered different
Hint

Counting needs a precise equality rule for outcomes.

Answer and reasoning

They determine which outcomes are considered different. Changing distinguishability can change the answer from assignments to compositions or partitions.

7. For identical objects, exchanging two of them changes the outcome how?

Foundation

  1. It empties a box
  2. It changes the number of objects
  3. It does not change it
  4. It always creates a new outcome
Hint

Identical objects have no individual labels.

Answer and reasoning

It does not change it. Only the occupancy pattern matters.

8. Three distinct balls in two labelled boxes, empties allowed: count?

Core

  1. 8
  2. 6
  3. 4
  4. 3
Hint

Each ball has two choices.

Answer and reasoning

8. 2³=8.

9. Why is blindly dividing knk^{n} by k! unsafe when empty boxes are allowed?

Stretch

  1. Relabelling can repeat assignments with empty boxes
  2. knk^{n} never counts assignments
  3. Factorials are not integers
  4. All boxes must contain one object
Hint

The label action may have stabilisers.

Answer and reasoning

Relabelling can repeat assignments with empty boxes. Permuting empty boxes may leave an assignment unchanged, so the multiplicity need not be k!.

Choose your next step

Continue to Pigeonhole principle. 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.