Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting cycles in a permutation

  1. Sep 27, 2008 #1
    I'm trying to show that for two permutations f ang g in Sn, the number of disjoint cycles in fg is the same as the number of disjoint cycles in gf. I know that in general fg does not equal gf, but by working examples it seems like they always decompose into the same number of disjoint cycles. Is this even true? Can anyone find a counterexample?

    I solved the related problem of showing that fg and gf both fix the same number of elements. This is true because fg fixes x if and only if gf fixes g(x), and g is a bijection.
  2. jcsd
  3. Sep 28, 2008 #2


    User Avatar

    Oops -- I posted a full solution here and then realized ... this is a homework problem, isn't it? At least it sure sounds like one.

    So here's a piece of a solution. Should get you started!

    It seems like your 1:1 mapping between fixed points in fg and gf generalizes to a 1:1 mapping between disjoint cycles, too. In particular, note that

    (f \circ g)^n = f \circ g \circ f \circ ... \circ g


    (g \circ f)^n = g \circ f \circ g \circ ... \circ f

    So, if (fg)n carries x to itself, where does (gf)n carry g(x)?

    'Nuff said.
    Last edited: Sep 28, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook