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
giving the ordinary generating function of the factorials. This power series has zero radius of convergence, but it still makes sense formally. Its logarithm
is another formal power series of the form 
Puzzle: What do the
No cheating using the OEIS! That’s no fun anyway.
Annoying Precision 
[…] Two days ago, as a puzzle, I asked what the generating function […]
[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
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?
Yes, that’s closer to what I have in mind.
[…] « MaBloWriMo begins with a puzzle […]
[…] 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 […]
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
is an EGF counting pairs of permutations on a set of 
elements. That is equivalent to being given two sets 
and 
of 
elements each and counting pairs of bijections 
and 
. This in turn is equivalent to counting the number of bipartite digraphs where 
and 
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 
and 
are the partite sets and every vertex has exactly one incoming edge and exactly one outgoing edge. So, 
, regarded as an EGF, counts the latter. The coefficients 
are related to 
via $b_n = a_n(n-1)!$. So, 
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 
.
This unfortunately doesn’t agree with the first few instances
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.
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.