Number of elements of the form $(a_1a_2a_3)(a_4a_5a_6)$ in $S_7$

121 Views Asked by At

In finding the number of elements of order $3$ with the form $(a_1a_2a_3)(a_4a_5a_6)$, my book has $$\dfrac{(7*6*5)(4*3*2)}{(3*3*2)}=280$$ The following is their reasoning for the $2$ in the denominator:

For elements of $S_7$ of the form $(a_1a_2a_3)(a_4a_5a_6)$ there are $(7*6*5)/3$ ways to create the first cycle and $(4*3*2)/3$ to create the second cycle, but the product of these fractions counts $(a_1a_2a_3)(a_4a_5a_6)$ and $(a_4a_5a_6)(a_3a_2a_1)$ as distinct when they are equal group elements.

Why are these equal group elements? I feel that I am not understanding a very basic concept or missing something important.

1

There are 1 best solutions below

0
On BEST ANSWER

To generalise, consider the group elements $S_n$ with the cycle form:

$$\underbrace{(\bullet)\cdots(\bullet)}_{\text{$k_1$ $1$-cycles}}\underbrace{(\bullet\bullet)\cdots(\bullet\bullet)}_{\text{$k_2$ $2$-cycles}}\cdots\underbrace{(\overbrace{\bullet\cdots\bullet}^{r})\cdots(\overbrace{\bullet\cdots\bullet}^{r})}_{\text{$k_r$ $r$-cycles}}$$

The elements with this cycle form have:

$$n=1k_1+2k_2+\cdots +rk_r$$

and we often denote cycles of this form with the notation $z_1^{k_1}z_2^{k_2}\cdots z_{r}^{k_r}$.

Lets count elements of $S_n$ with this cycle form:

There are $n!$ ways to replace $\bullet\,$s with the numbers $1$ to $n$. But then elements of $S_n$ are equivalent if the numbers in a cycle are in the same cyclic order hence we must divide by the number of cyclic orders of each cycle $\smash{1^{k_1}2^{k_2}\cdots r^{k_r}}$.

Also, elements are the same if they have cycles of the same length in a different order, hence we must also divide by the possible arrangements of cycles with the same length $k_1!k_2!\cdots k_r!$.

So, in general the number of group elements in $S_n$ of cycle form $z_1^{k_1}z_2^{k_2}\cdots z_{r}^{k_r}$ is given by:

$$N_{S_n}(k_1,k_2,\ldots , k_r)=\frac{n!}{1^{k_1}2^{k_2}\cdots r^{k_r} k_1!k_2!\cdots k_r!}$$

In your case we have cycle form $z_1^1z_2^0z_3^2$ (where we don't strictly need to use $z_2$ but I include it for clarity), so:

$$N_{S_7}(1,0,2)=\frac{7!}{1^1\cdot 3^2\cdot 2!}$$

Notice, for ease of notation I have truncated the arguments of $N_{S_n}$ at the greatest length cycle $r$.


More interesting stuff

$N_{S_n}(k_1,\ldots, k_r)$ can be thought of as the $z_1^{k_1}z_2^{k_2}\cdots z_r^{k_r}x^n/n!$ coefficient of the polynomial expansion of:

$$e^{z_1x/1}e^{z_2x^2/2}\cdots e^{z_rx^r/r}$$

using $e^a=1+a+a^2/2!+\cdots$ (can you see how?), and therefore also as the $z_1^{k_1}z_2^{k_2}\cdots z_r^{k_r}x^n/n!$ coefficient of the infinite product:

$$\prod_{i\ge 1}e^{z_ix^i/i}\, .$$

If we only care about the size of the group and the number of cycles then we can set all $z_i=z$ and we get:

$$e^{-z\ln(1-x)}=(1-x)^{-z}$$

which gives as it's $z^rx^n/n!$ coefficient the number of elements of $S_n$ with $r$ cycles: ${n\brack r}$. These are called the Stirling numbers of the first kind and there is a lot of literature surrounding them.

If we then put $z=1$ we recover the exponential generating function for number of elements of $S_n$ (i.e. The coefficient of $x^n/n!$ is $n!$):

$$e^{-\ln(1-x)}=\frac{1}{1-x}=\sum_{n\ge 0}n!\frac{x^n}{n!}$$