Counting set partitions with partition and subset permutation

Question

I'm wondering how can I count partitions and subset permutations.

Let's say I'm counting on object [1,2,3].

Desired outcome is below:

[[1, 2, 3]]
[[1, 3, 2]]
[[2, 1, 3]]
[[2, 3, 1]]
[[3, 1, 2]]
[[3, 2, 1]]
[[1], [2, 3]]
[[1], [3, 2]]
[[2, 3], [1]]
[[3, 2], [1]]
[[1, 2], [3]]
[[2, 1], [3]]
[[3], [1, 2]]
[[3], [2, 1]]
[[2], [1, 3]]
[[2], [3, 1]]
[[1, 3], [2]]
[[3, 1], [2]]
[[1], [2], [3]]
[[1], [3], [2]]
[[2], [1], [3]]
[[2], [3], [1]]
[[3], [1], [2]]
[[3], [2], [1]]

So, for each set partition I permute the sets and permute the elements in each set.

I'm aware I can use (ordered) Bell number to accomplish the task but I can't seem to find the mapping to get the permutations of elements.

Answer 1

On a set of size $n$, there are $2^{n-1} n!$ of these objects. That's because you can generate one of these objects by the following process.

• first, take a permutation of $\{1, 2, \ldots, n\}$. There are of course $n!$ ways to do this.
• then, decide which elements are the first element of a new block. There are $2^{n-1}$ ways to do this, because the first element in the permutation must be the first element of a new block and each following element either is or is not the first element of a new block.

For example, corresponding to the permutation $231$ you have in your list $2^{3-1} = 4$ objects:

[[2, 3, 1]]
[[2, 3], [1]]
[[2], [3, 1]]
[[2], [3], [1]]

and similarly for each of the other five permutations of $123$, giving a total of $4 \times 6 = 24$ of these permuted set partitions.