### J-C's blog

By J-C, history, 3 years ago, , ### The Basic Problem

Suppose, we have a Linear Algebraic Equation, X 1 + X 2 + X 3 = 5. Here the values of X 1, X 2 and X 3 can be non-negative integers. We want to know in how many ways we can assign values to X 1, X 2 and X 3 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.

Now let's modify the above problem by a bit. Let's set upper bounds on the terms of the above equation. Suppose, X 1≤2, X 2≤ 1 and X 3≤ 3 and we want to know the number of solutions to the equation. In the result we calculated above there are some solutions where X 1 > 2 or X 2 > 1 or X 3 > 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 X 1 > 2. We can simply deduct 3 from the total number of objects and give those to X 1 and then divide the rest of the objects among all the terms. In this way X 1 obviously exceeds its bound of 2. So solving the equation X 1 + X 2 + X 3 = 2, we get the number of solutions where X 1 exceeds its bound. Following the similar way we can find out the number of solutions where X 2 and X 3 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 X 1 exceeds 2 and solving X 1 + X 2 + X 3 = 2, we've also removed the solutions where X 2 exceeds 1. And then again we've removed it separately for X 2. So same invalid configuration is actually removed twice and we have to add the number of solutions where both X 1 and X 2 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.

Lastly consider that some lower bounds are set on the terms of the equation. Suppose, X 1 ≥ 1, X 2 ≥  0 and X 3 ≥  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

Code
• Cricket Ranking This problem is quite similar to the problem of solving Linear Algebraic Equation with upper and lower bounds discussed above.
Code
• 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.
Code math, Comments (4)
 » Nice! Always good to see blog posts like these!I'd add that sometimes it's worth considering a DP solution when n is too large for inclusion-exclusion and X i are not too big.
 » 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 what do you mean by choose term ?
 » Thanks man, It really helped!One more Practice Problem you can add if you want- https://atcoder.jp/contests/abc087/tasks/abc087_b
 » Another problem for exercise 1096E - The Top Scorer