Mathematica Stack Exchange is a question and answer site for users of Mathematica. 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 would like to know how to generate all rooted trees on $n$ vertices using Mathematica?

More precisely, I am interested in generating algebraic expressions equivalent to rooted trees and constructed as follows:

  • Let $U$ be some function of one variable $x$.
  • All expressions are obtained using exclusively composition by $U$ or multiplication by $U$
  • Multiplication by $U$ correspond to adding a child to a vertex.
  • Composition by $U$ corresponds to adding a parent.

Clarifying examples:

  • $U\big[U[x] U[x]\big]$ is equivalent to the rooted tree:

    enter image description here

  • While $U[x]U\big[U[x] U[x]\big]$ is equivalent to the rooted tree


  • And finally $U\Big[U[x]\,U\big[U[x] U[x]\big]\Big]$ is equivalent to the rooted tree


Could you please help me generate all rooted trees on $n$ vertices, i.e. algebraic expressions as above with $U$ appearing $n$ times?

share|improve this question

This might not be the most efficient way, but seems to do it:

expr[1] = {u[x]};
expr[n_Integer?Positive] := expr[n] =
        Outer[Times, expr[n - k], expr[k]], 
        {k, 1, n - 1}
     Map[u, expr[n - 1]]

For example:


(* {u[x]^3, u[x] u[u[x]], u[u[x]^2], u[u[u[x]]]} *)


   {u[x]^4, u[x]^2 u[u[x]], u[x] u[u[x]^2], u[x] u[u[u[x]]], 
    u[u[x]]^2, u[u[x]^3], u[u[x] u[u[x]]], u[u[u[x]^2]], u[u[u[u[x]]]]}
share|improve this answer
Thanks ! That does the job and generates all rooted trees, this is excellent. – ThQ May 14 '14 at 13:06
@ThQ Was glad to help. Next time you ask a question, I suggest including some (however flawed or incomplete) attempts / code you tried. Questions showing no effort from the asker's side are generally frowned upon here (although I understand that for a beginner user of Mathematica, question such as this can be hard to even start with). – Leonid Shifrin May 14 '14 at 13:14

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.