Permutations with even order
Yifat Veisberg
group S_n that have even order ?
Thanks,
Yifat
Fred Galvin
> Is there a formula for the number of permutations in the symmetric
> group S_n that have even order ?
Seems like a straightforward calculation, but I did it by hand and I
could have botched it, so you'd better check it. Is it homework?
The answer to your question is n!-a(n) where a(n) is the number of
*odd* order permutations in S_n. Let f(x) be the exponential
generating function of a(n), and write C(n,k) for the binomial
coefficient n(n-1)(n-2)...(n-k+1)/k!. Here's what I get:
a(n+1) = a(n)+n(n-1)a(n-2)+n(n-1)(n-2)(n-3)a(n-4)+...;
f(x) = sqrt((1+x)/(1-x));
a(n)/n! = the sum of C(1/2,n-k)*C(k-1/2,k) from k = 0 to n.
Did I get it right?
Ayatollah Potassium
> > Is there a formula for the number of permutations in the symmetric
> > group S_n that have even order ?
>
> Seems like a straightforward calculation, but I did it by hand and I
> could have botched it, so you'd better check it. Is it homework?
>
> The answer to your question is n!-a(n) where a(n) is the number of
> *odd* order permutations in S_n. Let f(x) be the exponential
> generating function of a(n), and write C(n,k) for the binomial
> coefficient n(n-1)(n-2)...(n-k+1)/k!. Here's what I get:
Use Joyal species. An odd permutation on a set is a partition
of the set into pieces, and an odd cyclic permutation on each. If
g(x) is exponential generating function for odd cyclic permutations,
this means f(x) = exp(g(x)). Exp generating function for cyclic
permutations is L(x) = sum( x^n / n ) = -log(1-x). For odd cyclic
permutations extract just the odd terms from this:
g(x) = (L(x)-L(-x) / 2) = (log (1+x) - log(1-x))/2.
Thus, f(x) = exp(g(x)) = sqrt ( (1+x)/(1-x)).
To get a formula with binomial coefficients, use the binomial
theorem; f(x) = (1+x)^(1/2) * (1-x) (-1/2) .
This agrees with your answer.
Fred Galvin
> Use Joyal species. An odd permutation on a set is a partition
> of the set into pieces, and an odd cyclic permutation on each. If
> g(x) is exponential generating function for odd cyclic permutations,
> this means f(x) = exp(g(x)). Exp generating function for cyclic
> permutations is L(x) = sum( x^n / n ) = -log(1-x). For odd cyclic
> permutations extract just the odd terms from this:
> g(x) = (L(x)-L(-x) / 2) = (log (1+x) - log(1-x))/2.
> Thus, f(x) = exp(g(x)) = sqrt ( (1+x)/(1-x)).
> To get a formula with binomial coefficients, use the binomial
> theorem; f(x) = (1+x)^(1/2) * (1-x) (-1/2) .
> This agrees with your answer.
Great! Thanks for verifying that. I guess I need to learn about Joyal
species, so that I'll be able to work out problems like the above
without having so much fun. By the way, I wouldn't call a permutation
of odd order an "odd permutation", which could be taken to mean the
product of an odd number of transpositions. But maybe my terminology
is as out of date as my methods.
Ola Veshta
>of the set into pieces, and an odd cyclic permutation on each.
Excuse my ignorance but what are "Joyal species" ?
(and correct me if I am wrong but "Ayatollah Potassium" is a pen name
and not a real name right ? )
Thanks,
Ola
Ayatollah Potassium
> >Use Joyal species. An odd permutation on a set is a partition
> >of the set into pieces, and an odd cyclic permutation on each.
>
> Excuse my ignorance but what are "Joyal species" ?
A refinement of the notion of (exponential) generating function
used in combinatorics, and an example of "categorification" as
described in the weekly physics(!) postings here. The point is
that generating functions enumerate various types of structures
on a finite set --- permutations, subsets, and so on --- and
operations on the power series can often be promoted
to the level of natural bijections between the structures, rather than
just equations between numbers. This was all "in the air" for many
years, but Joyal formalized it in a useful way:
Joyal, André
Une théorie combinatoire des séries formelles
Adv. in Math. 42 (1981), no. 1, 1--82.
Textbook references are Richard Stanley ENUMERATIVE
COMBINATORICS vol. 2, and F. Bergeron COMBINATORIAL
SPECIES AND TREE-LIKE STRUCTURES.
> (and correct me if I am wrong but "Ayatollah Potassium" is a pen name
> and not a real name right ? )
I'm not aware of anyone with legal name Ayatollah Potassium. I could
be wrong!
Ayatollah Potassium
> Is there a formula for the number of permutations in the symmetric
> group S_n that have even order ?
Here is a more direct approach than what I posted earlier.
An even-order permutation of an n-element set consists of:
a subset of size n - 2k of fixed points, 0 < k <= n/2; and
a fixed-point-free permutation of even order of the remaining
2k elements. There are C(n,2k) of the first, and (by a canonical
bijection) M(2k)^2 of the second, where M(2k) = 1*3*...(2k-1) =
(2k)!/(k!*2^k) is the number of matchings of a 2k-element set.
So we get: sum from k=1 to n/2 of C(n,2k)*[(2k)!/k!2^k]^2.
Ayatollah Potassium
> > Use Joyal species. An odd [order] permutation on a set is a partition
>
> > of the set into pieces, and an odd cyclic permutation on each. If
> > g(x) is exponential generating function for odd cyclic permutations,
> > this means f(x) = exp(g(x)). Exp generating function for cyclic
> > permutations is L(x) = sum( x^n / n ) = -log(1-x). For odd cyclic
> > permutations extract just the odd terms from this:
> > g(x) = (L(x)-L(-x) / 2) = (log (1+x) - log(1-x))/2.
> > Thus, f(x) = exp(g(x)) = sqrt ( (1+x)/(1-x)).
> > To get a formula with binomial coefficients, use the binomial
> > theorem; f(x) = (1+x)^(1/2) * (1-x) (-1/2) .
> > This agrees with your answer.
> Great! Thanks for verifying that. I guess I need to learn about Joyal
> species,
Probably you already know it in some form. It's written up
in volume 2 of Stanley's book on enumerative combinatorics, or
Bergeron's book on combinatorics of tree-like structures, or
(in French, using category-theory language) in Joyal's long paper
in Adv.Math.
> so that I'll be able to work out problems like the above
> without having so much fun.
More fun. In this case, f(x) = sqrt (1 + 2x + 2x^2 + 2x^3 + ....)
being the exp generating function for odd order permutations, means
that breaking an n-element set into two pieces and installing an
permutation
of odd order on each piece, should be equivalent to installing some
other kind of structure on the set, of which there are 2*n! for n>1.
So the "species" approach forces the question: what are some natural
structures whose number is 2*n!, and how are they in bijection with pairs
of odd order
permutations?
Ola Veshta
name
> and not a real name right ? )
>I'm not aware of anyone with legal name Ayatollah Potassium. I
>could
>be wrong!
Well I am very curious about the combination of your names.
Ayatollah relates to Iran as far as I know,
Potassium to chemistry,
Carnus Edimus, Ave Tedimus is Latin ??
and what is san...@bibimus.edu ? the only bibi that I know is the
former prime minister of Israel :-).
Give us a hint !!!
Regards,
Ola
Ayatollah Potassium
> Well I am very curious about the combination of your names.
> Ayatollah relates to Iran as far as I know,
> Potassium to chemistry,
> Carnus Edimus, Ave Tedimus is Latin ??
> and what is san...@bibimus.edu ? the only bibi that I know is the
> former prime minister of Israel :-).
> Give us a hint !!!
It's in homage to: a great sage of the Usenet; a favorite Jerry
Goldsmith composition; and a famous living mathematician.
Ola Veshta
>Goldsmith composition; and a famous living mathematician.
Well I do not know what is the favorite Jerry Goldsmith composition
but since the symbol of potassium is "K" maybe the famous living
mathematician is Daniel Quillen ?
Ola