Problem 16

List all unlabeled trivalent phylogenetic trees with 15 leaves.

Solution

Here is a solution in Mathematica:

This makes a graph from a tree object:

makeTree[nodes_] :=
 Module[{counter = 0},
  traverse[h_[childs___]] := With[{id = counter}, {UndirectedEdge[id, ++counter],
       traverse[#]} & /@ {childs}];
  traverse[_] := Sequence[];
  Graph[#] &@Flatten[traverse[nodes]]]

This makes all ROOTED trees on 15 leaves:

AllRootedTrees[n_] := makeTree /@ TreeForm /@ Groupings[Table[a, n - 1], {2, Orderless}]

This deletes the duplicates:

AllTrees[n_] := DeleteDuplicates[AllRootedTrees[n], IsomorphicGraphQ[#1, #2] &]

The computation:

Trees15 = Timing[AllTrees[15]];

How long it took:

Trees15[[1]]

How many trees it found:

Length[Trees15[[2]]]