2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Why would generating functions be used for either? $\endgroup$ – zibadawa timmy Sep 14 '14 at 4:00
2
$\begingroup$

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...

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.