The Basic Problem
Suppose, we have a Linear Algebraic Equation, X1 + X2 + X3 = 5. Here the values of X1, X2 and X3 can be non-negative integers. We want to know in how many ways we can assign values to X1, X2 and X3 so that the summation is 5.
We can consider this problem as dividing 5 objects among 3 persons. And below are some possible ways to do it — 
Here by O the objects are being represented and | represents partition. As the objects are divided among 3 persons we need 2 partitions which is pretty clear from the partitioning instances above.
We can finalize this problem as simple combinatorial problem of number of ways of arranging 7 objects where 5 are of first kind and the other 2 are of second kind. And the answer is 
So if we have n objects in total and we want to divide those among k persons, we can do that in 
ways.
Adding Upper Bound
Now let's modify the above problem by a bit. Let's set upper bounds on the terms of the above equation. Suppose, X1≤2, X2≤ 1 and X3≤ 3 and we want to know the number of solutions to the equation. In the result we calculated above there are some solutions where X1 > 2 or X2 > 1 or X3 > 3. If we can figure out the number of invalid solutions and deduct it from the above result then we can get our desired result. Let's first figure out the number of solutions where X1 > 2. We can simply deduct 3 from the total number of objects and give those to X1 and then divide the rest of the objects among all the terms. In this way X1 obviously exceeds its bound of 2. So solving the equation X1 + X2 + X3 = 2, we get the number of solutions where X1 exceeds its bound. Following the similar way we can find out the number of solutions where X2 and X3 exceeds their bounds. Then we can deduct all of these invalid solutions from the above result to remove the invalid results.
Now we've actually removed some invalid solutions more than once. When finding out the number of solutions where X1 exceeds 2 and solving X1 + X2 + X3 = 2, we've also removed the solutions where X2 exceeds 1. And then again we've removed it separately for X2. So same invalid configuration is actually removed twice and we have to add the number of solutions where both X1 and X2 exceeds their bounds to the above result. This is actually a classical Inclusion-Exclusion problem. If we choose odd number of terms and find out the numbers of solutions where they exceed bounds, we deduct it from the result and if we choose even number of terms and find out the numbers of solutions where they exceed bounds, we add it to the result. Finally we get the number of solutions where all the terms are under the bound.
Adding Lower Bound
Lastly consider that some lower bounds are set on the terms of the equation. Suppose, X1 ≥ 1, X2 ≥ 0 and X3 ≥ 2 and we want to know the number of solutions to the equation. If you observe carefully you will notice that if we decrease the particular upper bounds by their lower bounds and reset them and also decrease the total number of objects by the summation of lower bounds then the problem is just similar to the previous problem of finding number of solutions with upper bounds. Now the number of solutions to the newly set equation is actually the numbers of solutions to a Linear Algebraic Equation with both upper and lower bounds.
Practice Problems
- Problem Makes Problem This problem is quite similar to the basic problem discussed above.
- Cricket Ranking This problem is quite similar to the problem of solving Linear Algebraic Equation with upper and lower bounds discussed above.
- Toph Biswa the Digital Gutibaj In this problem you also need to find the number of solutions to a Linear Algebraic Equation with upper and lower bounds. But here you can use as many terms as you want. So just choose some terms at each step and then solve for them. You also need to multiply the answer at each step with the factorial of number of terms chosen as the requirement of the problem. Here the number of objects can be as large as 1012 but the number of terms is at most 10. You can simply iterate to find out the nCr value.
