Unrooted binary tree: Difference between revisions

Revision as of 20:00, 16 June 2017

Revision as of 11:55, 26 June 2017

Line 28:

==Enumeration==

Because of their applications in hierarchical clustering, the most natural [[graph enumeration]] problem on unrooted binary trees is to count the number of trees with ''n'' labeled leaves and unlabeled internal nodes. An unrooted binary tree on ''n'' labeled leaves can be formed by connecting the ''n''th leaf to a new node in the middle of any of the edges of an unrooted binary tree on ''n'' − 1 labeled leaves. There are 2''n'' − 53 edges at which the ''n''th node can be attached; therefore, the number of trees on ''n'' leaves is larger than the number of trees on ''n'' − 1 leaves by a factor of 2''n'' − 5. Thus, the number of trees on ''n'' labeled leaves is the [[double factorial]]

:<math>(2n-5)!!=\frac{(2n-4)!}{(n-2)!2^{n-2}}.</math><ref>{{harvtxt|Balding|Bishop|Cannings|2007}}.</ref>

The numbers of trees on 2, 3, 4, 5, ... labeled leaves are