Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked familiar to me, but I could not place it. I was hoping someone here could throw me some search terms.

The construction is essentially a map $\phi$ from the set of rooted trees to the positive reals arising from some operations on the positive reals, $+$ and a collection of operations, one for each $n$, $\oplus_n$, taking $n$ arguments. Every one of these operations is symmetric and $+$ distributes over $\oplus_n$ for each $n$. There is a notion of composition of trees, which is just root-to-leaf adjoining of graphs. We require that whenever a tree, $T$, can be written as a composition of an $n$-corolla (ie. a rooted tree with $n+1$ vertices and $n$ leaves) and $n$ trees $A_1,..,A_n$, then


So that $\phi$ is completely determined by its values on the set of $n$-corollae for each $n$. I was wondering if $\phi$ had a name or a combinatorial interpretation. For me, it is an internal algebra in an algebra where the trees correspond simultaneously to search algorithms, guessing strategies, ways of building up information measures, and ways of associating variables.

The map is actually defined more generally for such trees, since these trees act via $\oplus_n$ on the positive reals as prescribed by the $A_\infty$-operad. This allows us to define a more general recursion relation than the one above, but all are equivalent, so I will not fill this post with those technicalities.


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.