1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.