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.

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.

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

thinkmost 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 to2ncharacter 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.You are awesome.

Lemmy is better for you being here. Thanks for the reading material!

You’re very welcome! How kind.