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

[Wouter Meeussen]

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.

Needless to say that the dot products of rows from the first table with corresponding rows from the second produce n!  as they very well should (check: 10*1+4*2+1*6 = 24 = 4! )

By now, you might have expected the familiar StirlingS2 triangle to have popped up, but no.
That’s because the StirlingS2 counts Set Partitions by number of blocks.
But A036040 (Triangle of multinomial coefficients, read by rows) contains more details, since it counts by block lengths as integer partitions.  
In the table below  u * q[ c , p ]^v  is coding for u different v-tuplets, each consisting of  c  blocks with integer partition of rank p.
The coefficients u are exactly A036040 mentioned above,
and collecting terms with same ‘c’ produces the StirlingS2

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]
q[1,1]^120 + 6 q[2,2]^24 + 15 q[2,3]^6 + 10 q[2,5]^4 + 15 q[3,4]^6 + 60 q[3,6]^2 + 15 q[3,8] + 20 q[4,7]^2 + 45 q[4,9] + 15 q[5,10] + q[6,11]

Take the fourth row,  
1,4,3,6,1 (by ‘u’ : by partition structure of block lengths: A036040)
1,4+3=7,6,1 ( by ‘c’ : by block counts : StirlingS2)
1*(6) + 4*(2) + 3*(1) + 6*(1) + 1*(1) = 24 = 4!  (all permutations accounted for).

What the very first table in this mail counted, can be reconstructed as ‘grouping by multiplicity’
1 , 4 , 3+6+1 = 10   (by ‘v’ )

Wouter.

------------------------------------------ Mma 4.0 below ------------------------------
inits:
qbinomial[n_Integer, m_Integer] := Expand[Together[Product[(1 - q^(n-j))/(1 - q^(j+1)), {j,0,m-1}]]];
integerpartitions[n_, m_] := Coefficient[qbinomial[n+1+m, m], q^n];
rankpartition[(p_)?PartitionQ] := PartitionsP[Tr[p]] - Sum[(integerpartitions[Tr[#1], First[#1]-1] &)[Drop[p, k]], {k,0,Length[p]-1}];

main:
it2 = Table[
    q[Length at First[#], rankpartition[Reverse[Length /@ First[#]]]]^ Length[#] & /@ 
        Split[Map[ Sort, ToCycles /@ Permutations[Range at n], {0, 2}]] // Tr
       , {n, 7}]
---------------------------------------------------------------------------------------------




first two tables in full:
{1}, 
{2}, 
{4, 1}, 
{10, 4, 1}, 
{26, 20, 5, 1}, 
{76, 80, 10, 30, 6, 1}, 
{232, 350, 70, 140, 35, 42, 7, 1}, 
{764, 1456, 560, 700, 280, 224, 35, 56, 56, 8, 1}, 
{2620, 6384, 3360, 3276, 280, 2520, 1260, 315, 504, 336, 126, 84, 72, 9, 1}, 
{9496, 27840, 21000, 15960, 2800, 16800, 8652, 3150, 5040, 2100, 1260, 840, 126, 690, 120, 90, 10, 1}

{1}, 
{1}, 
{1, 2}, 
{1, 2, 6}, 
{1, 2, 6, 24}, 
{1, 2, 4, 6, 24, 120}, 
{1, 2, 4, 6, 12, 24, 120, 720}, 
{1, 2, 4, 6, 12, 24, 36, 48, 120, 720, 5040}, 
{1, 2, 4, 6, 8, 12, 24, 36, 48, 120, 144, 240, 720, 5040, 40320}, 
{1, 2, 4, 6, 8, 12, 24, 36, 48, 120, 144, 240, 576, 720, 1440, 5040, 40320, 362880}

full detail (formula given with n=10)

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],
q[1,1]^120+6 q[2,2]^24+15 q[2,3]^6+10 q[2,5]^4+15 q[3,4]^6+60 q[3,6]^2+15 q[3,8]+20 q[4,7]^2+45 q[4,9]+15 q[5,10]+ q[6,11],
q[1,1]^720+7 q[2,2]^120+21 q[2,3]^24+35 q[2,5]^12+21 q[3,4]^24+105 q[3,6]^6+70 q[3,8]^4+105 q[3,9]^2+35 q[4,7]^6+210 q[4,10]^2+
105 q[4,12]+35 q[5,11]^2+105 q[5,13]+21 q[6,14]+ q[7,15],

q[1,1]^5040+8 q[2,2]^720+28 q[2,3]^120+56 q[2,5]^48+35 q[2,8]^36+28 q[3,4]^120+168 q[3,6]^24+280 q[3,9]^12+210 q[3,10]^6+
280 q[3,13]^4+56 q[4,7]^24+420 q[4,11]^6+280 q[4,14]^4+840 q[4,15]^2+105 q[4,18]+70 q[5,12]^6+560 q[5,16]^2+420 q[5,19]+
56 q[6,17]^2+210 q[6,20]+28 q[7,21]+q[8,22],

q[1,1]^40320+9 q[2,2]^5040+36 q[2,3]^720+84 q[2,5]^240+126 q[2,8]^144+36 q[3,4]^720+252 q[3,6]^120+504 q[3,9]^48+378 q[3,10]^24+
315 q[3,13]^36+1260 q[3,14]^12+280 q[3,19]^8+84 q[4,7]^120+756 q[4,11]^24+1260 q[4,15]^12+1890 q[4,16]^6+2520 q[4,20]^4+1260 q[4,22]^2+126 q[5,12]^24+
1260 q[5,17]^6+840 q[5,21]^4+3780 q[5,23]^2+945 q[5,26]+126 q[6,18]^6+1260 q[6,24]^2+1260 q[6,27]+84 q[7,25]^2+378 q[7,28]+36 q[8,29]+ q[9,30],

q[1,1]^362880+10 q[2,2]^40320+45 q[2,3]^5040+120 q[2,5]^1440+210 q[2,8]^720+126 q[2,13]^576+45 q[3,4]^5040+360 q[3,6]^720+840 q[3,9]^240+
630 q[3,10]^120+1260 q[3,14]^144+2520 q[3,15]^48+1575 q[3,20]^36+2100 q[3,22]^24+120 q[4,7]^720+1260 q[4,11]^120+2520 q[4,16]^48+3780 q[4,17]^24+
1575 q[4,21]^36+12600 q[4,23]^12+3150 q[4,25]^6+2800 q[4,29]^8+6300 q[4,30]^4+210 q[5,12]^120+2520 q[5,18]^24+4200 q[5,24]^12+9450 q[5,26]^6+
12600 q[5,31]^4+12600 q[5,33]^2+945 q[5,37]+252 q[6,19]^24+3150 q[6,27]^6+2100 q[6,32]^4+12600 q[6,34]^2+4725 q[6,38]+210 q[7,28]^6+
2520 q[7,35]^2+3150 q[7,39]+120 q[8,36]^2+630 q[8,40]+45 q[9,41]+ q[10,42]

---------------- told you it was longish --------------------------------