Stuck on Generating Functions

Question

1) Determine how many ways Brian, Katie, and Charlie can split a 50 dollar dinner bill such that Brian and Katie each pay an odd number of dollars and Charlie pays at least 5 dollars .

2) Determine how many ways I can distribute 80 candies to 3 kids, such that:

The first kid receives an arbitrary number of candies (possibly 0).

The second kid receives an even positive number of candies.

The third kid receives 0, 2, or 5 candies.

Every candy is distributed.

I have been trying to use generating functions to get the answer for these problems, but I am stuck. Any help is greatly appreciated!

Answer 1

For 1, we want to solve the equation $$x_1+x_2+x_3 = 50$$ where $x_1,x_2$ are odd positive numbers, and $x_3 \geq 5$.

Now by subtitution of $x_1,x_2$ with $y_1 = x_1 - 1, y_2 = x_2 - 1$ and $x_3$ with $y_3 = x_3 - 5$ we get the equivalent equation: $$y_1 + y_2 + y_3 = 43$$ where $y_1, y_2 \geq 0$ are even and $y_3 \geq 0$.

Now, note that since $y_1,y_2$ are even, $y_3$ has to be odd, so we can replace it with $z_3 + 1$ when $z_3$ is even.

So we finally get the equation: $$y_1 + y_2 +z_3 = 42 $$ with all it's variables even non negative, which is equivalent to the equation: $$ k_1 + k_2 +k_3 =21 $$ where $k_i$ are non-negative integers with no constraints, this is solved easily by $$CC_3^{21} = {21+3-1\choose 21} $$

For 2, split into cases determine the number of candies that the third kid get ($0,2$ or $5$) and use the same technique...

Answer 2

You have to write the constraints in terms of a generation function. So Brian and Katy both get the generating functions $b(x) = k(x) = x + x^3 + x^5 + \ldots x^{2k+1} + \ldots = \sum_{i=0}^{\infty} x^{2i+1}$, which only has the odd powers of $x$, while Charlie has $c(x) = x^5 + x^6 + x^7 + \ldots = \sum_{i+0}^{\infty}x^{5+i}$, which has all powers greeter than or equal to $5$. So the question asks what the coefficient of $x^{50}$ is in the product $b(x)k(x)c(x)$ (as this power only occurs if we take some power of $x$ from each of the functions, and these powers are chosen to obey the constraints of the problem).

We can write $b(x)$ (and $k(x)$) as $x \cdot \sum_{i=0}^{\infty} (x^2)^i = \frac{x}{1-x^2}$ using the geometric series. $c(x) = x^5 \sum_{i=0}^{\infty}x^i = \frac{x^5}{1-x}$. Now you can compute the product and try to find the power series for it (using partial fractions, e.g.), and then see what $x^{50}$ is.

The second problem is similar, where the first kid has generating function $1+x+x^2+\ldots+ = \sum_{i=0}^{\infty} x^i = \frac{1}{1-x}$, the second has $x^2 + x^4 + \ldots + = \sum_{i=1}^{\infty} x^{2i} = x^2 \sum_{i=0}^{\infty} (x^2)^i = \frac{x^2}{1-x^2}$, and the third has $(1+x^2+x^5)$. Now we are looking for the coefficient of $x^{80}$, clearly.