# Tag Archives: permutation

## Number of permutations of order 2

Let $\sigma\in S_n$ be an element of order 2. Then $\sigma$ must be a product of $k\ge 1$ disjoint transpositions. Hence $\sigma$ can be chosen in

$\displaystyle\frac{1}{k!}\binom n2\binom{n-2}{2}\cdots\binom{n-2k+2}{2}=\frac{n!}{k!(n-2k)!2^k}$

ways. So there are exactly

$\displaystyle\boxed{\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{k!(n-2k)!2^k}}$

elements of order 2 in $S_n$.

This can also be expressed in terms of the double factorial

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!$

The following table lists several values of $n$ (left column) along with the number of elements of order 2 in $S_n$:

An interesting feature of the table is that the entries on the second column, except for the first row, are all odd. This is true in general and is not difficult to prove. Using the double factorial notation, the number of elements of order 2 is

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!\equiv \sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}\pmod 2$

Using the binomial theorem for $(1+1)^n$ and $(1-1)^n$ one deduces

$\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}-1\equiv 1\pmod 2$

as expected. Thus

Fact. The number of elements of order 2 in $S_n$ is odd for every $n>1$.

1 Comment

Filed under Combinatorics

## Permuting the units mod n

Let $n>2$ be an integer and $a\in(\mathbb Z/n\mathbb Z)^\times$. We have a permutation map on $(\mathbb Z/n\mathbb Z)^\times$ given by $\pi(a):x\mapsto ax$. Then it is easy to see that

$\pi:(\mathbb Z/n\mathbb Z)^\times\to S_{\phi(n)}$

is an injective homomorphism, where $\phi$ is Euler’s totient function. This is the key idea in the proof of Cayley’s theorem, but we are going to do something a bit different.

Let’s look at $\pi(a)$ in the disjoint cycle notation. One of the cycles is $(1\ a\ a^2 \cdots a^{k-1})$, where $k$ is the order of $a$ modulo $n$. What about the others? In fact, every cycle is of the form $(b\ ba\ ba^2\cdots ba^{k-1})$ for some $b\in(\mathbb Z/n\mathbb Z)^\times$. So every cycle has length $k=\hbox{ord}_n(a)$. And the number of cycles is $\phi(n)/k$.

Let’s look at the sign $\varepsilon(\pi(a))$ of $\pi(a)$. There are $\phi(n)/k$ cycles each of length $k$, and each cycle of length $k$ can be written as a product of $k-1$ transpositions, so

$\varepsilon(\pi(a))=\displaystyle (-1)^{(k-1)\phi(n)/k}=(-1)^{\phi(n)/k}\quad(*)$

where the last equality is obtained by looking at the cases when $k$ is even/odd (and using the fact that $\phi(n)$ is even).

Remark. $(*)$ is saying that the number of transpositions in $\pi(a)$ has the same parity as the number of disjoint cycles in it.

Hence $f=\varepsilon\circ\pi$, being a composition of homomorphisms, is a homomorphism from $(\mathbb Z/n\mathbb Z)^\times$ to $\{\pm 1\}$. It might be interesting to know for which $n$ we get all of $\{\pm 1\}$ as $\hbox{im}(f)$, and for which $n$ we just get the trivial group $\{1\}$.

Fact.  $\hbox{im}(f)=\{\pm 1\}$ if and only if $\phi(n)/\hbox{ord}_n(a)$ is odd for some $a\in(\mathbb Z/n\mathbb Z)^\times$.

Corollary. If there exists $a\in(\mathbb Z/n\mathbb Z)^\times$ such that $v_2(\hbox{ord}_2(a))=v_2(\phi(n))$, then there are exactly $\phi(n)/2$ such $a$‘s. ($v_2(n)$ is the largest integer $k$ such that $2^k\mid n$.)

Proposition. If $n$ is a power of two other than $2^2=4$, then $\hbox{im}(f)=\{1\}$.

Proof. We want to show that $\phi(n)/\hbox{ord}_n(a)$ is even for each $a\in(\mathbb Z/n\mathbb Z)^\times$. If $n=2^k$ then the integers coprime to $n$ are precisely the odd integers, so $\phi(n)=2^{k-1}$. So $\hbox{ord}_n(a)=2^j$ for some $j\le k-1$. If $j there is nothing to prove. Otherwise, suppose that $j=k-1$. This means $a$ is a primitive root modulo $n$. A well-known theorem says that primitive roots exist only for $2,4,p^k,2p^k$ for $p$ an odd prime. Hence $n$ must be $2$ or $4$$\square$

On the other hand:

Proposition. If there is a primitive root modulo $n$, then $\hbox{im}(f)=\{\pm 1\}$.

Proof. Let $\phi(n)=2^qm$, where $m$ is odd. Let $a$ be a primitive root modulo $n$. Then $\hbox{ord}_n(a^m)=2^q$, so $\phi(n)/\hbox{ord}_n(a^m)=m$ is odd, and so $f(a^m)=-1$. $\square$

So both cases in fact occur infinitely often.

I don’t know whether it might be possible to completely classify the integers based on $\hbox{im}(f)$, nor do I know what any of this actually means, but perhaps it is something worth pondering.