Find the number of partitions of $n$ in which each part is at least $3$

486 Views Asked by At

Find the number of partitions of $n$ in which each part is at least $3$

Let $h_n$ be the number of partition of $n$ in which each part is at least $3$. I'm pretty sure that the generating function would be $$\sum_{n=0}^{\infty}h_nx^n=\frac{1}{(1-x^3)(1-x^4)(1-x^5)\cdots}$$ I'm not sure how to use this to find the desired number

1

There are 1 best solutions below

2
On BEST ANSWER

In addition to the generating function argument Gerry is hinting at, there's an inclusion/exclusion argument if you're content with a formula for your $h(n)$ in terms of $p(n)$, the number of partitions of $n$. Namely, $$h(n) = p(n) - p(n-1) - p(n-2) + p(n-3).$$ Among the $p(n)$ partitions of $n$, there are $p(n-1)$ of them with at least one part 1. And among the partitions of $n$, there are $p(n-2)$ of them with at least one part 2. We want to remove those, but we have overcounted since there can be partitions of $n$ with at least one 1 and at least one 2; there are exactly $p(n-3)$ of these since removing the necessary 1 and 2 leaves a partition of $n-3$.