%%&latex

        \hfuzz = 100pt
%        \renewcommand{\b}{\bullet}
%        \newcommand{\hf}{\(\frac{1}{2}\)}
%        \newcommand{\third}{\frac{1}{3}}
%        \newcommand{\minustwothirds}{-\frac{2}{3}}
%        \newcommand{\fourthirds}{\frac{4}{3}}
%        \newcommand{\ISpin}{\mathrm {ISpin}}
%        \newcommand{\End}{\mathrm {End}}
%        \newcommand\F{\mathbf {F}}
%        \newcommand\G{\mathbf {G}}
%        \newcommand\HH{\mathbf {H}}
        \newcommand\Z{\mathbb Z}
%        \newcommand\R{\mathbb R}
%        \newcommand\C{\mathbb C}
%        \renewcommand\H{\mathbb H}
%        \newcommand\K{\mathbb K}
%        \renewcommand\O{\mathbb O}
%        \newcommand\RP{\mathbb {RP}}
%        \newcommand\CP{\mathbb {CP}}
%        \newcommand\HP{\mathbb {HP}}
%        \newcommand\KP{\mathbb {KP}}
%        \newcommand\OP{\mathbb {OP}}
%        \renewcommand\P{\mathbb P}

%        \newcommand{\Cliff}{\mathrm {Cliff}}
%        \newcommand{\J}{\mathrm {J}}
%        \newcommand{\M}{\mathrm {M}}

%        \renewcommand\S{\mathrm {S}}
%        \newcommand{\OO}{\mathrm {O}}
%        \newcommand{\SO}{\mathrm {SO}}
%        \newcommand{\SL}{\mathrm {SL}}
%        \newcommand{\PSL}{\mathrm {PSL}}
%        \newcommand{\SU}{\mathrm {SU}}
%        \newcommand{\Sp}{\mathrm {Sp}}
%        \newcommand{\Spin}{\mathrm {Spin}}
%        \newcommand{\Pin}{\mathrm {Pin}}
%        \newcommand{\U}{\mathrm {U}}
%        \newcommand{\E}{\mathrm {E}}
%        \newcommand{\so}{\mathfrak {so}}
%        \newcommand{\Sl}{\mathfrak {sl}}
%        \newcommand{\symp}{\mathfrak {sp}}
%        \renewcommand{\u}{\mathfrak {u}}
%        \newcommand{\e}{\mathfrak {e}}
%        \newcommand{\f}{\mathfrak {f}}
%        \newcommand{\g}{\mathfrak {g}}
%        \newcommand{\su}{\mathfrak {su}}
%        \renewcommand{\a}{\mathfrak {a}}
%        \newcommand{\sa}{\mathfrak {sa}}
%        \newcommand{\h}{\mathfrak {h}}
%        \newcommand{\sh}{\mathfrak {sh}}
%        \newcommand{\coll}{\mathfrak {coll}}
%        \newcommand{\isom}{\mathfrak {isom}}
%        \newcommand{\Isom}{\mathrm {Isom}}
%        \newcommand{\Der}{\mathfrak {der}}
%        \newcommand{\Tri}{\mathfrak {tri}}
%        \newcommand{\et}{\hspace{-0.08in}\textbf {.}\hspace{0.1in}}
%        \newcommand{\DOT}{\hspace{-0.08in}\textbf {.}\hspace{0.1in}}
%        \newcommand{\BOX}{\hbox {\(\sqcap\) \kern -1em \(\sqcup\)}}
%        \newcommand{\qed}{\hskip 3em \hbox{\BOX} \vskip 2ex}
%        \renewcommand{\Re}{\mathrm {Re}}
%        \renewcommand{\Im}{\mathrm {Im}}
%        \newcommand{\Hom}{\mathrm {hom}}
%        \newcommand{\Aut}{\mathrm {Aut}}
%        \newcommand{\Inv}{\mathrm {Inv}}
%        \newcommand{\tensor}{\otimes}
%        \newcommand{\iso}{\cong}
        \newcommand{\implies}{\Longrightarrow}
%        \newcommand{\impliedby}{\Longleftarrow}

%        \newcommand{\be}{\begin{equation}}
%        \newcommand{\ee}{\end{equation}}
%        \newcommand{\ba}{\begin{eqnarray}}
%        \newcommand{\ea}{\end{eqnarray}}
        \newcommand{\ban}{\begin{eqnarray*}}
        \newcommand{\ean}{\end{eqnarray*}}

%        \newcommand{\ad}{\mathrm {ad}}
%        \newcommand{\Cob}{\mathrm {Cob}}
%        \newcommand{\Vect}{\mathrm {Vect}}
%        \newcommand{\Hilb}{\mathrm {Hilb}}
        \newcommand{\maps}{\colon}
