How many set partitions of [n] are there in which 1 is not in a block of size 1?

Question

I'm not at all sure how to solve the following question: How many set partitions of [n] are there in which 1 is not in a block of size 1? Could someone please help? Thanks!

Answer 1

Here's what I understood ,

If $n = \{1,2,3\}$

Then the partitions of n are,

$P_1 = \{ \{1\}, \{2\}, \{3\} \}$

$P_2 = \{ \{1, 2\}, \{3\} \}$

$P_3 = \{ \{1, 3\}, \{2\} \}$

$P_4 = \{ \{1\}, \{2, 3\} \}$

$P_5 = \{ \{1, 2, 3\} \}$

But according to your question we cannot consider $P_1$ and $P_4$ as $1$ is inside a block of size $1$.

So what we can do is , remove $1$ from the set and then calculate the number of partitions of the new set .

$n' = \{2,3\}$

Then the partitions of $n'$ are,

$P'_1 = \{ \{2\}, \{3\} \}$

$P'_2 = \{ \{2, 3\}\}$

Now to these partitions we can plug in $\{1\}$ , and get all the partitions which have $\{1\}$ in a block of size $1$, i.e $P_1$ and $P_4$.

So the number of partitions which do not have $1$ in a block size of $1 = B_n - B_{n-1}$ where $B_n$ is the Bell number.