## MaBloWriMo begins with a puzzle

November 1, 2015 by Qiaochu Yuan

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 , where the turn out to be positive integers.

**Puzzle:** What do the count?

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

### Like this:

Like Loading...

*Related*

on November 3, 2015 at 10:24 pm |The answer to the puzzle | Annoying Precision[…] Two days ago, as a puzzle, I asked what the generating function […]

on November 3, 2015 at 12:05 am |Noam Zeilberger[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".)

on November 3, 2015 at 4:43 pm |Qiaochu YuanAt 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…

on November 3, 2015 at 9:59 pm |Noam ZeilbergerOf 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?

on November 3, 2015 at 10:28 pm |Qiaochu YuanYes, that’s closer to what I have in mind.

on November 2, 2015 at 10:23 pm |MaBloWriMo continues with a hint | Annoying Precision[…] « MaBloWriMo begins with a puzzle […]

on November 2, 2015 at 7:59 pm |MaBloWriMo: The Lucas-Lehmer test | The Math Less Traveled[…] 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 […]

on November 1, 2015 at 10:16 pm |ZahlenI’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.

on November 1, 2015 at 10:30 pm |Qiaochu YuanThis is a good start, but you need to be careful to make and not make the right identifications near the end.

on November 1, 2015 at 5:58 pm |Caleb StanfordMinor detail: I think you’re missing a $(-1)^n$ in the sum. And there’s an extra left parentheses.

on November 1, 2015 at 6:33 pm |Qiaochu YuanWhoops, thanks for the catch.