Cayley's tree formula (after Andre Joyal)

Item: Cayley's tree formula (after Andre Joyal)
Rating: 5
Author: PostSingularity Institute

by Richard E Borcherds

Formal & Physical Sciences Mathematics PBMathematics PBVCombinatorics and graph theory

🎙 Richard E Borcherds 👥 82K 📅 November 14, 2021 ⏱ 11 min 👁 8K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

Cayley's formulalabeled treescombinatorial proofbijectionJoyal

Summary

The lecture begins by enumerating unlabeled trees for small n, noting the difficulty of counting them directly. The speaker introduces the idea of weighting trees by the inverse of their symmetry group size, which simplifies the count and reveals a pattern: the weighted count for n vertices is n^(n-2)/n!. This leads to the equivalent problem of counting labeled trees, which should be n^(n-2). The main proof presented is Andre Joyal’s bijective proof, which establishes a bijection between labeled trees with two distinguished vertices and functions from an n-element set to itself. The construction involves representing a function as a collection of cycles with trees attached, and then transforming this into a labeled tree by adding edges and choosing a starting and ending vertex. The proof is elegant and visual, requiring no lengthy calculations. The lecture also notes that the formula was first proved by Carl Wilhelm Borchardt, not Cayley, and that Cayley acknowledged this in his paper.

157 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and insightful explanation of Cayley’s formula, emphasizing the power of bijective proofs in combinatorics. The argumentation is rigorous and well-structured, starting with small examples to motivate the formula, then introducing the concept of weighted trees to simplify counting, and finally presenting Joyal’s bijection. The proof is constructive and visual, making it accessible while maintaining mathematical precision. The historical note about Borchardt adds depth and corrects a common misconception.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with a solid mathematical foundation. The speaker cites Joyal’s work and mentions the original paper by Cayley, providing historical context. The title accurately describes the content, which is a focused lecture on Cayley’s formula and Joyal’s proof. No external sources are cited in the description, but the content itself is based on well-established mathematical results.

148 words

Title / Content Match

The title accurately reflects the content, which is a lecture on Cayley's tree formula and Joyal's combinatorial proof.

Quality & Reliability

9/10

The lecture is given by a renowned mathematician, Richard Borcherds, and presents a rigorous combinatorial proof of Cayley's formula. The content is mathematically sound, with clear explanations and historical context. The proof is well-known and accepted in the mathematical community.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Contribution & Novelties

The lecture provides a clear exposition of Joyal’s bijective proof of Cayley’s formula, which is a classic example of a combinatorial proof. The approach of weighting trees by symmetry is a valuable technique in enumeration. The lecture also corrects the historical attribution, noting that Borchardt proved the formula first.

Pour aller plus loin :

Cayley’s formula — Wikipedia article providing background and alternative proofs.
Prüfer sequence — Another bijective proof of Cayley’s formula.
Combinatorial species — A framework that generalizes such bijective proofs.

83 words

Radar Profile

The radar profile shows high scores in quality and reliability, with slightly lower but still strong scores in quantity and technical level. This indicates a lecture that is both informative and rigorous, suitable for an audience with some mathematical background.

Reliability 9/10