Cayley's formula

Cayley's formula

2^{2-2}=1 tree with 2 vertices,3^{3-2}=3 trees with 3 vertices and 4^{4-2}=16trees with 4 vertices.

In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that if "n" is an integer bigger than 1, the number of trees on "n" labeled vertices is

:n^{n-2}.,

It is a particular case of Kirchhoff's theorem.

Proof of the formula

Let T_{n} be the set of trees possible on the vertex set {v_{1}, v_{2},ldots, v_{n}}. We seek to show that

:|T_{n}| = n^{n-2}.

We begin by proving a lemma:

Claim: Let d_{1}, d_{2}, ldots, d_{n} be positive integers such that sum_{i=1}^{n}d_{i} = 2n-2 . Let mathcal{A} be the set of trees on the vertex set {v_{1}, v_{2},ldots, v_{n}} such that the degree of v_{i} (denoted mbox{d}(v_{i})) is d_{i} for i = 1, 2,ldots, n. Then

:|mathcal{A}| = frac{(n-2)!}{(d_{1}-1)!(d_{2}-1)!cdots(d_{n}-1)!}.

Proof:We go by induction on n. For n=1 and n=2 the proposition holds trivially and is easy to verify. We move to the inductive step. Assume n>2 and that the claim holds for degree sequences on n-1 vertices. Since the d_{i} are all positive but their sum is less than 2n, exists kin{1,2,ldots,n} such that d_{k} = 1. Assume without loss of generality that d_{n} = 1.

For i = 1, 2, ldots, n-1 let mathcal{B}_{i} be the set of trees on the vertex set {v_{1}, v_{2}, ldots v_{n-1} } such that:

:d(v_{j}) = egin{cases} mbox{d}_{j}, & mbox{if }j eq i \ mbox{d}_{j}-1, & mbox{if }j=i end{cases}

where d(v) is the degree of v.

Trees in mathcal{B}_{i} correspond to trees in mathcal{A} with the edge {v_{i}, v_{n}}, and if mbox{d}_{i} = 1, then mathcal{B}_{i} = emptyset.

Since v_{n} must have been connected to some node in every tree in mathcal{A}, we have that

:|mathcal{A}| = sum_{i=1}^{n-1}|mathcal{B}_{i}|.

Further, for a given i we can apply either the inductive assumption (if mbox{d}_{i} > 1) or our previous note (if mbox{d}_{i} = 1, then mathcal{B}_{i} = emptyset) to find |mathcal{B}_{i}|:

:|mathcal{B}_{i}| = egin{cases} 0, & mbox{if }d_{i}=1 \ frac{(n-3)!}{(d_{1}-1)!cdots(d_{i}-2)!cdots(d_{n-1}-1)!}, & mbox{otherwise} end{cases} for i=1,2,ldots,n-1

Observing that

:frac{(n-3)!}{(d_{1}-1)!cdots(d_{i}-2)!cdots(d_{n-1}-1)!} = frac{(n-3)!(d_{i}-1)}{(d_{1}-1)!cdots(d_{n-1}-1)!}
it becomes clear that, in either case, |mathcal{B}_{i}| = frac{(n-3)!(d_{i}-1)}{(d_{1}-1)!cdots(d_{n-1}-1)!}.

So we have

::|mathcal{A}| = sum_{i=1}^{n-1}|mathcal{B}_{i}|

:=sum_{i=1}^{n-1}frac{(n-3)!(d_{i}-1)}{(d_{1}-1)!cdots(d_{n-1}-1)!}

:=frac{(n-3)!}{(d_{1}-1)!cdots(d_{n-1}-1)!}sum_{i=1}^{n-1}(d_{i}-1).

And since d_{n} = 1 and sum_{i=1}^{n}d_{i} = 2n-2, we have:

:|mathcal{A}| = frac{(n-3)!}{(d_{1}-1)!cdots(d_{n}-1)!}(n-2) = frac{(n-2)!}{(d_{1}-1)!cdots(d_{n}-1)!}

