Number of ways to distribute 100 identical chairs among 4 different rooms

Question

In how many ways can 100 identical chairs be divided among 4 different rooms so that each room will have 10,20,30,40 or 50 chairs?

I'm having problems coming up with the generating function for this question.

The answer given is 68.

Answer 1

Others already have given hints, but here is a generating function approach.

For every room, so $4$ times, you have to choose whether you place $1$, $2$, $3$, $4$ or $5$ chairs in it. This translates to a generating function with $4$ factors, because you have to choose a term from every factor. Because your possibilities are the same for every room, every factor is the same, so $G(x)=[f(x)]^4$ for some $f(x)$.

Because an amount of $n$ chairs corresponds with a term $x^n$, it follows that $f(x)=x+x^2+x^3+x^4+x^5$, because these are the possibilities to choose from. Notice that there is no $1$ in the function, because you are not allowed to place zero chairs in a room, also there is no $x^6$, because you are not allowed to place six chairs in a room.

Therefore the generating function is $(x+x^2+x^3+x^4+x^5)^4$. The coefficient for $x^{10}$ is indeed $68$ (Link). The coefficient from $x^{10}$ answers the question, because you have a total of $10$ chairs, so adding the chairs gives $10$, or multiplying the terms gives a tenth power.

Answer 2

The problem can also be done without generating functions.

After dividing by $10$ we need to find the number of ordered quadruples of numbers in $\{1,2,3,4,5\}$ that add to $10.$ This is equivalent to the number of ordered quadruples of numbers in $\{0,1,2,3,4\}$ that add to $6.$ If we drop the restriction that the numbers be no greater than $4,$ we can use stars-and-bars to find that the number of quadruples is $\binom{6+3}{3}=84.$

Now we need to subtract the number of quadruples that contain a number greater than or equal to $5.$ Such a quadruple contains exactly one such number, given that the numbers add to $6.$ We represent a quadruple in which the first number is greater than or equal to $5$ by $(5,0,0,0)+q,$ where $q$ is an ordered quadruple of non-negative integers that add to $1.$ We represent quadruples where the number greater than or equal to $5$ is in positions $2,$ $3,$ or $4$ similarly. Since there are four choices of position, and four choices of $q,$ there are $16$ quadruples containing a number greater than or equal to $5.$ This gives the desired result.

Added: I should add that the calculation above can be seen in the generating function approach. Using the expression in Thijs' answer, we get $$ \begin{aligned} \left[x^{10}\right]\left(x+x^2+x^3+x^4+x^5\right)^4&=\left[x^6\right]\left(1+x+x^2+x^3+x^4\right)^4\\ &=\left[x^6\right]\left(\frac{1-x^5}{1-x}\right)^4\\ &=\left[x^6\right]\frac{1-4x^5}{(1-x)^4}\\ &=\left[x^6\right]\left(1-4x^5\right)\sum_{j=0}^\infty\binom{-4}{j}(-1)^jx^j\\ &=1\cdot\binom{-4}{6}(-1)^6-4\cdot\binom{-4}{1}(-1)^1\\ &=\binom{9}{6}-4\binom{4}{1}. \end{aligned} $$ The notation $[\text{blah}]$ means "coefficient of blah". In the third line we discarded numerator terms of order $x^{10}$ or higher. In line four, we used the generalized binomial theorem to expand the denominator. In line six, we rewrote the binomial coefficients $\binom{n}{r}$ with negative $n$ in terms of positive $n.$

If one traces through the steps of this calculation, one sees that they correspond with the steps of the previous calculation.