Using a generating function for piggy bank problem

Question

A piggy bank contains 45 loonies and 25 toonies. How many ways can the coins be divided so that Jamie gets no loonies, Julie gets no toonies but at least 10 loonies, and Brenda gets an odd number of toonies? Use generating functions to solve the problem. (Note that you are only interested in how many of each type of coin each sibling gets, not which specific coins they get).

So far, my only idea is to split the problem up into 2 generating functions, and then multiply the two answers:

For the loonies, $g(x)=x^{10}(1+x+\cdots+x^{35})(1+x+x^2+\cdots+x^{45}) = x^{10}\frac{(x^{36}-1)}{x-1}\frac{(x^{46}-1)}{x-1}$

And I would do similarly for the toonies. My problem is that I'm not sure if this is even a way to do it, and my biggest problem is that I still don't understand how to find the coefficient of $x^{45}$ in the generating function I have shown, despite reading through all of my notes. Thanks very much in advance for any help!!

Answer 1

I think you have the right idea in dividing the problem into two parts, one for loonies and and for toonies.

For the loonies, we want to count the number of solutions in non-negative integers to $$x_1+x_2+x_3=45$$ subject to $x_1=0$ and $x_2 \ge 10$. The generating function is $$\begin{align} f(x) &= (x^{10} + x^{11} + x^{12} + \dots)(1+x+x^2+\dots)\\ &= x^{10} (1+x+x^2+\dots)(1+x+x^2+\dots)\\ &= x^{10}(1-x)^{-2} \\ &= x^{10} \sum_{i=0}^{\infty}\binom{2+i-1}{i}x^i \end{align}$$ where we used the Binomial Theorem for negative exponents in the last step. From this we see that the coefficient of $x^{45}$ is $$\binom{2+35-1}{35}$$ which solves the problem for the number of ways to distribute loonies. Notice that in the initial formulation of the generating function, we did not use the fact the $x_i \le 45$. Although this is true, it is not necessary, and we end up with a simpler solution if we don't restrict the generating function in that way.

Now for the toonies. We want to count the number of solutions in non-negative integers to $$y_1 + y_2 + y_3 = 25$$ subject to $y_2=0$ and $y_3$ odd. The generating function is $$\begin{align} g(x) &= (1+x+x^2+\dots)(x+x^3+x^5+\dots) \\ &= (1+x+x^2+\dots) \;x\; (1+x^2+x^4+\dots) \\ &= (1-x)^{-1} \;x\; (1-x^2)^{-1} \\ &= \sum_{i=0}^{\infty}x^i \cdot x \cdot \sum_{j=0}^{\infty} x^{2j} \end{align}$$ From the final equation we see that we have one solution for each solution of $i + 2j=24$, or $i = 24-2j$, which has a solution for each of the $13$ values of $j$ with $0 \le j \le 12$. So in the case of the toonies, a generating function didn't really gain us anything; we ended up essentially having to solve the original problem.

The final answer is the product of the solutions of the two sub-problems: $$\boxed{\binom{2+35-1}{35}\times 13}$$

Answer 2

To answer your first question, your method is essentially correct. If you have $a$ ways of distributing the loonies and $b$ ways of distributing the toonies, then you have $ab$ ways of doing both. See also the rule of product and this video.

To answer your biggest question, you know that each loony will go to one of two people, and you know that 10 of unlabeled loonies have a predetermined destination, so the question is how can the other 35 be distributed into two groups? You want to know how many ways there are to write 35 as the sum of two nonnegative integers. Well, there's $0+35$, and $1+34$... surely you can count them all.

More generally, with a generating function you can take the Taylor series expansion centered at 0 to find the coefficient you want, but that's not really reasonable to do by hand with the 45th coefficient.

Answer 3

I would also partition the problem into two parts like you do - but instead of multiplying the generating functions together, I would just solve the problems involving the loonies and the toonies separately, and then multiply the solutions. As you have already began to get a grasp of, trying to find the coefficient of $x^\text{whatever}$ gets pretty messy pretty quickly, so any attempt to minimize the number of polynomials involved helps.

Now, as far as simplifying goes, in my experience you will generally take the following steps:

• First, get your generating function as a product of polynomials
• Simplify the products/sums using the formulas for a geometric series
• Do as much cleaning up, cancellation, grouping together as you can. If there are terms in denominators, you will usually want to write them with negative exponents instead. So, for example, $1/(1-x^2)^3$ becomes $(1-x^2)^{-3}$
• Now, as applicable, you will "unsimplify" by expanding into geometric sums, the binomial theorem or using the generalized binomial theorem:

$$\begin{align} (1-x^r)^{-1} &= \sum_{k=0}^\infty x^{rk} &\text{Geometric sum}\\ (1-x^r)^n &= \sum_{k=0}^\infty \binom n k x^{rk} &\text{Binomial theorem,} \; n \in \Bbb Z^+\\ (1-x^r)^{-n} &= \sum_{k=0}^\infty \binom{n+k-1}{k-1} x^{rk} &\text{Generalized binomial theorem,} \; n \in \Bbb Z^+ \end{align}$$

---

Footnote: NoName mentioned the use of Taylor expansions. That might be reasonable and certainly seems a lot easier than this. I'm just commenting based on what I experienced so far in my combinatorics class this semester, and this is more or less what were taught. So I'm not going to say it's invalid or not: I just wanted to give this heads up as to a possible alternate method.

---

From there, you use the rules of polynomial multiplication to figure out the coefficient for $x^\text{whatever}$. If $(\text{whatever})$ isn't some particular number, i.e. you're just told to find it for $x^r$ in general, you might have to do it by cases since some of the summations might contribute terms and sometimes might not.

As you might imagine, it becomes a mess very fast for even simpler examples. It might prove fruitful to try very basic ones first to get a feel for the matter.