Number of trees

Description

These functions return the number of rooted or unrooted binary trees consistent with a given pattern of splits.

Usage

NRooted(tips)

NUnrooted(tips)

NRooted64(tips)

NUnrooted64(tips)

LnUnrooted(tips)

LnUnrooted.int(tips)

Log2Unrooted(tips)

Log2Unrooted.int(tips)

LnRooted(tips)

LnRooted.int(tips)

Log2Rooted(tips)

Log2Rooted.int(tips)

LnUnrootedSplits(...)

Log2UnrootedSplits(...)

NUnrootedSplits(...)

LnUnrootedMult(...)

Log2UnrootedMult(...)

NUnrootedMult(...)

Arguments

Details

Functions starting N return the number of rooted or unrooted trees. Replace this initial N with Ln for the natural logarithm of this number; or Log2 for its base 2 logarithm.

Calculations follow Cavalli-Sforza and Edwards (1967) and Carter et al. (1990), Theorem 2.

Functions

• NUnrooted: Number of unrooted trees

• NRooted64: Exact number of rooted trees as 64-bit integer (13 < nTip < 19)

• NUnrooted64: Exact number of unrooted trees as 64-bit integer (14 < nTip < 20)

• LnUnrooted: Log Number of unrooted trees

• LnUnrooted.int: Log Number of unrooted trees (as integer)

• LnRooted: Log Number of rooted trees

• LnRooted.int: Log Number of rooted trees (as integer)

• NUnrootedSplits: Number of unrooted trees consistent with a bipartition split.

• NUnrootedMult: Number of unrooted trees consistent with a multi-partition split.

Author(s)

Martin R. Smith (martin.smith@durham.ac.uk)

References

Carter M, Hendy M, Penny D, Székely LA, Wormald NC (1990). “On the distribution of lengths of evolutionary trees.” SIAM Journal on Discrete Mathematics, 3(1), 38–47. doi: 10.1137/0403005.

Cavalli-Sforza LL, Edwards AWF (1967). “Phylogenetic analysis: models and estimation procedures.” Evolution, 21(3), 550–570. ISSN 00143820, doi: 10.1111/j.1558-5646.1967.tb03411.x.

See Also

Other tree information functions: CladisticInfo(), TreesMatchingTree()

Examples

NRooted(10)
NUnrooted(10)
LnRooted(10)
LnUnrooted(10)
Log2Unrooted(10)
# Number of trees consistent with a character whose states are
# 00000 11111 222
NUnrootedMult(c(5,5,3))

NUnrooted64(18)
LnUnrootedSplits(c(2,4))
LnUnrootedSplits(3, 3)
Log2UnrootedSplits(c(2,4))
Log2UnrootedSplits(3, 3)
NUnrootedSplits(c(2,4))
NUnrootedSplits(3, 3)