Technique

Count integer solutions by fixing one variable

Algebra • Equations • Linear Equations

Statement

To count the solutions of a linear equation in several unknowns over the positive integers, fix one unknown at each of its admissible values in turn, count the solutions of the equation that remains in the other unknowns, and add those counts. The two-unknown case is the base:

x + y = S

with

x, y \geq 1

has exactly

S - 1

solutions, because

x

may be any of

1, 2, \dots, S - 1

and

y = S - x

is then forced.

How to use it

1Work out the range of the variable you fix before counting anything: every other unknown still needs at least $1$ , which is what bounds it.
2Fix the variable that leaves the simplest equation behind - in $x + y + z = n$ any of them will do, in $2 x + y = n$ fix the one with the coefficient.
3The counts usually come out as a run of consecutive integers, so the total is a triangular number $\frac{t ( t + 1 )}{2}$ rather than a sum to be added term by term.
4Check the two ends of the run by hand: the largest value of the fixed variable should leave exactly one solution.

Worked example

How many ordered triples

(x, y, z)

of positive integers satisfy

x + y + z = 5

Step-by-step

1
$x$ can be $1, 2$ or $3$
Why: $y$ and $z$ are each at least $1$ , so $x \leq 5 - 1 - 1 = 3$ .
2
For a fixed $x$ : $y + z = 5 - x$ has $(5 - x) - 1 = 4 - x$ solutions
Why: The two-unknown base case, with $S = 5 - x$ .
3
$x = 1, 2, 3$ give $3, 2, 1$ solutions, and $3 + 2 + 1 = 6$

Answer

6

Watch out

The bound on the fixed variable changes with the constraint: over the non-negative integers

x + y = S

has

S + 1

solutions, not

S - 1

, and ignoring that shift is the usual slip. The count is of ordered tuples, so

(1, 1, 3)

and

(3, 1, 1)

are two solutions; and the method needs every coefficient to be positive, or the admissible range is not a finite run.

Builds on

Integer solutions of

a x + b y = c

Also known as

number of positive integer solutions of x+y+z=n, count integer solutions by cases, fix one variable and sum the cases, number of solutions of a linear equation in positive integers

Count integer solutions by fixing one variable

Statement

Worked example

Appears in past papers

2020 (II)