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

Joerg Arndt 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.
> 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/

```