Combinatorics Question Principle of Inclusion-Exclusion, Stars and Bars

Question

There are five counties in California: San Mateo, San Francisco, Alameda, Marin, and Napa which are to receive 173 million in relief funding (in integer multiples of millions of dollars). In how many ways can this distribution be made, assuming that each county receives at least $1 million, San Mateo county receives at most 10 million, and San Francisco county receives at most 30 million.

Here's my thought process, use principle of inclusion-exclusion on the complement. In order to compute the complement we find the # of ways that either San Mateo county receives more than 10 million or SF receives more than 30 million. We can compute each individually and then subtract when both occur to account for double counting (both San Mateo and SF receive more than their restricted amount).

Since we are computing the complement we are subtracting from the total number, this problem boils down to: $a_1+a_2+a_3+a_4+a_5 = 168$. For the basic restriction of 1 million preallocated to each county. This means the total number of ways is $\binom{172}{4}$ by stars and bars.

Now lets compute when San Mateo receives more than 10 million: We preallocate 1 to each $a_1,a_2,a_3,a_4$ and $10$ to $a_5$ so we get: $b_1+b_2+b_3+b_4+b_5 = 159$ so $\binom{163}{4}$

Now lets compute when San Fran receives more than 30 million: We preallocate 1 to each $a_1,a_2,a_3,a_5$ and $30$ to $a_4$ so we get: $b_1+b_2+b_3+b_4+b_5 = 139$ so $\binom{143}{4}$

Now lets compute when San Mateo receives more than 10 million and SF more than 30 million: We preallocate 1 to each $a_1,a_2,a_3$ and $30$ to $a_4$ and $10$ to $a_5$ so we get: $b_1+b_2+b_3+b_4+b_5 = 130$ so $\binom{134}{4}$

This means by inclusion-exclusion principle we have $$\binom{172}{4} - (\binom{163}{4}+\binom{143}{4} - \binom{134}{4})$$ $\blacksquare$

Is my work correct?

Answer 1

You have handled not handled the restrictions correctly since allocations are in units of millions of dollars. Therefore, if San Mateo county receives more than $10$ million dollars, it must receive at least $11$ million dollars. Similarly, if San Francisco county receives more than $30$ million dollars, it must receive at least $31$ million dollars. With that in mind, let's proceed.

Let $x_i$ be the number of millions received by the $i$th county in an alphabetical list of the counties. Since the five counties are to be allocated a total of $173$ million dollars in units of millions of dollars, with each county receiving at least one million dollars, $$x_1 + x_2 + x_3 + x_4 + x_5 = 173 \tag{1}$$ is an equation in the positive integers. Using your idea of preallocating a million dollars to each county, we let $x_i' = x_i - 1$, $1 \leq i \leq 5$. Then each $x_i'$ is a nonnegative integer. Substituting $x_i' + 1$ for $x_i$, $1 \leq i \leq 5$, and simplifying yields $$x_1' + x_2' + x_3' + x_4' + x_5' = 168 \tag{2}$$ Since you prefer to work with nonnegative integers, equation $2$ has $$\binom{168 + 5 - 1}{5 - 1} = \binom{172}{4}$$ solutions, as you found.

If San Francisco county receives more than $30$ million dollars, it must receive at least $31$ million dollars. We have already given San Francisco county a million dollars. Therefore, the restriction that San Francisco county be given at most $30$ million dollars is violated if San Francisco receives at least $30$ million additional dollars. Suppose that San Francisco county does receive more than $30$ million dollars. Then $x_4' \geq 30$. Let $x_4'' = x_4' - 30$. Then $x_4''$ is a nonnegative integer. Substituting $x_4'' + 30$ for $x_4'$ in equation $2$ and simplifying yields $$x_1' + x_2' + x_3' + x_4'' + x_5' = 138 \tag{3}$$ which is an equation in the nonnegative integers with $$\binom{138 + 5 - 1}{5 - 1} = \binom{142}{4}$$ solutions.

If San Mateo county receives more than $10$ million dollars, it must receive at least $11$ million dollars. We have already given San Mateo a million dollars. Therefore, the restriction that San Mateo county be given at most $10$ million dollars is violated if we give San Mateo county at least $10$ million additional dollars. Suppose San Mateo receives at least $11$ million dollars. Then $x_5' \geq 10$. Let $x_5'' = x_5' - 10$. Then $x_5''$ is a nonnegative integer. Substituting $x_5'' + 10$ for $x_5'$ in equation $2$ and simplifying yields $$x_1' + x_2' + x_3' + x_4' + x_5'' = 158 \tag{4}$$ which is an equation in the nonnegative integers with $$\binom{158 + 5 - 1}{5 - 1} = \binom{162}{4}$$ solutions.

If San Francisco county receives at least $31$ million dollars and San Mateo county receives at least $11$ million dollars, then subsitute $x_4'' + 30$ for $x_4'$ and $x_5'' + 10$ for $x_5'$ in equation $2$ and simplify to obtain $$x_1' + x_2' + x_3' + x_4'' + x_5'' = 128 \tag{5}$$ which is an equation in the nonnegative integers with $$\binom{128 + 5 - 1}{5 - 1} = \binom{132}{4}$$ solutions.

By the Inclusion-Exclusion Principle, the number of admissible allocations of $173$ million dollars to the five counties is $$\binom{172}{4} - \binom{142}{4} - \binom{162}{4} + \binom{132}{4}$$