Ask Your Question

Combinatorial Species of Phylogenetic Trees

asked 2018-03-31 21:49:26 +0200

Frank Zenter gravatar image

updated 2018-03-31 22:26:26 +0200

I would like to study the combinatorial class ${\cal H}$ of labelled phylogenetic trees, defined as rooted trees, whose internal nodes are unlabelled and are constrained to have outdegree $\geq 2$, while their leaves have labels attached to them.

According to Flajolet, Sedgewick: Analytic Combinatorics, p. 128, this class satisfies the recursive specification $${\cal H}={\cal Z}+\mbox{Set}_{\geq 2}({\cal H})$$ I defined their species $H$ by the code







The number of labelled structures is given by the integer sequence.

In particular I tried to calculate (for a small cardinal number)

  1. a list of such structures.
  2. a generating series of this structures.
  3. the number of such structures.
  4. isomorphism-types of such structures.
  5. a generating series of the isomorphism-types of such structures.
  6. a random such structure.
  7. automorphism-groups of of such structures.

using the following code:

1. H.structures([1,2,3]).list()
2. g = H.generating_series()
3. g.counts(3)
4. H.isotypes([1,2,3])
5. g=H.isotype_generating_series()
6. r=H.structures([1,2,3]).random_element()
7. r.automorphism_group()

Only 2. seems to work.

If my code ist correct, I wonder if some of these (i.e. composition species) are not implemented and when (whether) they will be.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2018-04-01 02:33:41 +0200

tmonteil gravatar image

updated 2018-04-01 02:35:06 +0200

Note that the species module is mostly a raw translation of the old code from mupad-combinat. There are plans to update it, in particular, Jean-Baptiste Priez started to work on it, but left academia since then. Would you be interested in working on it ?

That said, why not defining H in a simpler way as follows:

sage: Z=species.SingletonSpecies()
sage: H=CombinatorialSpecies()
sage: H.define(Z+species.SetSpecies(min=2)(H))

Then, you can do, at least:

sage: g = H.generating_series()
sage: oeis([g.count(i) for i in range(10)])
0: A000311: Schroeder's fourth problem; also number of phylogenetic trees with n nodes; also number of total partitions of n.
edit flag offensive delete link more


...unfortunately i have only one up for (the answer and) the oeis...

dan_fulea gravatar imagedan_fulea ( 2018-04-02 17:09:26 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2018-03-31 21:49:26 +0200

Seen: 336 times

Last updated: Apr 01 '18