\centerline{\bf Linear orders, cyclic orders and
permutations\strut}
\centerline{Miguel Carri\'on \'Alvarez\strut}

\proclaim 1, 2. Generating functions.

The empty set is vacuously ordered in one way; a $1$-element set is
trivially ordered in~$1$ way; and an $n$-element set can be linearly
ordered by choosing a maximal element in one of~$n$ ways and linearly
ordering the remaining $(n-1)$-element subset. Hence, $|L_n|=n!$ and
$$
|L|(z)=\sum_{n\ge 0}{|L_n|\over n!}z^n=\sum_{n\ge 0}z^n={1\over 1-z}.
$$

The empty set admits no cyclic orders. If~$\{x_1,x_2,\ldots,x_n\}$ is
an~$n$-element set, the
map
$$
x_1<x_2<\cdots<x_n\mapsto(x_1\,x_2\,\ldots\,x_n)
$$ 
is an $n$-to-$1$ and onto function from linear orders to cyclic
permutations Therefore, $|C_n|={1\over n}|L_n|$ (except for~$C_0=0$) and
$$
|C|(z)=\sum_{n\ge 1}{z^n\over n}=\ln\left({1 \over 1-z}\right).
$$

It follows that
$$
{d\over dz}|C|(z)=|L|(z);
\qquad
{d\over dz}|L|(z)=|L|^2(z);
\qquad\hbox{and}\quad
e^{|C|(z)}=|L|(z).
$$

\proclaim 3. Structure type isomorphisms.

A ${D\over DZ}C$-structure on an~$n$-element set is a pointed
$C$-structure on an $(n+1)$-element set. But this is equivalent to a
linear order starting with the basepoint and increasing by the action
of the cyclic permutation, so it provides a linear order of the
original~$n$-element set. Conversely, a linear order on an $n$-element
set can be turned into a pointed cyclic order on an $(n+1)$-element
set by inserting the basepoint between the maximal and minimal
elements for the linear order. Hence,
$$
{D\over DZ}C\cong L.
$$

Similarly, a pointed linear order on an~$(n+1)$-element set is
equivalent to an ordered partition of an~$n$-element set into two
linearly ordered (possibly empty) subsets. Conversely, given an
ordered pair of linealy ordered sets having jointly~$n$ elements, one
can insert a basepoint between the first and second sets and obtain a
pointed linear order on an $(n+1)$-element set. Therefore,
$$
{D\over DZ}L\cong L^2
$$

Finally, observe that a cyclic permutation is a ``connected
permutation'' and that exponentiation of structure types corresponds
to building possibly disconnected structures from connected
ones. Indeed, any permutation has a unique cycle decomposition, which
is a partition of the original set into a collection of orbits of
cyclic permutations. Hence, 
$$
E^C\cong P.
$$
Although~$|P|=|L|$, a linear order is not a permutation. For each
finite set, the permutations on it form a group~$P_n$, and the linear
orders form a $P_n$-torsor. There can be no canonical isomorphism
between the two.

\proclaim 4. The groupoid cardinality of~$C(1//2!)$.

We have
$$
|C(1//2!)|=\ln\left({1\over 1-{1\over 2}}\right)=\ln 2.
$$

\bye

