11
$\begingroup$

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:

The fourth Euler zigzag number

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?

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Neil Strickland Mar 24 '14 at 13:04
  • $\begingroup$ I hadn't thought of that way of attacking the problem! $\endgroup$ – John Baez Mar 24 '14 at 13:43
  • $\begingroup$ 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. $\endgroup$ – Martin Rubey Mar 24 '14 at 19:56
  • $\begingroup$ 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.) $\endgroup$ – John Baez Mar 24 '14 at 23:20
  • $\begingroup$ 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. $\endgroup$ – Martin Rubey Mar 25 '14 at 8:39
8
$\begingroup$

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:

12 | 34, 13 | 24, 14 | 23, 34 | 12, 24 | 13, and 23 | 14.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.