furnasI_inv {treebalance}

Calculation of rooted binary tree for tuple (rank, leaf number)

Description

This function calculates the unique tree T (in phylo format) for two given integer values r and n, with n denoting the number of leaves of T and r denoting the rank of T in the left-light rooted ordering of all rooted binary trees with n leaves. It is the inverse function of furnasI(). For details on how to calculate T (including algorithm) see "The generation of random, binary unordered trees" by G.W. Furnas (1984) or "Tree balance indices: a comprehensive survey" by Fischer et al. (2023).

furnasI_inv can be used e.g. to generate random rooted binary trees with a certain number of leaves. Also, the concept of assigning each rooted binary tree a unique tuple (rank, n) allows to store many trees with minimal storage use.

For details on the Furnas rank, see also Chapter 22 in "Tree balance indices: a comprehensive survey" (https://doi.org/10.1007/978-3-031-39800-1_22).

Usage

furnasI_inv(rank, n)

Arguments

rank

An integer denoting the rank of the sought tree among all rooted binary trees with n leaves.

n

An integer denoting the number of leaves of the sought tree.

Value

furnasI_inv returns the unique tree (in phylo format) for the given leaf number and rank.

Author(s)

Sophie Kersting

References

G. W. Furnas. The generation of random, binary unordered trees. Journal of Classification, 1984. doi: 10.1007/bf01890123. URL https://doi.org/10.1007/bf01890123.

Examples

furnasI_inv(rank=6,n=8)