Counting the number of integer solutions of the following indeterminate equation is an important pattern in solving intermediate level counting problems. $$x_1+x_2+\cdots + x_k = n$$
This is because many counting problems can be modelled as solutions to such an equation. Two typical examples are shown below. Both of them are AMC10/12 problems.
This pattern has some common variations:
- all the $x_i$ are positive integers
- all the $x_i$ are non-negative integers
- some $x_i$ are positive integers, some are non-negative integers
- other types of restrictions imposed on $x_i$. For example, $1\le x_i \le 6$ if the $x_i$ represent readings from dice rolling
We have already discussed
- Solve the (1) above using the cut the rope technique.
- Solve the (2) above using the knives and balls technique.
- How to solve (3) above will be discussed in this lesson
- (4) above is a more general case which calls for a general solution - generating function (see further reading below)
The key to solve type (3) question above is to use the substitution method. If $x$ is positive, then $y=x-1$ must be non-negative. Similarly, if $x$ is non-negative, then $y=x+1$ must be positive. By using this technique, we can then translate all $x_i$ to be either all positive or all non-negative.
Please study the $1^{st}$ example (#4768) before watching the tutorial video.
Let $n \ge k$ are two positive integers. Given function $x_1+x_2+\cdots + x_k =n$,(4768)
A parking lot has $16$ spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires $2$ adjacent spaces. What is the probability that she is able to park?(790)
For some particular value of $N$, when $(a+b+c+d+1)^N$ is expanded and like terms are combined, the resulting expression contains exactly $1001$ terms that include all four variables $a, b,c,$ and $d$, each to some positive power. What is $N$?(2884)
Generating function is an advanced technique with wide application, not limited to counting. It will not be required to solve AMC/AIME level problems, thus will not be covered in this course. Interested readers can take the course: 25 - Advanced Combinatorics.