Feeds:
Posts

## MaBloWriMo begins with a puzzle

It’s time to try writing a blog post every day of November again. This time I’ll really try to make the posts shorter.

This one will consist entirely of a puzzle. Consider the formal power series

$\displaystyle f(z) = \sum_{n \ge 0} n! z^n = 1 + z + 2z^2 + 6z^3 + 24 z^4 + \dots$

giving the ordinary generating function of the factorials. This power series has zero radius of convergence, but it still makes sense formally. Its logarithm

$\displaystyle \log f(z) = \sum_{n \ge 1} \frac{(1 - f(z))^n}{n} = z + \frac{3z^2}{2} + \frac{13 z^3}{3} + \frac{71 z^4}{4} + \dots$

is another formal power series of the form $\displaystyle \sum_{n \ge 1} \frac{a_n z^n}{n}$, where the $a_n$ turn out to be positive integers.

Puzzle: What do the $a_n$ count?

No cheating using the OEIS! That’s no fun anyway.

### 11 Responses

1. […] Two days ago, as a puzzle, I asked what the generating function […]

2. [SPOILER SPACE….]

By the formula $All = exp(Connected)$ (http://mathoverflow.net/a/215053/1015), $a_n$ counts the number of connected (a.k.a. indecomposable) permutations on $n$ elements, i.e., permutations which do not fix any interval $[1..p]$ for $p < n$. Perhaps more surprisingly, $a_n$ also counts the number of rooted oriented hypermaps with $n$ edges. (A rooted oriented hypermap is a hypergraph embedded in a compact oriented surface without boundary, equipped with a choice of edge. A bijection between indecomposable permutations and rooted oriented hypermaps was given by Patrice Ossona de Mendez and Pierre Rosenstiehl. It restricts to a bijection between indecomposable involutions and rooted oriented maps, which is nicely described in their short paper, "Encoding pointed maps by double occurrence words".)

• At the very least you’re off by one here (which confuses me about this interpretation; that shouldn’t be happening); surely this interpretation gives $a_n \le n!$ and this bound doesn’t hold…

• Of course you’re right, I should have said indecomposable permutations on $n+1$ elements. From your hint in the next post, though, I suspect you were going for the second answer, rooted oriented hypermaps on $n$ edges, viewed as pairs of permutations acting transitively on a set. Is that right?

3. […] « MaBloWriMo begins with a puzzle […]

4. […] I noticed both Zachary Abel and Qiaochu Yuan plan to write a blog post every day this month (hooray!). I haven’t written on here as much as I […]

5. I’m making a mistake somewhere below but can’t figure out where I’m going wrong.

Since exponential generating functions (EGFs) are better behaved than ordinary generating functions (OGFs), let’s pretend that $f(z)$ is an EGF counting pairs of permutations on a set of $n$ elements. That is equivalent to being given two sets $A$ and $B$ of $n$ elements each and counting pairs of bijections $\pi: A \rightarrow B$ and $\rho: B \rightarrow A$. This in turn is equivalent to counting the number of bipartite digraphs where $A$ and $B$ are the partite sets and every vertex has exactly one incoming edge and exactly one outgoing edge. Such digraphs are unordered sets of connected bipartite digraphs where $A$ and $B$ are the partite sets and every vertex has exactly one incoming edge and exactly one outgoing edge. So, $\log f(z):= \sum_{n\ge 1} b_n z^n/n!$, regarded as an EGF, counts the latter. The coefficients $b_n$ are related to $a_n$ via $b_n = a_n(n-1)!$. So, $a_n$ ought to count the number of quotient set by obtained by identifying the connected bipartite digraphs above whenever they are related by a cyclic permutation of the elements of $A$.

This unfortunately doesn’t agree with the first few instances $a_n$ given in the post.

• This is a good start, but you need to be careful to make and not make the right identifications near the end.

6. Minor detail: I think you’re missing a $(-1)^n$ in the sum. And there’s an extra left parentheses.

• Whoops, thanks for the catch.