Permutations

In a course on mathematical analysis, Stirling's formula is proved

where $e=2,718281 \ldots$ is the base of the natural logarithm, $\pi =3,141592 \ldots$; here the symbol $\sim$ means that the ratio $\sqrt{2 \pi n} n^{n} e^{-n} / n$ ! tends to 1 as $n \rightarrow \infty$.

Using Stirling's formula, which gives an approximation from below, verify that $100 !>(9,33 \ldots ) 10^{157}$. How many cycles of length $100$ are there in $S_{100}$?

Find the order of permutation (4) and of the permutation

A permutation $\pi$ of the form (3) with $m$ independent cycles leaves

symbols (or points) fixed. The number $d(\pi )=n-\left(m+m^{\prime }\right)$ is called the decrement of the permutation $\pi$. Verify that $\varepsilon_{\pi }=(-1)^{d(\pi )}$.

Find the sign of the permutation

Let $\Omega =\left\{ 1,2, \ldots , n\right\} , \Omega \times \Omega$ be the Cartesian square. We call a pair $(i, j) \in \Omega \times \Omega$ an inversion with respect to a permutation $\sigma \in S_{n}$ (or, more briefly, a $\sigma$-inversion), if $i<j$ but $\sigma (i)>\sigma (j)$. Let us set

Since $(\sigma (j)-\sigma (i)) /(j-i)$ is a nonzero rational number, which is negative precisely when $(i, j)$ is a $\sigma$-inversion, and since $\sigma : \Omega \rightarrow \Omega$ is a bijective map, it follows that $\operatorname {sgn} \sigma =(-1)^{k}$, where $k$ is the total number of $\sigma$-inversions. If $\tau =(i j)$ is a transposition, then $\operatorname {sgn} \tau =-1$. As is easily seen,

so that the $\sigma$-inversion $(i, j$) ceases to be an inversion with respect to the permutation $\tau \sigma$, where $\tau =(\sigma (j) \sigma (i))$ is a transposition.

Show that there exist $k$ transpositions $\tau_{1}, \ldots , \tau_{k}$ for which

is the identity permutation. Hence $\sigma =\tau_{1} \ldots \tau_{k-1} \tau_{k}$, and $\operatorname {sgn} \sigma =(-1)^{k}=\varepsilon_{\sigma }$ are two equally valid notations for one and the same invariant of the permutation; sgn (from the Latin signum) means sign. We have thus obtained yet another convenient way of determining the sign of a permutation. For instance, with respect to permutation (4) the set of inversions consists of the five pairs $(1,5),(2,5),(3,5),(4,5),(6,7)$, so that $\operatorname {sgn} \pi =-1$. In practice, the matter reduces to counting, in the bottom row of the permutation $\pi$, the number of numbers $j$ greater than $i$ but standing before $i$, for $i=1,2, \ldots , n-1$.