Use the principle of inclusion-exclusion to find the number of integer partitions of n in which exactly one of 4,7 and 13 is a part

Question

Use the principle of inclusion-exclusion to find the number of integer partitions of $n$ in which exactly one of 4,7 and 13 is a part. The answer can be written as a linear combination of terms $p(k)$ for various $k$.

So I've started this by setting the ambient set as $A=[n]$. And defining the three properties as

$p_1$: 4 is a part of the partition,
$p_2$: 7 is a part of the partition, and
$p_3$: 13 is a part of the partition.

I have the formula $e(X)=\sum_{Y:X\subseteq Y \subseteq P} (-1)^{|Y-X|}a(Y)$
With $e(X)=$ the number of elements in A with exactly the properties in X
and $a(X)=$ the number of elements in A with at least the properties in X.

I know that I need to find $e(p_1)+e(p_2)+e(p_3)$, I'm just not sure how to do this

Answer 1

I will use $a(p_1,p_2)$ to denote the number of partitions containing $4$ and $7$, and similarly $a(p_1,p_2,p_3)$ counts partitions which contain $4,7$ and $13$. Using your formula,

$$e(p_1)=a(p_1)-a(p_1,p_2)-a(p_1,p_3)+a(p_1,p_2,p_3).\tag1$$

You can get similar expressions for $e(p_2)$ and $e(p_3)$. Furthermore,

• $a(p_1)=p(n-4)$, $a(p_2)=p(n-7)$, etc, because a partition containing $4$ corresponds exactly to a partition of $n-4$ with a part of $4$ added.
• $a(p_1,p_2)=p(n-4-7)$, etc, for the same reason.
• $a(p_1,p_2,p_3)=p(n-4-7-13)$.

Now, you just need to plug these expressions for $a(\dots)$ into the expressions for $e(p_i)$ in $(1)$.