\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Permutations.}
\end{center}

\noindent 1. Definition and cycle notation.

\medskip

\noindent {\bf Definition:}  A {\it permutation} of a set $N$ is a
bijective function $\pi \colon N\rightarrow N$.  $S_{n}$ will denote
the set of permutations of $N = \{1,2,\ldots,n \}$.

Let's first count the permutations.  Clearly a function $\pi \colon
N\rightarrow N$ is bijective iff injective iff surjective, since both
range and domain have $n$ elements.  So permutations can be counted either
as injective functions $\pi \colon N\rightarrow N$ for $(n)_{n} = n!$,
or as surjectives $\pi \colon N\rightarrow N$ for $n!S(n,n) = n!$.
Either way,
$$ |S_{n}| = n! $$

Two-line notation for permutations is:  in the first row write the
elements of $N$, in the second row write them rearranged so $\pi(x)$
is below $x$.  For example,
$$ \pi = \left(\begin{array}{cccccc}
1&2&3&4&5&6\\
3&5&1&4&6&2
\end{array} \right) $$
means $\pi (1) = 3$, $\pi (2) = 5$, and so on.
Sometimes we may just write the bottom row, with the order of the top
row understood, such as $351462$ for this permutation.
Note that in this fashion,
what we are now calling a permutation
(namely, a mapping from $[n]$ to itself)
can be seen to be equivalent to
what we used to call a permutation
(namely, a listing of the elements of $[n]$).

More informative than two-row notation is {\it cycle notation}.  We
say that $(a_{1},\ldots,a_{l})$ is a {\it cycle} of $\pi $ if $\pi
(a_{1}) = a_{2}$, $\pi (a_{2}) = a_{3}$, and so on, with $\pi (a_{l})
= a_{1}$.  In words, $\pi $ maps each member of the cycle to the next
one, and the last member back to the first.

The permutation $\pi $ above has two cycles: $(1\;3)$, $(2\;5\;6)$,
and $(4)$.  Notice the meaning of $(4)$ is that $\pi $ maps $4$ to
itself.  We say that $4$ is a {\it fixed point} of $\pi $.
These three cycles account for all the elements of $N$ in
this example, so we can write $\pi $ in cycle notation as
$$ \pi  = (1\;3)(2\;5\;6)(4). $$
Conventionally, we omit 1-cycles with the understanding that any
elements not explicitly mentioned are fixed points, thus we can also
write
$$ \pi  = (1\;3)(2\;5\;6). $$

In order to justify using cycle notation, we ought to prove that every
permutation can be so expressed.

\noindent {\bf Theorem:} Given any permutation $\pi $ of $N$, the
elements of $N$ are uniquely partitioned into cycles by $\pi $.

Proof: Select an element $a\in N$.  Define $C\subseteq N$ to be the
set of elements $a$, $\pi (a)$,$\pi (\pi (a)),\ldots$.  Our idea of course
is that $C$ is the cycle containing $a$.  Now $C$ is defined so that
for any $x\in C$ we have also $\pi (x)\in C$.  Thus $\pi $ restricts
to a function $\pi_{C} :C\rightarrow C$, which is injective.  Hence
$\pi _{C}$ is a permutation of $C$ and in particular, $a = \pi (x)$
for some $x\in C$.  This says the sequence $a,\pi (a),\pi (\pi
(a)),\ldots$ eventually returns to $a$.  Therefore it forms a cycle.
We have now shown that every element $a\in N$ belongs to some cycle.
But it is clear that once you specify one element of a cycle, the rest
of the cycle is determined by $\pi $, showing that the cycle
containing $a$ is unique and thus no two cycles overlap.  End of
proof.

Note that it doesn't matter in what order you list the cycles; the
notations still specify the same partition.  It also doesn't change
the partition if you ``rotate'' a cycle, thus $(1\;3\;2\;4\;5)$ is the
same as $(2\;4\;5\;1\;3)$.  For instance, our example above can also
be written
$$ \pi  = (5\;6\;2)(3\;1). $$

\medskip

\noindent 2.  Composition and inverses.

\medskip

