Generating functions word problem(balloons)

1.7k Views Asked by At

Find the generating function for the number of ways to create a bunch of n balloons selected from white, gold, and blue balloons so that the bunch contains at least one white balloon, at least one gold balloon, and at most two blue balloons. How many ways are there to create a bunch of 10 balloons subject to these requirements?

So I have $$\frac{x^2}{(1-x)^2} \cdot \frac{(1-x^3)}{1-x}$$ and I have no idea where to go from here. Have a test on this material in the morning so any help would be greatly appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

You have $$(x^2-x^5)\frac{1}{(1-x)^3}$$

We have the generating function $$\frac{1}{(1-x)^3}=\sum_{n\ge 0} {n+2\choose 2}x^n$$

Multiply by $x^k$ gives $$x^k\frac{1}{(1-x)^3}=\sum_{n\ge 0}{n+2\choose 2}x^{n+k}$$

We reindex using $m=n+k$ to get $$x^k\frac{1}{(1-x)^3}=\sum_{m\ge k}{m-k+2\choose 2}x^m$$

We do this twice, for $k=2$ and $k=5$, then subtract. The result is $$(x^2-x^5)\frac{1}{(1-x)^3}=\sum_{m\ge 5}{m-2+2\choose 2}-{m-5+2\choose 2}x^m + \sum_{m=2}^4{m-2+2\choose 2}x^m$$

Hence your answer (for $m\ge 5$) is ${m\choose 2}-{m-3\choose 2}$. You want $m=10$, so ${10\choose 2}-{7\choose 2}=24$.