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

wouter meeussen wouter.meeussen at pandora.be
Tue Aug 4 23:06:18 CEST 2009


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.

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.
"You only need to wite the permutation in cycle form, and, for even cycles,
do as the first half:

         1
               \
2                   6
       \
            \
                \
3                     5
     \
         4

and then, for the second half (second involution),

        ___
        \   /
          1

2 ------------ 6

3 ------------ 5

           4
         /     \
         ----

and for the odd cycles, just do the other thing (with only one loop).
(That"s how the old ones sketched proofs).
After a day or so, I understood.

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?
Who comes up with a GF for this abomination?

And, please, a more concise and lucid description vs.the current title?

Wouter.





More information about the SeqFan mailing list