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$
2
  • $\begingroup$ If you had to give this a try, what would you guess? $\endgroup$
    – Calvin Lin
    Sep 18, 2013 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, 2013 at 2:26

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .