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.

score 0 · Answer 1 · answered Dec 14 '19 at 06:46

0

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.

answered Dec 14 '19 at 06:46

marty cohen

107,799

Would it be $a_k = a_{k-1} + a_{k-2} +a_{k-3}$ – user734715 Dec 14 '19 at 06:52
I think that is right. Now get the GF. – marty cohen Dec 14 '19 at 23:08

score 0 · Answer 2 · answered Dec 14 '19 at 08:03

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

score 0 · Accepted Answer · answered Dec 14 '19 at 14:21

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)}$$

Find the ordinary generating function for number of partitions

3 Answers3