ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 02 Apr 2018 10:09:26 -0500Combinatorial Species of Phylogenetic Treeshttp://ask.sagemath.org/question/41852/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](https://en.wikipedia.org/wiki/Combinatorial_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](http://oeis.org/A000311).
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](http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html#section-generic-species) 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.Sat, 31 Mar 2018 14:49:26 -0500http://ask.sagemath.org/question/41852/combinatorial-species-of-phylogenetic-trees/Answer by tmonteil for <p>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. </p>
<p>According to Flajolet, Sedgewick:
<em>Analytic Combinatorics</em>, p. 128, this class satisfies the recursive specification
$${\cal H}={\cal Z}+\mbox{Set}_{\geq 2}({\cal H})$$
I defined their <a href="https://en.wikipedia.org/wiki/Combinatorial_species">species</a> $H$ by the code</p>
<pre><code>Z=species.SingletonSpecies()
E2=species.SetSpecies(min=2)
G=CombinatorialSpecies()
H=CombinatorialSpecies()
G.define(E2(Z+G))
H=Z+G
</code></pre>
<p>The number of labelled structures is given by the <a href="http://oeis.org/A000311">integer sequence</a>. </p>
<p>In particular I tried to calculate (for a small cardinal number)</p>
<ol>
<li>a list of such structures.</li>
<li>a generating series of this structures.</li>
<li>the number of such structures.</li>
<li>isomorphism-types of such structures.</li>
<li>a generating series of the isomorphism-types of such structures.</li>
<li>a random such structure.</li>
<li>automorphism-groups of of such structures.</li>
</ol>
<p>using the <a href="http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/tutorial.html#section-generic-species">following</a> code:</p>
<pre><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()
</code></pre>
<p>Only 2. seems to work.</p>
<p>If my code ist correct, I wonder if some of these (i.e. composition species)
are not implemented and when (whether) they will be.</p>
http://ask.sagemath.org/question/41852/combinatorial-species-of-phylogenetic-trees/?answer=41853#post-id-41853Note 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.Sat, 31 Mar 2018 19:33:41 -0500http://ask.sagemath.org/question/41852/combinatorial-species-of-phylogenetic-trees/?answer=41853#post-id-41853Comment by dan_fulea for <p>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 ?</p>
<p>That said, why not defining <code>H</code> in a simpler way as follows:</p>
<pre><code>sage: Z=species.SingletonSpecies()
sage: H=CombinatorialSpecies()
sage: H.define(Z+species.SetSpecies(min=2)(H))
</code></pre>
<p>Then, you can do, at least:</p>
<pre><code>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.
</code></pre>
http://ask.sagemath.org/question/41852/combinatorial-species-of-phylogenetic-trees/?comment=41866#post-id-41866...unfortunately i have only one up for (the answer and) the `oeis`...Mon, 02 Apr 2018 10:09:26 -0500http://ask.sagemath.org/question/41852/combinatorial-species-of-phylogenetic-trees/?comment=41866#post-id-41866