The n-Category Café

In general, how many permutations can be achieved by polynomials this way? The answer is given by the Schröder numbers:

$$1, 2, 6, 22, 90, 394, 1806, 8558, \dots$$

The following article nicely explains what’s going on:

• Étienne Ghys, Intersecting curves (variation on an observation of Maxim Kontsevich), The American Mathematical Monthly 120 (March 2013), 232-242.

I’m afraid this paper is not free, but you can see a version in French for free here:

• Étienne Ghys, Quand beaucoup de courbes se rencontrent, Images des Maths, CNRS.

One of the lessons here is that when $n > 1$, the $n$th Schröder number is twice the number of planar rooted trees with $n$ leaves such that each node has either no children or at least two.

The number of planar rooted trees with $n$ leaves such that each node has either no children or at least two, is called the $n$th Schröder–Hipparchus number. These numbers go like this:

$$1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, \dots$$

The Schröder–Hipparchus numbers are similar in flavor to Catalan numbers. For example, you can see the $n$th one as the number of ways of chopping a regular $(n+1)$-gon into polygons by drawing nonintersecting diagonals between corners. Here are the 11 ways to chop up the pentagon:

If we allowed only triangles in our chopped-up polygons, we’d get the Catalan numbers.

The Schröder–Hipparchus numbers also count parenthesizations of a sequence of $n$ symbols, where each pair of parentheses surrounds two or more symbols or parenthesized groups, and without any parentheses surrounding the entire sequence. Here’s how you translate between these parenthesizations and trees:

If we allowed only parentheses that surround exactly two symbols or parenthesized groups, we’d get the Catalan numbers.

Let $b(n)$ be the $n$th Schröder–Hipparchus number, and let $H$ be the generating function for these numbers:

$$H(z) = \sum_{n = 1}^\infty b(n) z^n$$

Then $H$ obeys the following equation:

$$H(z) = z + H(z)^2 + H(z)^3 + \cdots$$

and we can use this to solve for $H(t)$, work out the radius of convergence of this power series, and thus work out the asymptotic growth rate of the Schröder–Hipparchus numbers. Again, all this should be familiar if you know and love your Catalan numbers.

The trees I just mentioned remind me of operads: could this be why Kontsevich got interested in this topic? Ghys does not seem to say.

Question: I believe there is an operad whose set of $n$-ary operations has cardinality equal to the $n$th Schröder–Hipparchus number. This should be the free operad generated by one operation of each arity $2, 3, 4, 5, \dots$. Is this correct? Where, if anywhere, does this operad show up in mathematics?

Schröder numbers show up in G. W. Zinbeil’s encyclopedic work on operads, but I don’t quite see an answer to my question there. Perhaps I’m not looking hard enough. (Zinbiel is of course the long-lost brother of Leibniz, who rocketed into superstar status when he emerged from a time-reversing wormhole on January 12, 1946.)

The appearance of Schröder numbers in Uchino’s work on the derived bracket construction for operads looks a bit more promising.

Finally, how did the Schröder–Hipparchus numbers get their name? For some reason the logician Ernst Schröder, famous for the Schröder–Bernstein theorem, published a paper on them in 1870. Why? I don’t know. Can you find out?

But the even more interesting historical puzzle is this: how did the famous ancient Greek mathematician and astronomer Hipparchus get interested in these numbers?

Nobody knows for sure, but we have a big clue. The philosopher Plutarch wrote a book called Table Talk, which records some of the conversations he had with witty and erudite friends. And according to a line in this book, Hipparchus showed that the number of “affirmative compound propositions” that can be made from ten “simple propositions” is 103049.

At least in modern history, nobody had a clue what Plutarch was talking about until 1994. Nobody knew what it meant to build “affirmative compound propositions” from “simple propositions”. Part of the problem is that while Hipparchus is famous for his work on astronomy, back around 100 BC, not much is known about his work on logic.

But in 1994 David Hough, a graduate student at George Washington University, cleared up the mystery. He observed that there are precisely 103049 ways of inserting parentheses into a list of ten things, obeying the rules I’ve described. In other words, as we now say, 103049 is the tenth Schröder–Hipparchus number!

For more, see:

• Richard Stanley, Hipparchus, Plutarch, Schröder and Hough.

Given all this, I’m willing to speculate that the ways of building “affirmative compound propositions” from “simple propositions” are precisely the ways I described above for parenthesizing a list of symbols.

In other words, they are just the operations in the operad I’m speculating about!

So if I’m not making a mistake, this operad deserves to be called the Hipparchus operad.

And I believe that this operad deserves to have some application, even if only a small one, to logic. After all, Schröder was a logician… and Hipparchus was studying logic when he ran into this operad.

Were they working on the same problem?