# Trees and Cayley's formula

Of course the world is a complicated place, and there are many kinds of relationships that do not fit smoothly into the kinds we have discussed here. In fact once we learn about calculus, we can appreciate that there are other important relationships and functions that are less elementary but still very useful, such as exponential functions, circular functions, logarithmic functions and others too.

Let’s have a look at another more complicated relation which has an exponential aspect: the problem of determining how many trees can be formed from labelled nodes or vertices, solved by A. Cayley.

## How many labelled trees?

This mathematical example is quite important in computer science. In graph theory a *tree* is not a big plant, but rather a connected simple graph that has no cycles. That means that each edge joins different vertices, there is at most one edge between any two distinct vertices, and there is exactly one non-repeating path to go from any one vertex to any other.

In the diagram, you should be able to see four trees.

## Cayley’s formula

In mathematics, Arthur Cayley, a prolific 19th century English mathematician proved that for any positive integer n, the number of such trees on labeled vertices is .

This means that we have different vertices, each with a different label, or colour. We are interested in counting how many trees we can create using these coloured vertices.

In N. Sloane’s famous Online Encyclopedia of Integer Sequences, this is the sequence with number A000272.

Here are the first few entries:

1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793, 121439531096594251776, 5480386857784802185939

Here is a diagram that illustrates the sixteen possibilities for four vertices:
^{Cayley’s formula By Júlio Reis CC BY-SA 3.0, via Wikimedia Commons}

Cayley’s formula is no longer a polynomial relation, because both the base and the exponent involve . It grows much faster than any polynomial sequence. But it is also growing faster than a pure exponential function like .

© UNSW Australia 2015