Re: S_n permutation group


"Chip Eastham" <hardmath@xxxxxxxxx> ha scritto nel messaggio
news:1149638887.260891.172930@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

bargiax wrote:
Hello, how many permutations a in S_n are there such that a^2=1 ?
My answer is: there are Bin(n,2)+( Bin(n,2)*Bin(n-2,2) )/2 of such
permutations. Is this result correct?
Thank you.

It doesn't appear to give a correct answer when n = 3.

There are four permutations such that squaring gives
the identity permutation, three transpositions and the
identity itself, when n = 3.

If Bin(n,2) means the binomial coefficient, then Bin(3,2)
should be 3. Conventionally Bin(1,2) is zero, ie. no
ways to choose 2 out of 1 thing. With that interpretation
your formula gives 3 rather than 4.

Note that a permutation satisfies a^2 = identity if and
only if it can be written as a product of disjoint cycles
of length no greater than two.

Following that line of reasoning, one easily sees that
for n = 4, the solutions are (a) the identity, (b) six
different transpositions, and (c) three different pairs
of (disjoint) transpositions, for a total of 10 solutions.

Your formula appears to give an answer of 9.


Thank you Chip, perhaps I've found my mistake: my formula didn't mention the
obvious identical permutation. Indeed we know that a)(i,j)=(j,i) and that b)
(i,j)(k,l)=(k,l)(i,j). So the number of different transpositions of the kind
(a) should be Bin(n,2), the rest should be about (b). Unfortunately I did
not include the identity.


.

Relevant Pages

  • Re: Review of Mueckenheims book.
    ... There are *no* transpositions in that box at all. ... This requires an infinite sequence of transpositions. ... But Cantor recognized this as an infinite ... welche durch Permutation der Elemente entstehen." ...
    (sci.math)
  • Re: S_n permutation group
    ... bargiax wrote: ... the identity permutation, three transpositions and the ... different transpositions, ... disjoint cycles have length one. ...
    (sci.math)
  • Re: For ANY sets A, B: If A is proper subset of B then set B has more elts than set A.
    ... >> And as you continue with your sequence of transpositions, ... and no permutation of a finite number of positions can achieve that. ... > having is that you cannot concieve of an infinite process as being ... Or the composition of infinitely many permutations is not a ...
    (sci.math)
  • Re: abstract algebra: uniqueness of parity of transpositions
    ... Assume a permutation P has ... factorizations t1...tn and s1...sm. ... Then the inverse of P is tn...t1 (the same transpositions as in the ... in particular n+m is even, and so n,m have the same parity. ...
    (sci.math)
  • Re: Is there an easy way to show a transposition & n-cycle generate S_n?
    ... transposition and an n-cycle generate S_n doesn't require great ... ingenuity, but boy oh boy is the straightforward attack longwinded. ... I write the permutation left to right, so p.q means permutation p is ... So all transpositions can be formed for any a,b in. ...
    (sci.math)