Programmer Humor

I was saying unipotent at first instead of involutory, which was actually the wrong jargon because of the context, but I've fixed that now. Yes, they're all real.

A glossary:

Involution

Surjective

Injective

Free magma

Free monoid

Map, although in this context I could probably have just said function. I go with map by default when thinking bidirectionally.

I think most people here will know combinatorics, the study of the different possible configurations of something. The number of n-length strings with two possible characters is 2^n^, as coders should all know, and the number of trees turns out to be Catalan numbers, many of which have prime factors other than 2. This is an injective map from n node trees to 2n character strings, so it's possible, but you'll (almost?) never get a perfect match, so by the pigeonhole principle it can't be surjective.

I'm wondering now if Catalan numbers are O(n!). The equation has a lot of n! but it also has a certain smell like it might depend on big or little o.

Edit: D'oh, they must grow no faster than 2^2n^; I just wrote that. So, exponential.