# Writing a generating function

I came across the following question and it's a bit different from what I'm used to...

Write a generating function for each of the following:

1) You are making an Easter basket with at most two special edition Peeps. Each special edition Peep comes in its own one candy package. There are 4 different types of special edition Peep's: red velvet, lemon spice, party cake, and lemonade. If you have 2 peeps, they could either be the same or different flavors.

2) You are making an Easter basket and filling it with n pieces of candy. You can include any number of packages of 5 yellow chick Peeps, any number of packages of 5 blue bunny Peeps, and special edition peeps following the requirements in the previous problem.

=====================================

For (1), I'm being thrown off by the "at most two" requirement. Usually generating functions deal with infinite series with an arbitrary large n. At first I thought maybe the following might be it:

$(1+x+x^2)^4$

But I'm not sure at all. If I were allowed to express it as an integer addition question, I thought maybe I could express it like so:

$$x_1+x_2+x_3+x_4 \leq 2, x_{1,2,3,4} \geq 0$$ which can be solved via the stars & bars method: ${6 \choose 4}=15$ (is this right?) If so, the above generating function doesn't result in the coefficient of 15 when n = 2. I feel like I'm just thinking about this wrong.

For (2), since I'm stuck on (1) I don't know where to start on this.

Thanks for any help.

================================

EDIT2: So it looks like I'm getting close on (1)...

Also, for (2), is the first part of it just $(1+x+x^2+x^3+x^4+x^5)^2$ or am I missing something? Thanks.

• Oh wait, since n is at most 2, am I supposed to take into consideration all values of n from 0 to 2? If so the above generating function does result in the sum of 15... – user3280193 Apr 19 '16 at 2:33
• Your comment is correct; you’ve now almost answered the first question. If $g(x)=(1+x+x^2)^4$, you want the function such that the coefficient of $x^n$ is the sum of the coefficients in $g$ of $x^k$ with $k\le n$. Do you know what to multiply $g(x)$ by to get that? – Brian M. Scott Apr 19 '16 at 2:34
• Hmm...I guess I'm stuck again. :D I've just never run into this type of question variant before. – user3280193 Apr 19 '16 at 2:43
• Useful fact (that you should try to prove): if $g(x)=\sum_{n\ge 0}a_nx^n$, then $$\frac1{1-x}\cdot g(x)=\sum_{n\ge 0}\left(\sum_{k=0}^na_k\right)x^n\;.$$ Multiplying by $\frac1{1-x}$ gives you the partial sums of the sequence of coefficients of the original series. – Brian M. Scott Apr 19 '16 at 2:45
• Awesome, I'll think about this. Thanks. – user3280193 Apr 19 '16 at 3:06