Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - Counting problem

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,889
    Thanks
    326
    Awards
    1

    Counting problem

    Hi! It's me again with another counting problem.

    I am trying to find the order of the following set (where n \in \mathbb{Z} is fixed): G_1 = \{ \sigma \in S_n | \sigma (1) = 1 \} , the stabilizer of 1 in S_n.

    Now, I have calculated 4 of these:
    n = 2: G_1 = \{ e \} so |G_1| = 1

    n = 3: G_1 = \{ e, (23) \} so |G_1|= 2

    n = 4: G_1 = \{ e, (234), (243), (23), (24), (34) \} so |G_1|= 6

    I also did n = 5 which gives: |G_1| = 24

    The pattern seems to be that |G_1| = (n - 1)!, but the examples don't help me to understand the counting in general, which was the intent of doing the examples in the first place.

    Any thoughts?
    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Counting problem

    My only thought is, |S_n| = n! since it is the number of ways to permute n items. Hence, |G_1| = (n-1)! since it is the number of ways to permute n-1 items (if you have n items, but stabilize 1, then you are only permuting n-1 items).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,889
    Thanks
    326
    Awards
    1

    Re: Counting problem

    Quote Originally Posted by SlipEternal View Post
    My only thought is, |S_n| = n! since it is the number of ways to permute n items. Hence, |G_1| = (n-1)! since it is the number of ways to permute n-1 items (if you have n items, but stabilize 1, then you are only permuting n-1 items).
    Yes, it is as you say. (sighs) I was hoping to get back before someone answered. If I had calculated this with the nth position (the stabilizer of the highest place) I would have seen it right away. I was thinking about it way too hard and I got lost in it.

    Thanks!
    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,371
    Thanks
    740

    Re: Counting problem

    Sometimes this is called the "fixed group" (or isotropy group) of 1, that is: the elements of Sn that fix 1. It should be obvious this is, in fact a subgroup of Sn, because it is closed under composition (the multiplication of Sn).

    There are a couple of way to approach this:

    the first is to show that the mapping:

    f:\text{Stab}(1) \to S_{n-1} given by:

    (f(\sigma))(k) = (\sigma(k+1)) - 1, for k = 1,2,...,n-1 is an isomorphism.

    The second is to use the orbit-stabilizer theorem:

    |S_n| = |S_n(1)|\ast|\text{Stab}(1)|

    Now because we have the n-1 transpositions (1 k), along with the identity map, it is clear that |Sn(1)| = n (the orbit of 1 has size n, because Sn acts TRANSITIVELY on the n letters (the set of cardinality n...in this case {1,2,...,n}) it permutes). Thus:

    |Stab(1)| = n!/n = (n-1)!.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting Problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2013, 02:23 PM
  2. Counting problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 20th 2010, 12:17 PM
  3. Counting problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 11th 2010, 06:47 AM
  4. Counting problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2010, 05:21 PM
  5. Replies: 3
    Last Post: April 13th 2009, 05:42 PM

Search Tags


/mathhelpforum @mathhelpforum