Find the ordinary generating function for number of partitions

Question

let $a_n$ denote the number of ways to split $[n]$ into blocks of size $1, 2$, or $3$. Find the ordinary generating function for ${a_n}$.

For this would I first split $n$ into three groups? From those three groups, I choose to either split them into the size of $1,2,3$? Will this be correct? Thank you.

Answer 1

We want to know the GF of the number of ways to break $1,2,3, \dots ,n$ into blocks of length 1, 2, or 3.

The GF of the length of a single block is $x+x^2+x^3$. A complete arrangement is a sequence of such blocks. So its GF is $$f(x) = \frac{1}{1-(x+x^2+x^3)}$$

Answer 2

Find the recursion expressing $a_n$ in terms of the previous $a_k$. (Hint: it depends on whether 1, 2, or 3 are added.)

Then convert that into the generating function.

Answer 3

$n$ is either in a block of one by itself, a block of two with one other, or a block of three with two others. The remaining elements can be renumbered and the same process applied.

In terms of o.g.f. you'll get a second order differential equation to solve.