Today, I have solved a beautiful problem (link). So, basically, the problem is counting the number of solution for this equation:
x1 + x2 + … + xn = A
With A is constant and x1 … xn are integer, and there are different constraints for each xi: 0 <= xi <= ci.
Without those additional constraints, this problem is the famous stars and bars problem. So basically, imagine that we have A stars on a row, and we need to put (n – 1) bars to separate those stars, how many way we can put our bars? See the connection? (Hint: notice that after we put (n – 1) bars, we separate those stars into n sections, which has zero or more stars)
- The answer for above question is simple, add n – 1 stars into those A stars, the problem become, finding the number of ways to pick n – 1 stars from A + n – 1 stars, which basically is C (A + n – 1, n – 1)
Go back to the original problem, so, after getting the answer without those constraints, our job now is only to subtract number of solution violated the constraints. But how do we find that number?
Let’s start by assuming that we only violated the constraint of the first variable x1, which is, x1 > c1. We define y1 = x1 – c1 – 1.
So, the problem becomes, finding all solutions which satisfy following conditions:
y1 + x2 + … + xn = A – c1 – 1.
And, 0 <= y1 <= c1, 0 <= xi <= ci.
Ah ha!, at that moment, we realize that this problem can be solved by applying Inclusion-exclusion principle.
So, the final result X is:
X = C (A + n – 1, n – 1) – C(A + n – 1 – c1 – 1, n – 1) – C (A + n – 1 – c2 – 1, n – 1) …. + C(A + n – 1 – c1 – c2 – 2, n – 1) + ….
trungpham90 