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.

Definition

Epsil, as the implementation runs it.

count(_n)

Fold(Function(pc * (2pk - 3), pc, pk), 1, Range(3, _n, 1))

unrank(_n, _r)

Map(
     Function((_r - _r % Fold(
                               Function(pw * (2pi + 1), pw, pi),
                               1,
                               Range(pj + 1, Max(_n - 2, 0), 1),
                             )) / Fold(
                                       Function(pw * (2pi + 1), pw, pi),
                                       1,
                                       Range(pj + 1, Max(_n - 2, 0), 1),
                                     ) % (2pj + 1), pj),
     Range(1, Max(_n - 2, 0), 1),
   )

rank(_n, _x)

Fold(Function(pr * (2pd + 1) + _x[pd], pr, pd), 0, Range(1, Max(_n - 2, 0), 1))

valid(_n, _x)

Fold(
      Function(ok_pv && 0 <= _x[pv] && _x[pv] < 2pv + 1, ok_pv, pv),
      True,
      Range(1, Length(_x), 1),
    ) if Length(_x) == Max(_n - 2, 0) else False

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