# Combinatorial Species of Phylogenetic Trees

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

Z=species.SingletonSpecies()

E2=species.SetSpecies(min=2)

G=CombinatorialSpecies()

H=CombinatorialSpecies()

G.define(E2(Z+G))

H=Z+G


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 close merge delete

Sort by ยป oldest newest most voted

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.

more

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

( 2018-04-02 10:09:26 -0500 )edit