About Warm-ups Problems News

Problem 25

Posted 04/07/2016
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

This problem is about set partitions of $\{1,2,3,\cdots,n\}$.

For example, $\{1,3,5,6\}\{2,4\}$ is a set partition of $\{1,2,\cdots,6\}$ into $2$ parts.
The total number of set partitions of $\{1,2,\cdots,n\}$ is counted by Bell numbers (OEIS:A000110).

Suppose $a(n)$ is the number of set partitions of $\{1,2,\cdots,n\}$ such that each part in the partition contains at least one prime number.

For example, $a(1)=0$ because no such set partition exists and $a(3)=3$ because there are three such set partitions and they are $\{1,2,3\}$, $\{1,2\}\{3\}$ and $\{1,3\}\{2\}$.

Find $a(n)$.








Back to top