PhylogeneticTrees

The rooted binary trees on $n$ labeled leaves with unlabeled internal nodes, as a lazy indexed family.

PhylogeneticTrees(n)every rooted binary tree with leaves labeled $1, …, n$ and unlabeled internal nodes.

Typed signatures

Type	Package	Applies
(integer<0..>) -> indexed_collection<phylogenetic_tree>	combinatorics	always

Domain: Collections

Details

• A lazy indexed collection; the count is $(2n-3)!! = A001147(n-2)$ — $PhylogeneticTrees(5)$ has $105$ elements. See Factorial2.
• Built by successive insertion: start from the cherry $\{1,2\}$, then for $k = 3, …, n$ attach leaf $k$ at one of $2k-3$ places — above the current root, or subdividing one of the tree's edges.
• Each element is the digit sequence $(d_3, …, d_n)$ with $d_k \in [0, 2k-3)$ recording that insertion choice at each step; $At$ unranks it as a mixed-radix number in those insertion-step radices.

Enumeration

Examples

1 more kept as data, checked against the oracles

Basic #

$Count(PhylogeneticTrees(5)) = 105 = (2 \cdot 5 - 3)!!$, A001147

live ↗

In$\mathrm{Count}(\mathrm{PhylogeneticTrees}(5))$Out$105$

About

Examples	2

See also: Factorial2, Count, At