NRooted {TreeTools}

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

tips

Integer specifying the number of leaves.

...

Integer vector, or series of integers, listing the number of leaves in each split.

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 ([e-mail])

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)