In how many ways can you divide bonuses between employees?

Question

How many ways are there to divide 33 000 USD between 22 employees of a company (including 1 president, 1 vice-chairman and 20 normal employees), if a normal employee can get 1000 or 1500 USD, whereas both president and vice-chairman can get: 0, 1500 or 3000 USD?

Answer 1

Assuming we have to distribute all \$33,000, the fact that each normal employee gets \$1,000 or \$1,500 means we have to distribute at least \$3,000 to the executives.

Since there are three ways to distribute \$3,000 to our executives, that leaves exactly \$30,000 to distribute to the employees. That can happen only 1 way, every one gets \$1,500.

Since there are two ways to distribute \$4,500 to our executives, that leaves $\binom{20}{17}$ ways to distribute 3 \$1,000 bonuses and 17 \$1,500 bonuses amongst the 20 employees.

Since there is only one way to distribute \$6,000 to our executives, that leaves $\binom{20}{14}$ ways to distribute 6 \$1,000 bonuses and 14 \$1,500 bonuses amongst the 20 employees.

Thus the total is $$ 3\binom{20}{20}+2\binom{20}{17}+\binom{20}{14}=3+2280+38,760=41,043. $$

Answer 2

You tagged this as generating functions, so I'll provide the generating function as well. Since each normal employee can get 1000 or 1500, we have $e(x) = (x^{1000} + x^{1500})$. There are 20 such employees, so we consider $(e(x))^{20}$. Now the executives can get $0, 1000, 1500$, so we have $f(x) = (1 + x^{1500} + x^{3000})$. There are two executives, so we consider $(f(x))^{2}$. Now our generating function is $g(x) = (e(x))^{20} * (f(x))^{2}$. You can factor $x^{20000}$ out from $(e(x))^{20}$, which leaves you looking for the coefficient of $x^{13000}$ as opposed to $x^{33000}$.