%        \newcommand{\tr}{\mathrm {tr}}
%        \newcommand{\rank}{\mathrm {rank}}
%        \newcommand{\id}{\mathrm {id}}
%        \newcommand{\Fun}{\mathrm {Fun}}
%        \newcommand{\Ad}{\mathrm {Ad}}
%        \newcommand{\om}{\omega}
%        \newcommand{\eps}{\epsilon}

%        \newtheorem{thm}{Theorem}
%        \newtheorem{prop}{Proposition}
%        \newtheorem{lemma}{Lemma}
%        \newtheorem{corollary}{Corollary}
%        \newtheorem{ex}{Example}

\documentclass{article}
\usepackage{amsfonts,amssymb}
\usepackage[all]{xy}
%\usepackage{latexsym}

\catcode `\@ 11
\renewcommand \( {\leavevmode \sw@slant \math }
\catcode `\@ 12

\let \enddisplaymath \]
\def \]#1 {\mbox {#1}\enddisplaymath }

\bigskipamount 1 em

\newenvironment {commentary}
 {\itshape \bigbreak \noindent \ignorespaces }
 {}

\newenvironment {hint}
 {\begin {commentary} Hint:}
 {\end {commentary}}

\newcount \questioncount
\questioncount 0
\newenvironment {question}
 {\global \advance \questioncount 1
  \bigbreak \noindent \the \questioncount . \ignorespaces }
 {}

\newenvironment {answer}
 {\slshape \bigbreak \noindent \ignorespaces }
 {}

