# [seqfan] Re: collapsing permutations to mere Set Partitions (longish)

franktaw at netscape.net franktaw at netscape.net
Wed Jul 25 14:37:17 CEST 2012

```Could the row sums of the multiplicities be A201968?

Also, it seems like the Landau function, A000793, ought to be involved
here somewhere.

-----Original Message-----
From: Wouter Meeussen <wouter.meeussen at telenet.be>

hi all,

take all n! permutations of n in cycle form, sort their cycles. The
result is
simply the Set Partitions of n, counted by the Bell numbers A000110.
I tried to find out how many permutations collapse to the same Set
Partition,
and drew a blank in the OEIS when looking up the resulting
un-triangular table
generated by

q, 2 q, 4 q + q^2, 10 q + 4 q^2 + q^6, 26 q + 20 q^2 + 5 q^6 + q^24, ...

where   u q^v    stands for u different set partitions, each generated
by v
permutations, say u different v-tuplets, or ‘of multiplicity  v ’.

The coefficients ‘u’ give
{1},
{2},
{4, 1},
{10, 4, 1},
{26, 20, 5, 1},
{76, 80, 10, 30, 6, 1},

and have row sums A000110 (Bell) of course, and first element A000085
(involutions)

the multiplicities ‘v’ give
{1},
{1},
{1, 2},
{1, 2, 6},
{1, 2, 6, 24},
{1, 2, 4, 6, 24, 120},

the row lengths are 1, 1, 2, 3, 4, 6, 8, 11, 15, 18, ...
which might be A033834 (Number of proper factorizations of the numbers
with a
record number of proper factorizations) or just as well not. Needs more
pondering.

...
```