which proves the lemma.

We have shown that given a particular list of positive integers d_{1}, d_{2}, ldots, d_{n} such that the sum of these integers is 2n-2, we can find the number of trees with labeled vertices of these degrees. Since every tree on n vertices has n-1 edges, the sum of the degrees of the vertices in an n-vertex tree is always 2n-2. To count the total number of trees on n vertices, then, we simply sum over possible degree lists. Thus, we have:

:|T_{n}| = sum_{d_{1}+d_{2}+cdots+d_{n} = 2n-2} frac{(n-2)!}{(d_{1}-1)!cdots(d_{n}-1)!}.

If we reindex with k_{i}=d_{i}-1 for i=1,2,ldots,n, we have:

:|T_{n}| = sum_{k_{1}+k_{2}+cdots+k_{n} = n-2} frac{(n-2)!}{k_{1}!cdots k_{n}!}.

Finally, we can apply the multinomial theorem to find:

:|T_{n}| = n^{n-2}

as expected. Box

Note

Prüfer sequences yield one of the many alternate proofs of Cayley's formula.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Fórmula de Cayley — Lista completa de todos los árboles con 2,3 y 4 vértices etiquetados: 22 − 2 = 1 árboles con 2 vértices, 33 − 2 = 3 árboles con 3 vértices y 44 − 2 = 16 árboles con 4 vértices. En teoría de grafos, la fórmula de Cayley es un resultado lla …   Wikipedia Español

  • Cayley–Dickson construction — In mathematics, the Cayley–Dickson construction produces a sequence of algebras over the field of real numbers, each with twice the dimension of the previous one. The algebras produced by this process are known as Cayley–Dickson algebras; since… …   Wikipedia

  • Cayley transform — In mathematics, the Cayley transform, named after Arthur Cayley, has a cluster of related meanings. As originally described by Harvtxt|Cayley|1846, the Cayley transform is a mapping between skew symmetric matrices and special orthogonal matrices …   Wikipedia

  • Cayley's Ω process — In mathematics, Cayley s Ω process, introduced by Arthur Cayley (1846), is a relatively invariant differential operator on the general linear group, that is used to construct invariants of a group action. As a partial differential operator… …   Wikipedia

  • Fórmula de Herón — Triángulo de lados a, b, c. En geometría, la fórmula de Herón, descubierta por Herón de Alejandría, relaciona el área de un triángulo en términos de las longitudes de sus lados a, b y c …   Wikipedia Español

  • Arthur Cayley — Infobox Scientist name = Arthur Cayley |242px image width = 242px caption = Portrait in London by Barraud Jerrard birth date = birth date|1821|8|16|mf=y birth place = Richmond, Surrey, UK residence = England nationality = British death date =… …   Wikipedia

  • Arthur Cayley — Arthur Cayley. Arthur Cayley (Richmond, Reino Unido, 16 de agosto de 1821 Cambridge, 26 de enero de 1895) fue un matemático británico. Es uno de los fundadores de la escuela británica moderna de matemáticas puras. Además de su predilección por… …   Wikipedia Español

  • Construcción de Cayley-Dickson — En matemáticas, la construcción de Cayley Dickson produce una secuencia de álgebras sobre el cuerpo de los números reales, cada una con dimensión doble que la anterior. Las álgebras producidas por este proceso son conocidas como álgebras de… …   Wikipedia Español

  • Genus–degree formula — In classical algebraic geometry, the genus–degree formula relates the degree d of a non singular plane curve with its arithmetic genus g via the formula: A singularity of order r decreases the genus by .[1] Proofs The proof follows immediately… …   Wikipedia

  • Rotation matrix — In linear algebra, a rotation matrix is a matrix that is used to perform a rotation in Euclidean space. For example the matrix rotates points in the xy Cartesian plane counterclockwise through an angle θ about the origin of the Cartesian… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”