Combinatorics path · C09

Before this lesson: Combinations with repetition, Floor and ceiling functions

Your goal: Convert a constrained sum into a counting model with valid bounds.

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: nonnegative integer solutions; bounded stars and bars.

Counting Integer Solutions with Stars and Bars: the key idea

Integer-solution counting starts with the domain of each variable. Nonnegative solutions of x₁+⋯+xᵣ=n are counted by C(n+r−1,r−1), while positive solutions are counted by C(n−1,r−1) when n≥r. Lower bounds are removed by shifting variables. For upper bounds, count forbidden solutions after shifting the violating variable, then use inclusion–exclusion for overlaps. If the target sum becomes negative after a shift, that forbidden case contributes zero.

A worked example

Count nonnegative solutions of x+y+z=7 with x≤3.

Without the bound there are C(9,2)=36. Forbidden x≥4 gives u=x−4≥0 and u+y+z=3, counted by C(5,2)=10. Subtract: 36−10=26.

Your turn: change one thing

Count positive solutions of x+y+z=7.

Try this on paper before opening the explanation.

Compare your reasoning

Set x=u+1,y=v+1,z=w+1. Then u+v+w=4, giving C(6,2)=15.

Pause and check

A trap to avoid: Applying stars and bars while ignoring upper bounds.

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 nonnegative solutions of x+y+z=5 with each variable at most 3.

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

There are C(7,2)=21 unrestricted solutions. A specified variable at least 4 leaves a sum of 1 and has C(3,2)=3 solutions. There are three choices of violating variable. Two variables cannot both be at least 4 because the total is only 5. Thus the answer is 21−3·3=12.

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. For positive variables, what shift gives nonnegative variables?

Foundation

  1. xᵢ=yᵢ−1
  2. xᵢ=2yᵢ
  3. No shift is possible
  4. xᵢ=yᵢ+1
Hint

Subtract the minimum allowed value.

Answer and reasoning

xᵢ=yᵢ+1. Then yᵢ=xᵢ−1≥0.

2. An upper bound x≤3 is violated when what holds for integer x?

Foundation

  1. x≤2
  2. x=0
  3. x≥4
  4. x≥3
Hint

Use the next integer after 3.

Answer and reasoning

x≥4. Forbidden integer values start at 4.

3. Nonnegative solutions of x+y+z=7 without bounds: count?

Core

  1. 21
  2. 28
  3. 15
  4. 36
Hint

Use C(9,2).

Answer and reasoning

36. Seven stars and two bars give 36 arrangements.

4. Positive solutions of x+y+z=7: count?

Core

  1. 10
  2. 15
  3. 36
  4. 21
Hint

Reserve one unit for each variable.

Answer and reasoning

15. The remaining sum 4 gives C(6,2)=15.

5. Nonnegative solutions of x+y+z=7 with x≤3: count?

Stretch

  1. 36
  2. 10
  3. 16
  4. 26
Hint

Subtract x≥4 cases.

Answer and reasoning

26. 36−C(5,2)=36−10=26.

6. For x+y+z=5, can two variables both be at least 4?

Stretch

  1. No
  2. Yes, once
  3. Yes, three times
  4. Only if one is negative despite nonnegativity
Hint

Their sum would already exceed 5.

Answer and reasoning

No. Two such variables contribute at least 8, impossible with all variables nonnegative.

7. A nonnegative integer variable may equal what?

Foundation

  1. Only a positive integer
  2. Only a negative integer
  3. Only a prime
  4. 0
Hint

Nonnegative includes zero.

Answer and reasoning

0. The domain is 0,1,2,… .

8. Nonnegative solutions of x+y=5: count?

Core

  1. 4
  2. 6
  3. 5
  4. 10
Hint

Choose x from 0 through 5.

Answer and reasoning

6. Each choice determines y=5−x.

9. Why subtract overlaps carefully when several upper bounds are violated?

Stretch

  1. Violations are always disjoint
  2. All variables become negative
  3. Upper bounds never overlap
  4. One solution may violate several bounds
Hint

Apply inclusion–exclusion.

Answer and reasoning

One solution may violate several bounds. Subtracting each forbidden set separately removes overlap solutions too many times.

Choose your next step

Continue to Binomial expansions and generating functions. 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.