How many nonnegative solutions are there to the equation x1 + x2 + x3 + x4 = 28 with x1 <= 8, x2 <= 6, x3 <= 12, and x4 <= 9? Use the principle of inclusion exclusion in order to answer the question.

Answer 1

Hi Samantha C.,

Assuming x1, etc. are variable names, and not miswritten exponents!, and that variables are integer only.

I don't know what "inclusion exclusion" refers to; here's how I would approach. This is a real-world type problem -- satisfying a criterion with constrained resources. And it's a little messy, since choices for each variable affect the range available for the others. Probably if you had sufficient incentive, you would approach by bundling the variables as sums, e.g. as (x1 + x2) and as (x3 + x4), then assigning fixed values for each sum, and counting distributions within each, etc., and taking the product of the ways across the groups. And running this through all possible pairs of the groped sums.

BUT -- it may do to first calculate how many possibilities (permutations) for Σ <= 28 (easy enough: add max of each variable = 35, so must "discard" total value of 7 to get down to 28, the ways of doing that are easy to tote up). That is possibilities lost from the universe U of 8x6x12x9 = 5184 .

Next, do the same for Σ <=27 ; this requires discarding total value of 8, again from 5184. The difference between these two calculations is the exact value for the desired answer.

Note that if you have the discards of 7 tabulated, it's quick to figure on to the discards of 8!

-- Cheers, --Mr. d.