É. Czabarka, P.L. Erdős, V. Johnson, V. Moulton: Generating functions for multi-labeled trees

and in

Virginia Johnson<'s Ph.D. thesis, (Aug. 2012)

Recently it has become apparent that it can also be useful to employ a slightly more general type of tree when trying to understand, for example, gene evolution. In particular, due to processes such as gene (or genome) duplication or lateral gene transfer, trees can often arise in which more than one leaf is labeled by the same element of the label set. We call such trees

- Go to http://www.sagenb.org/
- Create an account if you do not already have one; open your account.
- Click on New Worksheet. Name the program if you wish.
- Copy the code for binary trees or the code for non-binary trees into the box
- Hit evaluate
- In the next box type in T(n,k) for binary trees or G(n,k) for non-binary trees (n is for number of leaves and k is for number of labels).
- Hit evaluate again. See the next section for description of the output you get.

For example for the call T(10,5) the program returns:

Number of leaves,number of labels

10 5

Rooted MUL Binary Trees

[0, 5, 15, 75, 495, 3600, 28275, 232500, 1979385, 17287050, 154041450]

Rooted MUL Binary Trees using all k labels

[0, 0, 0, 0, 0, 105, 2625, 42075, 554820, 6578550, 73169250]

Marked MUL Binary Trees

[0, 5, 25, 110, 600, 4200, 31730, 255750, 2144400, 18530875, 163771800]

Marked MUL Binary Trees using all k labels

[0, 0, 0, 0, 0, 120, 2925, 46065, 599670, 7041285, 77720100]

Unrooted MUL Binary Trees

[0, 5, 15, 35, 120, 600, 3530, 23250, 165510, 1243825, 9733950]

Unrooted MUL Binary Trees using all k labels

[0, 0, 0, 0, 0, 15, 300, 3990, 44850, 462735, 4550955]

This output tells you that for example there are 28275 rooted leaf-multi-labeled binary trees on 6 leaves that use at most 5 labels and 2625 of these use all 5 labels, and there are 9733950 unrooted leaf-multi-labeled binary trees on 10 leaves that use at most 5 labels.

The function G(n,k) (where n is the number of leaves and k is the number of labels) returns two lists of counts, each containing the number of trees using at most k labels on 0,1,2,...,n leaves. The first list counts rooted non-binary leaf-multi-labeled trees, labeled with at most k labels. The second list is for unrooted leaf-multi-labeled non-binary trees, labeled with at most k labels.

For example for the call G(9, 5) the program returns:

Rooted Non-binary Multi-leaf-labeled Trees

[0, 5, 15, 110, 965, 9376, 97775, 1068450, 12081605, 140160650]

Unrooted Non-binary Multi-leaf-labeled Trees

[0, 5, 65, 335, 2840, 27151, 279465, 3028655, 34035550, 393044405]

This output tells you that for example there are 97,775 rooted leaf-multi-labeled non-binary trees on 6 leaves that use at most 5 labels and there are 34,035,550 unrooted leaf-multi-labeled non-binary trees on 8 leaves that use at most 5 labels.