[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