# Is there an interesting species whose generating function gives the zigzag numbers?

Let's say a species is a functor

$$F: \mathrm{FinSet}_0 \to \mathrm{FinSet}_0$$

from the groupoid of finite sets and bijections to itself. Let $F(n)$ be its value on your favorite $n$-element set; then its generating function is the formal power series

$$|F|(z) = \sum_{n = 0}^\infty \frac{|F(n)| z^n}{n!}$$

where the absolute value denotes cardinality.

In plain English: $F$ is a way of putting structures on finite sets, and the generating function is a power series whose $n$th coefficient is the number of ways of putting this structure on an $n$-element set, divided by $n!$.

Is there an interesting species whose generating function is $\sec z + \tan z$?

There's an answer that comes frustratingly close to being good. We have

$$\sec z + \tan z = \sum_{n = 0}^\infty \frac{A_n z^n}{n!}$$

where $A_n$ is the $n$th Euler zigzag number. This is the number of permutations $\sigma$ of the set $\{1, \dots, n\}$ that are alternating, by which I mean that

$$\sigma(1) < \sigma(2) > \sigma(3) < \sigma(4) > \cdots$$

For example, here is a picture that shows $A_4 = 5$, drawn by Robert M. Dickau: This seems nice and combinatorial. However, to define an alternating permutation of a finite set, we need to equip it with a total ordering. There is a species that assigns to any finite set its collection of total orderings together with alternating permutations... but for an $n$-element set, there are $A_{n}$ times $n!$ of these, so the generating function of this species is

$$\sum_{n = 0}^\infty A_{n} z^{n},$$

not what I want.

I believe we could fix this by creating a species $F$ that assigns to each finite set the collection of isomorphism classes of total orderings and alternating permutations, where two are considered isomorphic if they differ by the action of a permutation. However, the resulting species, if indeed it's well-defined, will be 'uninteresting' in that now

$$F: \mathrm{FinSet}_0 \to \mathrm{FinSet}_0$$

maps every permutation of a finite set to an identity morphism.

Richard Stanley has many other interpretations of the Euler zigzag numbers in A survey of alternating permutations. However, I believe they all suffer from the same problem: they count structures on totally ordered finite sets. In this situation we expect to get the ordinary generating function

$$\sum_{n = 0}^\infty A_{n} z^{n}$$

rather than the exponential generating function

$$\sum_{n = 0}^\infty \frac{A_n z^n}{n!}$$

If this is inevitable, I'd like to know why the function $\sec z + \tan z$ comes so close to being the generating function of an interesting species, yet fails! Could we get it using a species valued in some other groupoid, like the groupoid of finite-dimensional vector spaces? Or maybe some other trick?

• You want $F(6)$ to be an $S_6$-set of order $A_6=61$, which does not divide $|S_6|=720$, so the action cannot be transitive. Maybe $F(6)$ could split as a single fixed point plus an orbit of size $60$, which would have a stabiliser of order $12$. There are some obvious dihedral groups of order $12$ in $S_6$ that could be the stabilisers. Perhaps this kind of analysis might be helpful? – Neil Strickland Mar 24 '14 at 13:04
• I hadn't thought of that way of attacking the problem! – John Baez Mar 24 '14 at 13:43
• Wouldn't the representation corresponding to the zig-zag shape $\tau_n$ described in Section 3.6 of Stanley's survey qualify? Of course, that's not a permutation representation, but at least you get a functor into finite dimensional vector spaces. – Martin Rubey Mar 24 '14 at 19:56
• I don't really understand that passage of Stanley. If he gives a nontrivial functor from the groupoid of finite sets to the category of finite-dimensional vector spaces such that any $n$-element set gets mapped to a vector space of dimension $A_n$, I will be happy. ("Trivial" here means that all automorphisms get sent to identity morphisms.) – John Baez Mar 24 '14 at 23:20
• Let $n=3$, then $\tau_n$ is a square Ferrers diagram with the top-left cell missing. Let $U=\{a,b,c\}$. The functor takes $U$ to the Specht module of polytabloids of shape $\tau_n$. A basis is for example $\begin{array}{cc} & a\\ b & c\end{array}-\begin{array}{cc} & c\\ a & b\end{array}$ and the same with $b$ and $c$ interchanged. The symmetric group $\mathfrak S_{a,b,c}$ acts on this module, in particular, the transposition $(b,c)$ switches the two basis elements. – Martin Rubey Mar 25 '14 at 8:39

Here's a more self-contained description of this module. For simplicity, I'll consider only the case $n=2m$. Consider the vector space $V$ spanned by the set $P$ of ordered partitions of $[2m]$ into $m$ blocks of size two. The symmetric group $S_{2m}$ acts naturally on $V$. Now let $T$ be the set of ordered partitions of $[2m]$ with $m-2$ blocks of size two and one block of size 4, and for $t\in T$, let $\alpha(t)$ be the sum in $V$ of all the elements of $P$ from which $t$ can be obtained by merging two adjacent blocks. Then the quotient of $V$ by the $S_n$-module spanned by the $\alpha(t)$ is the desired $S_{2m}$-module, with dimension $A_{2m}$.
For example, with $n=4$, there are 6 ordered partitions:
There is only one element $t\in T$, and $\alpha(t)$ is the sum of all six ordered partitions in $P$, so the quotient module has dimension $5=A_4$.
Instead of ordered partitions of $[2m]$ we could have used any $2m$-element set, and it is clear that the construction is functorial.