# Counting problem

• Dec 20th 2013, 07:22 AM
topsquark
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
• Dec 20th 2013, 08:52 AM
SlipEternal
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).
• Dec 20th 2013, 10:04 AM
topsquark
Re: Counting problem
Quote:

Originally Posted by SlipEternal
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
• Dec 20th 2013, 10:13 AM
Deveno
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)!.