Interview Question 5

An increasing tree is a rooted labelled tree whose labels increase along paths away from the root. For simplicity, if the tree has \(n\) vertices we will take the root to be labelled \(1\) and the other vertices to be labelled by \(2, \ldots, n\). An example is shown below.

Note that when a node has more than one child, the order in which the children are represented is irrelevant, so that, for example, the following two trees are equivalent.

Can you draw all the increasing trees with \(4\) vertices?
How many increasing trees on \(n\) vertices are there?
Suppose now that \(n\) is even. How many of these can be split by removing a single edge into a tree labelled only by odd numbers and a tree labelled only by even numbers?
Suppose now that we want to generate an increasing tree on \(n\) vertices picked uniformly at random, i.e. pick each of the possible trees with equal probability. Can you give an algorithm to do this?
When a random tree is picked as in the previous part, what is the average number of neighbours of the root?

This question was used in Maths & CS interviews at Lady Margaret Hall in December 2021. The question is due to Christina Goldschmidt.

def main(): num = int(input("Number of vertices: ")) print(trees(num)) def trees(n): list = [0 for i in range(n)] list[0] = 1 for i in range(2, n 1): for j in range(i-1, 0, -1): list[j] = list[j-1] + (j + 1)*list[j] return list if __name__ == "__main__": main()

def main(): num = int(input("Number of vertices: ")) print(sum(trees(num))) def trees(n): list = [0 for i in range(n)] list[0] = 1 for i in range(2, n 1): for j in range(i-1, 0, -1): list[j] = list[j-1] + (j + 1)*list[j] return list if __name__ == "__main__": main()

4 responses

I’m a bit stuck on Q2, could you publish the discussion please.

A – October 7th, 2023
@A, I see your question hasn’t been answered so I’ll give it a shot.

Consider the number of increasing trees on n vertices to be f(n).

When we want to find f(n + 1), we simply take our increasing trees from f(n) and add an extra vertex of value n + 1 to it.

Recall that for a vertex to be the child of another vertex (ie. be connected by an edge but lower on the tree) the value of the child vertex must be larger than the value of the parent.

So when we add the vertex n + 1 to the increasing trees from f(n), we know that n + 1 is the vertex with the highest value, and thus can be the child of any of the n vertices in each tree of f(n). Hence, f(n + 1) = n * f(n), since when we add our n + 1-th vertex to the tree, we can add it in any of the n positions.

f(2) = 1, so the formula becomes f(n) = (n-1)!.

L – November 13th, 2023

for question 2, it took me a while to code, but I got the following recursive algorithm:
def main():
    num = int(input("Number of vertices: "))
    print(trees(num))

def trees(n):
    list = [0 for i in range(n)]
    list[0] = 1
    for i in range(2, n 1):
        for j in range(i-1, 0, -1):
            list[j] = list[j-1] +  (j + 1)*list[j]
    return list
    
if __name__ == "__main__":
    main()
Nicolas – November 13th, 2023

Correction for the code’s output:

Nicolas – November 13th, 2023

Respond to this

4 responses