[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.
Franklin T. Adams-Watters
-----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.
...
More information about the SeqFan
mailing list