We combine permutations by functional composition.  Given $\pi \colon
N\rightarrow N$ and $\sigma \colon N\rightarrow N$, the composite
function $\pi \sigma \colon N\rightarrow N$ is a composition of
bijections, hence itself a bijection and a permutation.  Always
remember that $\pi \sigma $ means {\it first apply $\sigma $, then
$\pi $}, so that $\pi \sigma (x) = \pi (\sigma (x))$.

Example: $\pi  = (1\;3)(2\;5\;6)$ just as before, $\sigma  = (2\;6\;4)$.
Then $\pi \sigma (1) = \pi (\sigma (1))= \pi (1) = 3$; $\pi \sigma (3)
= \pi (\sigma (3)) = \pi (3) = 1$, so $(1\;3)$ is a cycle of $\pi
\sigma $.  Likewise we find the cycle of $2$ and so on, until we get 
$$ \pi \sigma  = (1\;3)(2)(4\;5\;6)\quad\mbox{{\rm or simply}}\quad
(1\;3)(4\;5\;6). $$ 

It might seem the notation $(1\;3)(2\;5\;6)$ is ambiguous.  Does it
mean (a) the permutation with cycles $(1\;3)$ and $(2\;5\;6)$ or (b)
the product of the permutation $(1\;3)$ and the permutation
$(2\;5\;6)$?  Fortunately, there is no problem: as long as we are
writing disjoint cycles, these permutations are the same.  Thus the
notation is actually helpful rather than ambiguous.

Since a permutation is a bijection, it has an inverse.  This can be
neatly expressed in terms of composition.  Let us use the symbol ${\bf
1}$ for the {\it identity} permutation ${\bf 1}(x) = x$, that is,
$$ {\bf 1} = \left(\begin{array}{cccccc}
1&2&3&4&5&6\\
1&2&3&4&5&6
\end{array} \right) = (1)(2)(3)(4)(5)(6) $$
in $S_{6}$ (each set $N$ has its own identity permutation).  The
inverse property is then simply
$$ \pi \pi ^{-1} = {\bf 1} = \pi ^{-1}\pi . $$
Moreover, it is simple to compute $\pi ^{-1}$ in cycle notation.  Just
reverse each cycle.  In our example,
$$ \pi  =  (1\;3)(2\;5\;6),\quad \pi ^{-1} = (3\;1)(6\;5\;2).$$
From this you can see simple facts such as: a permutation has the same
collection of cycle lengths as its inverse; a permutation is its own
inverse iff it has only fixed points and 2-cycles (such a permutation
is called an involution).  An involution that consists of a single 2-cycle
and $n-2$ fixed points (that is, a permutation of the form $(i \ j)$)
is called a {\it transposition}.

\medskip

\noindent 3.  Inversions and sign.

