MathDB

A partition of a set

A

is a family of non-empty subsets of

A

, such that any two distinct subsets in the family are disjoint, and the union of all subsets equals

A

. We say that a partition of a set of integers

B

is separated if each subset in the partition does not contain consecutive integers. Prove that, for every positive integer

n

, the number of partitions of the set

\{1, 2, \dots, n\}

is equal to the number of separated partitions of the set

\{1, 2, \dots, n+1\}

.
For example,

\{\{1,3\}, \{2\}\}

is a separated partition of the set

\{1,2,3\}

. On the other hand,

\{\{1,2\}, \{3\}\}

is a partition of the same set, but it is not separated since

\{1,2\}

contains consecutive integers.

Problem Statement