[seqfan] Re: please advise: count of decompositions of permutatations of n into products of involution pairs

[Joerg Arndt]

* 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.
> Validation?

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?
> 
> Wouter.
> 
> 

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/