[seqfan] Re: please advise: count of decompositions of permutatations of n into products of involution pairs
arndt at jjj.de
Wed Aug 5 03:29:59 CEST 2009
* wouter meeussen <wouter.meeussen at pandora.be> [Aug 05. 2009 10:00]:
> dear all,
> for 1, 2, 10, 46, 326, 2476, 22492,...
> I could argue that, to some, it might be of interest to count the
> decompositions of the permutations of n into pairs of involutions. If not
> now, then maybe later.
Yes this is interesting (well, to me).
> Any permutation can be written as a product of a pair of involutions, and
> often in many ways. A notorious mathematician once (1998?) showed me how.
> [ascii art garbled for me; yes, fixed font display]
Notorious computationalist says this is trivial.
To rotate an array of n=8 elements be s=3 positions
(no sctratch space needed):
Rotate left by 3 positions:
[ 1 2 3 4 5 6 7 8 ] original array
[ 3 2 1 4 5 6 7 8 ] reverse first 3 elements
[ 3 2 1 8 7 6 5 4 ] reverse last 8-3=5 elements
[ 4 5 6 7 8 1 2 3 ] reverse whole array
I call this the 'triple reversal technique', deserves to
be better known.
(With rotation by s=1 positions one reversal disappears.)
Method still OK if elements scattered, just copy cycle
to array, triple-rev, then copy back.
Reversal is an involution.
This gives you a 'canonical' way to decompose any permutation.
(And another one if instead of rotating right by 1 position,
you rotate left by n-1 positions).
> About ten years later, it came to me that the set of permutations of n
> generates more than n! couples of involutions as its decompositions (no, not
> prime, not unique).
> Count of which is, teasingly to n=36: (offset 1)
> 1, 2, 10, 46, 326, 2476, 22492, 222860, 2539756, 31101976, 424163576,
> 6183804232, 98022462760, 1653222913616, 29862161016976, 570997442386576,
> 11573674977168272, 247136949802012960, 5552950221534095776,
> 130868386599399370976, 3227555172686193633376, 83164157620475009758912,
> 2232922569081925813952960, 62421208989699816969363136
> No, this did *not* take ten years to calculate. 8 seconds sufficed.
Determine numof pairs for length-L cycle, then
iterate over integer partitions (?).
> Who comes up with a GF for this abomination?
No simple OGF, or simple Euler transform (as expected).
==> Rather look for EGFs. Someone?
> And, please, a more concise and lucid description vs.the current title?
Some insight may be gained form 'standard tableaux', cf. Knuth.
Tableaux are 1-to-1 with involutions.
Knuth gives IIRC one way to form a bijection between
permutations and pairs of tableaux.
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan