Inclusion–Exclusion Identical Computers Problem

Question

Find the number of ways to distribute 19 identical computers to four schools, if School A must get at least three, School B must get at least two and at most five, School C get at most four, and School D gets the rest.

a) Solve using inclusion-exclusion

b) Solve using generating functions

I've been tackling this question for a couple of days and I am pretty confused where to even start.

So I bet the answer is in the form $x_1 + x_2 + x_3 + x_4 = 19$, where $x_1 \ge 3; 2 \le x_2 \le 5; x_3 \le 4$ and $x_4$ is whatever is left over.

And then I get confused. I've looked all over the internet, through textbooks and I'm not getting anywhere. Any help would be appreciated, thank you.

Answer 1

Addendum to the generating function part of the answer of @callculus. Assuming WA is not available, it's not too hard to calculate the coefficient by hand. In order to do so it's convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. This way we can write e.g. \begin{align*} [x^j](1+x)^n=\binom{n}{j} \end{align*}

We obtain \begin{align*} [x^{19}]&\left(\sum_{k=3}^{17}x^k\right)\left(\sum_{k=2}^5x^k\right)\left(\sum_{k=0}^4x^k\right)\left(\sum_{k=0}^{14}x^k\right)\\ &=[x^{19}]\left(\sum_{k=0}^{14}x^{k+3}\right)\left(\sum_{k=0}^3x^{k+2}\right)\frac{1-x^5}{1-x}\cdot\frac{1-x^{15}}{1-x}\tag{1}\\ &=[x^{19}]x^3\frac{1-x^{15}}{1-x}\cdot x^2\frac{1-x^4}{1-x}\cdot\frac{1-x^5}{1-x}\cdot\frac{1-x^{15}}{1-x}\tag{2}\\ &=[x^{14}]\left(1-x^{15}\right)^2\left(1-x^4\right)\left(1-x^5\right)\sum_{n=0}^{\infty}\binom{-4}{n}(-x)^n\tag{3}\\ &=[x^{14}]\left(1-x^4\right)\left(1-x^5\right)\sum_{n=0}^{\infty}\binom{-4}{n}(-x)^n\tag{4}\\ &=[x^{14}](1-x^4-x^5+x^9)\sum_{n=0}^{\infty}\binom{n+3}{3}x^n\tag{5}\\ &=\left([x^{14}]-[x^{10}]-[x^9]+[x^5]\right)\sum_{n=0}^{\infty}\binom{n+3}{3}x^n\tag{6}\\ &=\binom{17}{3}-\binom{10}{3}-\binom{9}{3}+\binom{8}{3}\tag{7}\\ &=680-286-220+56\\ &=230 \end{align*}

Comment:

• In (1) we shift the index of $k$ to start from $0$ and apply the finite geometric series formula.

• In (2) we apply the finite geometric series formula again.

• In (3) we use the linearity of the coefficient of operator and apply the rule $$[x^{n-m}]A(x)=[x^n]x^mA(x)$$ We also use the binomial series expansion of $\frac{1}{(1-x)^4}$.

• In (4) we observe that we can replace the binom $(1-x^{15})$ with $1$, since multiplication with $x^{15}$ does nothing contribute to the coefficient of $x^{14}$.

• In (5) we use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

• In (6) we apply the rule $[x^{n-m}]A(x)=[x^n]x^mA(x)$ again.

• In (7) we select the coefficients accordingly.

Answer 2

Let $A,B,C$ be the count of identical computers distributed to the relevant schools (and school D gets $19-A-B-C$).   Using the principle of inclusion and exclusion to avoid over-counting, you want the measure: $$\begin{align} & \lvert\{3{\leq}A~,2{\leq}B{\leq}5~,C{\leq}4\}\rvert \\[1ex] =~&\lvert\{A{\geq}3\}\cap(\{B{\geq}2\}\setminus\{B{\geq}6\})\cap(\{C{\geq}0\}\setminus\{C\geq 5\})\rvert \\[1ex] =~&\lvert \{A{\geq}3,B{\geq}2,C{\geq}0\}\lvert -\lvert\{A{\geq}3, B{\geq}6,C{\geq}0\}\rvert-\lvert\{A{\geq}3,B{\geq}2,C{\geq}4\}\rvert+\lvert\{A{\geq}3,B{\geq}6,C{\geq}5\}\rvert \\[1ex] =~&\mu(3,2,0)-\mu(3,6,0)-\mu(3,2,5)+\mu(3,6,5)\end{align}$$

Where $\mu(a,b,c)$ is the count the distinct ways to distribute 19 identical computers to four schools such that the relevant schools get at least $a,b,c$ respectively.   Can you evaluate?   (Hint: use the "stars and bars" method.)

$$\begin{align} \mu(a, b, c) ~=~& \boxed{\large ?} & \mbox{iff }0\leq a,0\leq b,0\leq c, a+b+c\leq 19 \end{align}$$

---

The generating function is $(x_{\small A}+x_{\small B}+x_{\small C}+1)^{19}$ but you want the count of occurrence of terms $x_{\small A}^ax_{\small B}^bx_{\small C}^c$ where $(3\leq a) ~\wedge~ (2\leq b\leq 5)~\wedge~(c\leq 4)$ .

Answer 3

The generating function for school A,B,C and D are

$ \sum_{k=3}^{\infty }x^k, \sum_{k=2}^{5 }x^k , \sum_{k=0}^{4}x^k,\sum_{k=0}^{\infty }x^k$

I think the limits are self explaining. For all four schools together the generating function is

$ \sum_{k=3}^{\infty }x^k\cdot \sum_{k=2}^{5 }x^k \cdot \sum_{k=0}^{4}x^k\cdot \sum_{k=0}^{\infty }x^k$

Only 19 compters available. Therefore we have an upper bound of 19 for the schools A,B and D. This upper bound can be reduced for every school due the sum of the lower bound of the other schools.

$ \sum_{k=3}^{17 }x^k\cdot \sum_{k=2}^{5 }x^k \cdot \sum_{k=0}^{4}x^k\cdot \sum_{k=0}^{14}x^k$

If you add the upper bound of school A and the lower bound of the other schools you´ll get 19. Similar for school D.

I don´t see no more simplification for this term. We need to find the coefficient of $x^{19}$.

Using the calculator we see that the coefficient is $230$.

Thus there are 230 ways to distribute 19 identical computers to the four schools.