2
$\begingroup$

I'm having an intro combinatorics class and I do understand the theorems but I don't really know how to apply them. It's pretty easy to solve straight forward questions, but I just don't understand how to solve harder questions, can someone explain this question to me? What I got is completely different from the back of the book ... should I drop this class?

Let $a_n$ be the number of ways to write the number $n$ as $i_1+i_2+i_3+i_4$, where $i_1,i_2,i_3,i_4$ are integers such that:

$$0<i_1<3\\i_2>0\\i_3=2 \text{ or } 4\\i_4>1$$

How do I write the generating function for this sequence, representing this as a rational function?

The only thing I know to first solve this question is to solve it by using the multiplication rule of power series (perhaps?). I know the generating function is a product of $4$ power series, corresponding to $i_1,i_2,i_3,i_4$.

Help appreciated. Really struggling.

$\endgroup$
  • $\begingroup$ If you had to give this a try, what would you guess? $\endgroup$ – Calvin Lin Sep 18 '13 at 2:14
  • $\begingroup$ Hint: $$\begin{cases} 0 < i_1 < 3 & \longleftrightarrow\quad t + t^2\\ i_2 > 0 & \longleftrightarrow\quad t + t^2 + t^3 + \cdots\;=\;\frac{t}{1-t}\\ i_3 = 2\text{ or }4 & \longleftrightarrow\quad ???\\ i_4 > 1 & \longleftrightarrow\quad ??? \end{cases}$$ $\endgroup$ – achille hui Sep 18 '13 at 2:26
4
$\begingroup$

You know that the generating function you want is a product of the four generating functions for $i_1,i_2,i_3$, and $i_4$. So all that remains is to find those.

For $i_1$, think about this: in how many ways can you express an integer $n$ as a sum of a single integer drawn from $\{1,2\}$? If $n$ is anything but $1$ or $2$, you can't do it at all, and if $n$ is $1$ or $2$, you can do it in only one way. So this generating function is $x + x^2$. The generating function for $i_3$ can be found by the same reasoning.

For $i_2$, for essentially the same reasons as $i_1$ and $i_3$, you get the series $1+x+x^2+x^3+x^4+\dots$, which you should recognise as $\frac{1}{1-x}$. $i_4$, again, uses the same reasoning, but with no constant term

Once you've found these four functions, you just need to multiply them together.

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