When $\pi \in S_{n}$ is a permuation, we say that a pair $\{i,j\}$ of
numbers from $\{1,\ldots,n \}$ is an {\it inversion} of $\pi $ if
$\pi $ maps them to numbers in the opposite order.  That is, if $i<j$,
for $\{i,j \}$ to be an inversion means $\pi (i)>\pi (j)$.  Inversions are
easiest to recognize by writing $\pi ^{-1}$ in row notation.  Then $\{i,j \}$
is an inversion iff $i$ and $j$ appear out of order.
(Note: This is different from Brualdi's definition!)

Example: $\pi  = 351462 $ as before.  Its inverse is $\pi ^{-1} = 361425$.
The inversions are $\{1,3 \}$,$\{1,6 \}$,$\{2,3 \}$,$\{2,4 \}$,$\{2,6
\}$,$\{4,6 \}$, and $\{5,6 \}$.  There are seven
altogether.
(Brualdi would say that the inversions of $\pi$
are $(3,1)$, $(3,2)$, $(4,2)$, $(5,1)$, $(5,2)$, $(5,4)$, $(6,2)$.
But both would agree that the total number of inversions is 7,
because both are really counting the same ``things'' --
just labelling them in different ways.)

The minimum possible number of inversions is 0, for the identity
permutation.  The maximum is ${n\choose 2 } = n(n-1)/2$, for the permutation
$n\;(n-1)\cdots 1$ in which every pair is an inversion.  The number of
permutations in $S_{n}$ with $k$ inversions is called the {\it
inversion number} $i(n,k)$.  We studied these in some homework problems;
in particular,
we showed that the generating function $\sum_{k=0}^{n(n-1)/2} i(n,k) x^k$
is $\prod_{j=1}^n (1+x+x^2+...+x^{j-1})$.

  It is also interesting to count {\it adjacent} inversions,
usually called {\it descents}.  In our example $\pi ^{-1} = 361425$
the two descents are $61$ and $42$.  The number of descents possible ranges
from a $0$ to $n-1$, with the same examples as for inversions giving
the minimum and maximum.  The number of permutations in
$S_{n}$ with $k$ descents is called the {\it Eulerian number} $A(n,k)$
and also can be studied using generating functions.

A permutation is called {\it odd} or {\it even}, according as its
number of inversions is odd or even.  We say that the {\it sign} of
$\pi $ is 
$$ \epsilon (\pi ) = \left\{\begin{array}{r@{\quad }l}
+1	&\pi \quad \mbox{{\rm even}}\\
-1	&\pi \quad \mbox{{\rm odd.}}
\end{array} \right. $$
Our example is odd, and its sign is $\epsilon (\pi ) = -1$.

The sign is of interest because of the following property.

% \noindent {\bf Definition:} A {\it transposition} is a permutation of
% the form $(i\;j)$.  That is, it simply exchanges two numbers and fixes
% all the others.

\noindent {\bf Theorem:} Composing with a transposition changes the
sign.  In symbols, if $\tau $ is a transposition and $\pi $ is any
permutation, then $\epsilon (\tau \pi) = -\epsilon (\pi ) $.

Proof.  Express $\pi^{-1} $ as $a_{1}a_{2}\cdots a_{n}$ in one-row
notation.  Then $(\tau \pi)^{-1} = \pi ^{-1} \tau ^{-1} =\pi ^{-1}\tau
$ will have the
same one-row notation,
except that two of the $a$'s will be switched, namely $a_{i}$ and
$a_{j}$, where $\tau  = (i\;j)$.  The pair $a_{i},a_{j}$ gets
reversed, adding or subtracting one from the total number of inversions.
Inversions not involving $a_{i}$ and
$a_{j}$ remain unchanged.  Inversions involving $a_{i}$ or $a_{j}$ and
an $a$ preceding or following both $i$ and $j$ also remain unchanged.
What remains are pairs $a_{i},a_{k}$ and $a_{j},a_{k}$ with $k$ in
between $i$ and $j$.  For each such $k$, both pairs get reversed,
changing the number of inverions by 0 or $\pm 2$.  The net change in
number of inversions from all of this is then odd, so the sign
changes.

Now every permutation can be composed up out of transpositions
(exercise), so composing with any permutation $\sigma $ is the same as
composing 
with the number of transpositions it takes to express $\sigma $, and
this number will be even or odd according to the sign of $\sigma $.
Consequently the previous theorem gives the {\it sign formula:}
$$ \epsilon (\pi \sigma ) = \epsilon (\pi )\epsilon (\sigma ). $$

Using the sign formula we can easily compute $\epsilon (\pi )$ from
its cycle structure.  You can verify that an $n$-cycle can be composed
out of $n-1$ transpositions, and is thus even if $n$ is odd and odd if
$n$ is even.  It follows that
$$ \epsilon (\pi ) = (-1)^{\mbox{{\rm number of even cycles}}} $$.

% It turns out that for $n>1$, exactly half of the permutations in $S_n$
% are even, and half are odd.  (Proof: if $\tau$ is any transposition,
% then the map that sends $\pi$ to $\tau \pi$ gives a pairing between
% the odd permutations and the even permutations.)

\medskip

4. Stirling numbers of the first kind.

\medskip

In previous notes we defined the Stirling numbers $s(n,k)$ as a sort
of inverse to the Stirling numbers $S(n,k)$.  Some turned out to be
negative, so we defined $c(n,k) = |s(n,k)|$ to be the {\it signless
Stirling numbers of the first kind}.  We then had the recurrence
$$ c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k) $$
with starting values $c(1,k) = 1$ if $k = 1$, $0$ otherwise.

In a homework problem, we described something that these numbers count,
namely, ways of seating people at tables.
We can now describe a more fundamental significance of these numbers.

\noindent {\bf Theorem:} $c(n,k)$ is the number of permutations in
$S_{n}$ that have $k$ cycles.

Proof.  Let $c^{*}(n,k)$ be the number of permutations in question.
When $n = 1$ we certainly have $c^{*}(1,k) = c(1,k)$ since
since there is
only the permutation ${\bf 1} = (1)$ and it has 1 cycle.  Now we
need only verify the recurrence.

Let us count permutations with $k$ cycles in $S_{n}$ as follows.
First, count those in which $(1)$ is a cycle.  To choose such a
permutation is to choose the other $k-1$ cycles permuting $\{2,\ldots,n \}$.
There are $c^{*}(n-1,k-1)$ possibilities for this.

Second, count permutations $\pi $ in which $1$ belongs to a cycle with other
elements.  If we were to erase $1$ from the cycle notation for $\pi $
we would have left a $k$ cycle permutation $\sigma $ of $\{2,\ldots,n \}$ and
there are $c^{*}(n-1,k)$ possibilities for this.  Now we must ask, how
many places could $1$ have been erased from?  Well it could have been
in any cycle, and its position in that cycle could have been after any
member of the cycle.  In short, it could have been after any of the
$n-1$ elements making up all the cycles of $\sigma $, for $n-1$
choices.

Thus we have shown that $ c^{*}(n,k) = c^{*}(n-1,k-1) +
(n-1)c^{*}(n-1,k) $, and since this is the same recurrence that gives
$c(n,k)$ we find $c^{*}(n,k) = c(n,k)$.

If this proof looked familiar, that's not surprising:
there is a natural bijection 
between the ways of seating $n$ people at $k$ tables
and the permutations of $n$ that consist of $k$ cycles.
For, given a cycle $(a_1,...,a_l)$ of the permutation $\pi$,
we can seat the corresponding people
at a table, arranged counter-clockwise;
in this way,
the permutation determines a seating-arrangement.
Conversely,
given a seating arrangement,
define $\pi$ by sending $i$ to $j$
iff person $j$ is sitting to the right of person $i$.
Then a seating arrangement with $k$ tables
gives rise to a permutation with $k$ cycles.

\medskip

5. Derangements.

\medskip

A {\it derangement} is a permutation $\pi$
such that for all $i$, $\pi(i) \neq i$.
That is, it is a permutation without fixed points --
all of its cycles are of length 2 or more.

It is easy to check that these permutations
do indeed correspond to what we used to call derangements
(back when permutations meant listings of a set
and not bijections of a set with itself).
But the new viewpoint sheds new light on old results.

For instance,
let derive a recurrence relation for $D_n$.
We start by observing that
if $\pi$ is a derangement of $[n]$,
then, in the cycle decomposition of $\pi$,
the integer $n$ belongs to either a 2-cycle or some longer cycle.

Case I:
If it belongs to a 2-cycle,
take away both $n$ and $\pi(n)$
(which can be any one of $1,2,...,n-1$);
what results is a derangement of a set with $n-2$ elements.
The number of possibilities for this alternative is thus $(n-1)D_{n-2}$.

Case II:
If $n$ belongs to a cycle of length 3 or more,
then snipping $n$ from the cycle and closing the cycle up
(that is, sending $\pi^{-1}(n)$ to $\pi(n)$,
by-passing $n$ itself)
results in a derangement of $[n-1]$.
Conversely, given any derangement of $[n-1]$,
there are $n-1$ places to cut it open
and re-insert the $n$.
The number of possibilities for this alternative is thus $(n-1)D_{n-1}$.

Adding together the number of possibilities for the two cases,
we see that $$D_n = (n-1)D_{n-2}+(n-1)D_{n-1}.$$
\end{document}
