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

Wouter Meeussen wouter.meeussen at telenet.be
Wed Jul 25 16:48:09 CEST 2012

```hi all,

after some more ponderous pondering, things seem to simplify considerably:
Franklin suggested:
> Could the row sums of the multiplicities be A201968?
no, negative, it's
1, 1, 3, 9, 33, 157, 889, 6013, 46725, 411621, 4057869, 44118229, 524296885,
...

My own collision with the 'Strong Law of small Integers' was:
> 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.
and again, it's not. Rather :
1, 1, 2, 3, 4, 6, 8, 11, 15, 18, 24, 33, 40, 51, 65, 81, 98, 122, 145, 176,
218, 259, 314, 380, 445, 529, 629, 739, 856, 1015, 1184, 1387, ..

Since the coefficients 'u'  in In the table below  u * q[ c , p ]^v   were
just  A036040,
and the p are just the partitions in A&S order (with c the # of parts in
it), all we need to do
is find out what the exponents 'v' are.  They match with the products of
(#-1)! over the
parts of the partitions:

Table[Times @@@ ( (Map[Reverse, Sort@(Sort /@ Partitions[n]), {1}] - 1)!),
{n,10}]

And now, the whole kit and kaboodle can be calculated for n up to 36 or so.
Just generate the table
q[1,1],
q[1,1] + q[2,2],
q[1,1]^2 + 3 q[2,2] + q[3,3],
q[1,1]^6 + 4 q[2,2]^2 + 3 q[2,3] + 6 q[3,4] + q[4,5],
q[1,1]^24 + 5 q[2,2]^6 + 10 q[2,3]^2 + 10 q[3,4]^2 + 15 q[3,5] + 10 q[4,6] +
q[5,7]
etc
and collect terms by block lengths, by block counts or by 'multiplicities'
as desired.

Wouter.

-----Original Message-----
From: franktaw at netscape.net
Sent: Wednesday, July 25, 2012 2:37 PM
To: seqfan at list.seqfan.eu
Subject: [seqfan] Re: collapsing permutations to mere Set
Partitions(longish)

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.

...

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/

```