About Warm-ups Problems News

Problem 17

Posted 11/01/2015 and typo fixed 11/06/2015
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. A set partition is a way to partition a set into several disjoint subsets. For example, there are $5$ set partitions of $\{1,2,3\}$. They are $\{\{1,2,3\}\}$, $\{\{1\},\{2,3\}\}$, $\{\{2\},\{1,3\}\}$, $\{\{3\},\{1,2\}\}$, $\{\{1\},\{2\},\{3\}\}$. The number of set partitions of $\{1,2,\cdots,n\}$ is counted by Bell numbers(A000110).

$a(n)$ is the number of set partitions of $\{1,2,\cdots,n\}$ such that each part in the set partition has almost equal sum. It means the difference between the largest sum and the smallest sum is at most $1$.

For example, $a(4)=3$ because there are $3$ such set partitions, $\{\{1,2,3,4\}\}$, $\{\{1,4\},\{2,3\}\}$, $\{\{1,2\},\{3\},\{4\}\}$. $a(5)=5$ because there are $5$ such set partitions, $\{\{1,2,3,4,5\}\}$, $\{\{1,2,4\},\{3,5\}\}$, $\{\{1,2,5\},\{3,4\}\}$, $\{\{1,3,4\},\{2,5\}\}$, $\{\{1,4\},\{2,3\},\{5\}\}$.

Find $a(n)$.







Back to top