\newcommand \strong [1] {\textup {\textbf {#1}}}

\newcommand \eq {{}\mkern - 5 mu &
 \mkern - 5 mu {=}\mkern - 5 mu & \mkern - 5 mu {}}

%\let \dotsp \textellipsis
\renewcommand \textellipsis
 {.\kern \fontdimen 3 \font .\kern \fontdimen 3 \font .}
\newcommand \dotss {\dots \ }

\newcommand \LN {\mathop {\mathrm {LN}}}

\newcommand \wkfract [2] {{#1/\!/#2}}

        \textwidth 6in
        \textheight 8.5in        \evensidemargin .25in
        \oddsidemargin .25in
        \topmargin .25in
        \headsep 0in
        \headheight 0in
        \footskip .5in
%If you want single spaced copy, delete the next two lines.
% \parskip 1.75\parskip plus 3pt minus 1pt
% \renewcommand{\baselinestretch}{1.5}
        \pagestyle{empty}
        \begin{document}

        \begin{center}
        \textbf {Linear Orderings, Cyclic Orderings and Permutations}\\
        {\small Questions by: John C.\ Baez, April 1, 2004}\\
        {\small Answers by: Toby Bartels\footnote
{I reserve no legel rights whatsoever to any of my creative work;
see \texttt {http://toby.bartels.name/copyright/}.}, 2004 April 8}\\
        \vspace{0.3cm}
        \end{center}

\begin {commentary}
A \strong {linear ordering} of a set \(S\), also called a
\strong {total ordering}, is a binary relation \(<\) on \(S\) that is:
\begin{itemize}
\item irreflexive (\(x \nless x\)),
\item asymmetric (\(x < y \implies y \nless x\)),
\item transitive (\(x < y \ \& \ y < z \implies x < z\))
\item and linear (\(x \ne y \implies x < y \ \mathrm {or} \ y < x\)).
\end{itemize}
In pictures, a linear ordering looks something like this:
\vskip 0.5em
\[
 \xy
(-20,0)*+{\bullet}="A";
(-10,0)*+{\bullet}="B";
  (0,0)*+{\bullet}="C";
 (10,0)*+{\bullet}="D";
 (20,0)*+{\bullet}="E";
     {\ar_{} "A";"B"};
     {\ar_{} "B";"C"};
     {\ar_{} "C";"D"};
     {\ar_{} "D";"E"};
\endxy
\]
\vskip 0.5em
\noindent
A `cyclic ordering', on the other hand, looks like this:
\[
 \xy 0 ;/r.18pc/:
(-12,10)*+{\bullet}="TL"; (12,10)*+{\bullet}="TR";
(-18,0)*+{\bullet}="ML"; (18,0)*+{\bullet}="MR"; (0,-10)*+{\bullet}="B";
     {\ar_{} "B";"ML"};
     {\ar^{} "ML";"TL"};
     {\ar_{} "MR";"B"};
     {\ar^{} "TR";"MR"};
     {\ar^{} "TL";"TR"};
\endxy
\]
More formally, we can
define a \strong {cyclic ordering} of the finite set \(S\) to be a
permutation \(\sigma \maps S \to S\) with exactly one orbit.  The permutation
maps each element of \(S\) to the `next one on the cycle'.
We can also define a cyclic ordering
to be an equivalence class of linear orderings,
where the linear ordering of \(\{x_1,\ldots,x_n\}\) with
\[    x_1 < x_2 < \cdots < x_{n-1} < x_n  \]
is equivalent to the total ordering with
\[    x_n < x_1 < x_2 < \cdots < x_{n-1}  \].
(``And the last shall be first.''\ --- Matthew 19.)
However, this definition is valid only if \( S \) is nonempty;
the empty set has no cyclic ordering
(because its unique permutation has zero orbits).

Let \(L\) be the structure type ``being a linearly ordered finite set'',
and let \(C\) be the structure type ``being a cyclically ordered finite set''.
There are some nice relations between these two structure types.
\end {commentary}

\begin {question}
Compute the generating functions \(|L|\) and \(|C|\) directly, by counting the
number of linear orderings and cyclic orderings on an \(n\)-element set.
\end {question}

\begin {answer}
To linearly order a set with \( n \) elements,
first pick the first element (in \( n \) possible ways),
then pick the next element (in \( n - 1 \) possible ways),
then \dotss then pick the last element (in \( 1 \) possible way).
Thus the number of ways to linearly order a set with \( n \) elements
is \( n ! \).
Therefore,
\[ | L | = \sum _ { n = 0 } ^ { \infty } \frac { n ! } { n ! } z ^ n
= \sum _ { n = 0 } ^ { \infty } z ^ n = \frac 1 { 1 - z } \].

To cyclically order a set with \( n > 0 \) elements,
linearly order it in \( n ! \) ways if you like;
but then notice that this is overdetermined by a factor of \( n \),
since we should not have been able to tell which of \( n \) positions
is the starting position.
Thus the number of ways to cyclically order a set with \( n > 0 \) elements
is \( ( n - 1 ) ! \).
On the other hand, the empty set can't be cyclically ordered,
so the number of ways to cyclically order a set with \( 0 \) elements
is \( 0 \).
Therefore,
\[ | C | = \sum _ { n = 1 } ^ { \infty } \frac { ( n - 1 ) ! } { n ! } z ^ n
= \sum _ { n = 1 } ^ { \infty } \frac 1 n z ^ n \].
I could find a closed form for \( | C | \) now,
but it's easier to do this in the context of question 2..
\end {answer}

\begin {question}
Using 1.\ show that
\[       \frac {d} {dz} |C| = |L|   \]
\[       \frac {d} {dz} |L| = |L|^2  \]
\[              e^{|C|}     = |L|  \].
\end {question}

\begin {answer}
Differentiating term by term,
\[ \frac d { d z } | C |
= \sum _ { n = 1 } ^ \infty \frac d { d z } \frac 1 n z ^ n
= \sum _ { n = 1 } ^ \infty z ^ { n - 1 }
= \sum _ { n = 0 } ^ \infty z ^ n = | L | \].

Now using a closed form,
\[ \frac d { d z } | L | = \frac d { d z } \frac 1 { 1 - z }
= \frac 1 { ( 1 - z ) ^ 2 } = | L | ^ 2 \].

Now combining these facts,
\[ \frac d { d z } | L | = | L | ^ 2 = | L | \frac d { d z } | C | \],
or \[ \frac d { d z } | C | = \frac 1 { | L | } \frac d { d z } | L |
= \frac d { d z } \ln | L | \].
Also \( | C | ( 0 ) = | C | _ 0 = 0 \) and \( | L | ( 0 ) = | L | _ 0 = 1 \),
so \( | C | ( 0 ) = \ln | L | ( 0 ) \).
Therefore, \( | C | = \ln | L | \), or \( | L | = e ^ { | C | } \).
(Note that \( | L | \) has an inverse and a logarithm,
since \( | L | _ 0 > 0 \).)

I can now write down a closed form for \( | C | \);
\[ | C | = \ln | L | = \ln \frac 1 { 1 - z } = - \ln ( 1 - z ) \].
\end {answer}

\begin {question}
Do the above equations between generating
functions come from natural isomorphisms
between the structure types?  Show that
\[    \frac {D} {DZ} C \cong L  \]
and
\[    \frac {D} {DZ} L \cong L^2  \]
but
\[          E^{C}     \ncong  L  \].
\end {question}

\begin {hint}
Hint: for the last one,
let \(P\) be the structure type ``being a finite set equipped with
a permutation of its elements''.  Show that
\(E^{C}      \cong P \)
and \(P \ncong L\).
\end {hint}

\begin {answer}
To place a \( \frac D { D Z } C \) structure on a set \( S \),
adjoin a point and then cyclically order the result \( S + \).
By starting with the adjoined point and ordering from there,
this defines a linear order on \( S \).
Conversely, if \( S \) has been linearly ordered,
then we may cyclically order \( S + \)
by mapping each point to the next in order,
with the extra point serving on the boundary.
These transformations are inverses of each other,
so \( \frac D { D Z } C \cong L \).

To place a \( \frac D { D Z } L \) structure on a set \( S \),
adjoin a point and then linearly order the result \( S + \).
The new point will break \( S \) up into pieces
(one before the point and one after it),
each of which will be linearly ordered,
giving an \( L ^ 2 \) structure on \( S \).
Conversely, if \( S \) has an \( L ^ 2 \) structure,
then linearly order \( S + \) by
going through the one subset of \( L \) in order,
then the new point, then the other subset of \( L \) in order.
These transformations are inverses of each other,
so \( \frac D { D Z } L \cong L ^ 2 \).

At this point, I should be able to calculate
\( \frac D { D Z } C = \frac D { D Z } \LN L \)
and \( C ( 0 ) \cong \LN L ( 0 ) \),
although \( \LN \) hasn't yet been covered fully in class.
Even so, this is insufficient to conclude
that \( C \cong \LN L \) and then \( E ^ C \cong L \),
since differential equations don't have unique solutions.
Indeed, \( E ^ C \ncong L \), as stated.

For, to place an \( E ^ C \) structure on a set \( S \),
partition \( S \) and cyclically order each piece.
Since each point \( x \) of \( S \) belongs to a unique piece,
whose cyclic ordering assigns \( x \) a value,
this defines a single permutation on all of \( S \).
Conversely, given a permutation \( p \) on \( S \),
the orbits of \( p \) form a partition of \( S \),
each piece of which has a single orbit of the partition,
which is a cyclic order.
These transformations are inverses of each other,
so \( E ^ C \cong P \).

Now suppose that \( P \cong L \) through a natural isomorphism \( H \).
Then in particular, \( P _ 2 \cong L _ 2 \) through a bijection \( H _ 2 \).
Now, \( P _ 2 \) is the set of permuations of \( 2 = \{ 0 , 1 \} \);
these permutations
are \( i : = \{ ( 0 , 0 ) , ( 1 , 1 ) \} \)
and \( t : = \{ ( 0 , 1 ) , ( 1 , 0 ) \} \).
On the other hand, \( L _ 2 \)
is the set of linear orderings of \( 2 = \{ 0 , 1 \} \);
these linear orderings
are \( f : = \{ ( 0 , 1 ) \} \) and \( b : = \{ ( 1 , 0 ) \} \).
Now, \( H _ 2 \) maps \( i \) to either \( f \) or \( b \), not both.
Either way, it must respect the automorphisms of \( 2 \),
since it comes from a natural isomorphism.
In particular, \( H _ 2 \) must respect
the involution \( \tau \) that swaps \( 0 \) to \( 1 \).
(Yes, \( t \) and \( \tau \) are literally the same thing,
but they are playing very different roles here.)
Now, \( P _ \tau \) fixes \( i \),
but \( L _ \tau \) swaps \( f \) with \( b \).
This is a contradiction; therefore, \( P \ncong L \).
\end {answer}

\begin {commentary}
\(P\) and \(L\) are an interesting pair of structure types.
Even though a permutation is very different from a linear order:
\[       P \ncong L  \]
there are just as many permutations of a finite set as linear orders on it:
\[       |P| = |L|   \]
and we've seen above that both can be defined in terms of cyclic orderings:
\[       P \cong E^{C} , \qquad \qquad L \cong \frac {DC} {DZ}   \].
\end {commentary}

\begin {question}
Let \(\wkfract 1{2!}\) be the groupoid with one object and \(\Z_2\) as the
group of automorphisms of this object, so that
\[          |\wkfract 1{2!} \,| = 1/2  \].
Calculate the groupoid cardinality of \(C(\wkfract 1{2!})\).  This is
the groupoid of `half-colored cyclically ordered finite sets'.
\end {question}

\begin {answer}
Knowing the generating function for \( C \), this is easy:
\[ | C ( \wkfract 1 { 2 ! } ) | = | C | ( | \wkfract 1 { 2 ! } | )
= - \ln ( 1 - 1 / 2 ) = \ln 2 \].
\end {answer}

\end{document}
