## Want to keep learning?

This content is taken from the UNSW Sydney's online course, Maths for Humans: Inverse Relations and Power Laws. Join the course to learn more.
4.11

Arthur Cayley

# 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 $$\normalsize{n}$$ 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 $$\normalsize{n}$$ labeled vertices is $$\normalsize{n^{n-2}}$$.

This means that we have $$\normalsize n$$ different vertices, each with a different label, or colour. We are interested in counting how many trees we can create using these $$\normalsize n$$ 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 $$\normalsize{n}$$. It grows much faster than any polynomial sequence. But it is also growing faster than a pure exponential function like $$\normalsize{2^n}$$.