Counting Integer Solutions
On this page
Direct answer
How many ways can 10 identical sweets go to 3 children? C(12, 2) = 66 — and that single stars-and-bars computation, done slowly once, unlocks every x + y + z = n question JEE asks. The base counts: x₁ + ... + x_r = n has C(n − 1, r − 1) positive integer solutions and C(n + r − 1, r − 1) non-negative solutions, read off by choosing divider positions in a row of units and gaps. Bounds are handled by substitution (x ≥ k becomes x' = x − k) and upper limits by inclusion–exclusion: count freely, subtract violations, add back double violations. The variables are labelled throughout — order matters.
What you must remember
- Positive solutions: x₁ + ... + x_r = n with each xᵢ ≥ 1 gives C(n − 1, r − 1); e.g. x + y + z = 10 with all ≥ 1 has C(9, 2) = 36 solutions.
- Non-negative solutions: each xᵢ ≥ 0 gives C(n + r − 1, r − 1); x + y + z = 10 has C(12, 2) = 66.
- Lower bounds: xᵢ ≥ kᵢ → substitute xᵢ = xᵢ' + kᵢ and count non-negative solutions of the reduced equation.
- Upper bounds: x ≤ m is counted by subtracting the x ≥ m + 1 family (via substitution) and re-adding overlaps when two caps can bind together.
- Generating-function view: the count is the coefficient of tⁿ in (1 + t + ... + t^m)^r with caps m, or in (1 − t)^(−r) without — the polynomial bridge between chapters.
- Distinctness discipline: identical objects into distinct boxes → stars and bars; distinct objects into distinct boxes → rⁿ with empty boxes allowed, or inclusion–exclusion when none may be empty; the formulas are not interchangeable.
- Term-count link: the number of distinct terms of (x₁ + ... + x_k)^n is the non-negative count C(n + k − 1, k − 1) — one formula, two chapters.
Sweets, bounds and subtraction
Count non-negative solutions of x + y + z = 10 with x ≤ 3. Free count: C(12, 2) = 66. Violations, x ≥ 4: substitute x = x' + 4, reducing the equation to x' + y + z = 6 with C(8, 2) = 28 solutions. Only one cap applies, so the answer is 66 − 28 = 38.
Now cap both x ≤ 3 and y ≤ 3 to see the machinery finish. Violations of the first: 28; of the second: 28 by symmetry. Double violations, x ≥ 4 and y ≥ 4: substitute both, x' + y' + z = 2, giving C(4, 2) = 6. Inclusion–exclusion assembles it: 66 − 28 − 28 + 6 = 16. Verify independently: (1 + t + t² + t³)² has coefficients 1, 2, 3, 4, 3, 2, 1 across degrees 0 to 6, and each pair (x, y) with x + y ≤ 6 determines z = 10 − x − y ≥ 0, so the count is 1 + 2 + 3 + 4 + 3 + 2 + 1 = 16 ✓. The add-back term is where scripts go wrong — omit it and the answer drops to 10, a distractor option setters place deliberately.
Identical or identical-looking
Main asks the direct formula as a numerical-value question — answers like 36, 66, 38 — dressed as "distribute 10 identical items among 3 boxes". Advanced couples constraints (x ≤ y) or embeds the count in probability, with stars and bars on both favourable and total sides. The traps: using C(n + r − 1, r − 1) for positive solutions — the off-by-one between n + r − 1 and n − 1 gaps is the chapter's most common error; forgetting the add-back term under multiple caps; and treating variables as unlabelled — solutions up to permutation are integer partitions, a different and harder count with no stars-and-bars formula.
Frequently asked questions
How many positive solutions does x + y + z = 10 have?
C(9, 2) = 36 — place 9 gaps between 10 units and choose 2 of them as dividers.
How do I count solutions with an upper bound like x ≤ 3?
Count freely, subtract the solutions with x ≥ 4 via the substitution x = x' + 4, and add back double violations if two caps can bind together.
What is the coefficient link to these counts?
The non-negative count for x₁ + ... + x_r = n is the coefficient of tⁿ in (1 − t)^(−r); caps replace it by (1 + t + ... + t^m)^r.
Do the variables need to be ordered?
Yes — stars and bars counts labelled variables; counting solutions up to permutation is the partition problem, which needs different tools.
How does this connect to multinomial expansions?
The number of distinct terms of (x₁ + ... + x_k)^n equals the non-negative solution count C(n + k − 1, k − 1) of the exponent equations.