Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

    tree1

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

    tree2

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

1 Answer 1

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

ClearAll[expr];
expr[1] = {u[x]};
expr[n_Integer?Positive] := expr[n] =
   Join[
     DeleteDuplicates@Flatten@Table[
        Outer[Times, expr[n - k], expr[k]], 
        {k, 1, n - 1}
     ],
     Map[u, expr[n - 1]]
   ];

For example:

expr[3]

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

expr[4]

(* 
   {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 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 at 13:14

Your Answer

 
discard

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.