fun with partitions & permutations

[Wouter Meeussen]

hi,

in addressing the question,
" for each q<=n, how many permutations p(n) are there so that p(n)^q = 1 "
I hit on some candidate sequences, some ugly, some nice.

Looking at the possible cycle structures of p(n) as partitions of n,
it can be asked "how many partitions of n are there with a LCM equal to q (q<=n)
- ----------------
example:

a permutation
(1,3,5)(2,4)(6) can be considered as having structure (3,2,1)
and the LCM of that is 6.
- ----------------

for n from 1 to 12, the number of partitions with LCM equal to q 
running from 1 to n is :

{1}
{1, 1}
{1, 1, 1}
{1, 2, 1, 1}
{1, 2, 1, 1, 1}
{1, 3, 2, 2, 1, 2}
{1, 3, 2, 2, 1, 3, 1}
{1, 4, 2, 4, 1, 5, 1, 1}
{1, 4, 3, 4, 1, 7, 1, 1, 1}
{1, 5, 3, 6, 2, 9, 1, 2, 1, 3}
{1, 5, 3, 6, 2, 12, 1, 2, 1, 4, 1}
{1, 6, 4, 9, 2, 16, 1, 4, 2, 6, 1, 9}

the rows total to: (not in EIS)

{1,2,3,5,6,11,13,19,23,33,38,61}

But, the LCM can get bigger than n itself. The biggest it can get is
Landau's g(n) A000793:
{1,2,3,4,6,6,12,15,20,30,30,60,60,84,105,140,210,210,420,420,420,420,840,840}

the number of "long" or high-LCM partitions (with LCM >n) is : (not in EIS)

{0,0,0,0,1,0,2,3,7,9,18,16,...}
where partitions(5) stands out with its 5=3+2 and LCM(3,2)=6 > 5.

Using some slight of hand to count the number of permutations that correspond
to a given cycle structure (ergo, partition), the original question 
" for each q<=n, how many permutations p(n) are there so that p(n)^q = 1 "
leads to: (not in EIS)

{1}
{1, 1}
{1, 3, 2}
{1, 9, 8, 6}
{1, 25, 20, 30, 24}
{1, 75, 80, 180, 144, 240}
{1, 231, 350, 840, 504, 1470, 720}
{1, 763, 1232, 5460, 1344, 10640, 5760, 5040}
{1, 2619, 5768, 30996, 3024, 83160, 25920, 45360, 40320}
{1, 9495, 31040, 209160, 78624, 584640, 86400, 453600, 403200, 514080}
{1, 35695, 142010, 1290960, 809424, 4496030, 237600, 3326400, 2217600,
4823280, 3628800}
{1, 140151, 776600, 9753480, 4809024, 42658440, 570240, 39916800, 26611200,
57081024, 43545600, 80166240}

the row totals answers to "how many permutations p(n) are there so that
p(n)^q = 1 for q<=n"

{1,2,6,24,100,720,4116,30240,237168,2370240,21007800,306028800}  (not in EIS)
this sequence starts out as n! but soon dips under it.

the difference is in the permutations with higher-than-n period:

 {0},
 {0},
 {0},
 {0},
 {20},
 {0},
 {504,420},
 {2688,4032,3360},
 {25920,18144,24192,9072,18144,15120,15120},
 {172800,259200,151200,181440,120960,120960,50400,151200,50400},
 {2217600,1663200,1425600,1900800,712800,1425600,1330560,1663200,
       997920,997920,443520,1330560,443520,415800,554400,415800,831600,138600},
 {26611200,19958400,13685760,17107200,11404800,11404800,8553600,5702400,
       15966720,7983360,11975040,3991680,5322240,3991680,7983360,1330560}

with rows totaling at

{0,0,0,0,20,0,924,10080,125712,1258560,18909000,172972800}  (not in EIS)

and of course, the sum of both (q<=n) and (q>n) sequences equals (n!).

If we use the (partitions to nr of permutations)-trick on all partitions,
irrespective of their LCM, then we get a kind of analogue to StirlingS1
(that counts the number of permutations of n with exactly m cycles)

mine looks at permutations in terms of partitions :

{1}
{1, 1}
{2, 3, 1}
{6, 8, 3, 6, 1}
{24, 30, 20, 20, 15, 10, 1}
{120, 144, 90, 90, 40, 120, 40, 15, 45, 15, 1}
{720, 840, 504, 504, 420, 630, 210, 280, 210, 420, 70, 105, 105, 21, 1}

versus StirlingS1[n,m] in terms of cycle-counts:

{1}
{1, 1}
{2, 3, 1}
{6, 11, 6, 1}
{24, 50, 35, 10, 1}
{120, 274, 225, 85, 15, 1}
{720, 1764, 1624, 735, 175, 21, 1}

Of course, both add up to (n!). Note that the first & last two entries
correspond.


So, why not go for the StirlingS2 too ?
a minor adaptation of the (partitions to nr of permutations)-trick will
do the counting of permutations with disregard to ordering within the cycles
themselves.
That gives :

{1}
{1, 1}
{1, 3, 1}
{1, 4, 3, 6, 1}
{1, 5, 10, 10, 15, 10, 1}
{1, 6, 15, 15, 10, 60, 20, 15, 45, 15, 1}
{1, 7, 21, 21, 35, 105, 35, 70, 105, 210, 35, 105, 105, 21, 1}

to be compared with StirlingS2[n,m] :

{1}
{1, 1}
{1, 3, 1}
{1, 7, 6, 1}
{1, 15, 25, 10, 1}
{1, 31, 90, 65, 15, 1}
{1, 63, 301, 350, 140, 21, 1}


and of course, the row sums are the same in both,

{1,2,5,15,52,203,877, ... 4140,21147,115975,678570,4213597}
and equal to A000110 : Bell's numbers.

*******************************************
conclusion:

the trouble with non-triangular tables as above is that the counting
must than "arbitrarily" be split up in "p(n)^q with q<=n" , giving the 
triangular bit, and "p(n)^q with q>n", giving only the totals for each n,
and maybe the maximum q attainable (A000793).

If interesting enough for EIS, I ll format them at length 24.


wouter.

comments, grumbles & notes on Senilitas Praecox welcomed.

Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be