Determing number of partitions which can be formed from a given partition by manipulating a single element

Question

Background: I know it is possible to calculate the number of partitions of a set of size $n$ using the Bell numbers: https://en.wikipedia.org/wiki/Bell_number

I am also aware that you can calculate all of the partitions of size $k$ of a set of size $n$ using the Stirling Numbers of the second kind: https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

I am curious if it is possible to calculate, given a particular partition, how many possible partitions can be made by manipulating a single element. For example, given $n=4$ and partition {1,2,3}, {4}, I can move to any of the following partitions:

1. {1,2,3,4}
2. {1,2}, {3,4}
3. {1,3}, {2,4}
4. {2,3}, {1,4}
5. {1,2}, {3}, {4}
6. {1,3}, {2}, {4}
7. {2,3}, {1}, {4}

Is there a way to do this in general?

Answer 1

Let $k$ be the number of groups in the given partition, $k_1$ the number of groups of size 1, and $k_2$ the number of groups of size 2.

Each possible move is one of the following:

• Merging two size-1 groups: $\binom{k_1}2$ ways.
• Merging a size-1 group with a larger group: $k_1\times(k-k_1)$ ways.
• Moving an element from a size $\ge2$ group to a different group: $(n-k_1)\times (k-1)$ ways.
• Splitting a size-2 group into two size-1 groups: $k_2$ ways.
• Taking an element from a group of size $\ge3$ to form a new group: $n-k_1-2k_2$ ways.

No two of these can give the same outcome, so the total number of possible outcomes is the sum of these five counts.