Cayley's tree formula (after Andre Joyal)

Cayley's tree formula (after Andre Joyal)

par Richard E Borcherds

Sciences formelles & physiques Mathématiques PBMathématiquesPBVAnalyse combinatoire et théorie des graphes
🎙 Richard E Borcherds 👥 82K 📅 14 novembre 2021 ⏱ 11 min 👁 8K 📄 vulgarisation 🧭 2026-08-17
Disponible en : Français (actuel) English

Mots-clés

formule de Cayleyarbres étiquetéspreuve combinatoirebijectionpermutations

Résumé

Cette vidéo présente une preuve combinatoire élégante de la formule de Cayley, qui énonce que le nombre d’arbres étiquetés à n sommets est n^(n-2). L’exposé commence par l’observation des premiers cas, montrant que le comptage naïf des arbres non étiquetés est difficile. L’auteur introduit alors l’idée de compter les arbres pondérés par l’inverse de l’ordre de leur groupe d’automorphismes, ce qui révèle une régularité : la somme pondérée pour n sommets vaut n^(n-2)/n!. Il explique ensuite que compter les arbres pondérés équivaut à compter les arbres étiquetés divisés par n!. La preuve principale, due à André Joyal (vers 1981), établit une bijection entre les arbres étiquetés avec deux sommets distingués et les fonctions d’un ensemble à n éléments vers lui-même. La construction est illustrée par un exemple : on part d’une permutation écrite en cycles, puis on ajoute des branches pour former un arbre, et on définit une fonction en orientant les arêtes vers les cycles. Cette bijection est explicite et se visualise par un schéma. Enfin, l’auteur mentionne que la formule a été démontrée pour la première fois par Carl Wilhelm Borchardt en 1860, et que Cayley l’a redécouverte et publiée, d’où l’attribution courante à Cayley.

197 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La valeur des informations est élevée : la vidéo fournit une preuve complète et rigoureuse de la formule de Cayley, un résultat fondamental en combinatoire. L’argumentation est solide, car elle repose sur une construction bijective explicite, démontrée étape par étape. L’auteur prend soin de justifier chaque étape, comme l’équivalence entre arbres pondérés et arbres étiquetés, et illustre la bijection par un exemple concret. La démarche pédagogique est efficace, passant du cas particulier à la généralisation.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est exemplaire : la preuve est correcte et bien expliquée. L’auteur cite les sources historiques, notamment l’article original de Cayley et la contribution de Borchardt, ce qui montre une attention à l’exactitude historique. Le titre est en adéquation avec le contenu, qui se concentre effectivement sur la preuve de Joyal. Aucune source externe n’est fournie dans la description, mais la vidéo est auto-suffisante pour la démonstration.

159 mots

Adéquation titre / contenu

Le titre est parfaitement adapté : il annonce la formule de Cayley et la preuve de Joyal, qui est effectivement le contenu principal.

Qualité & fiabilité

9/10

Exposé mathématique rigoureux par un expert reconnu, avec preuve combinatoire détaillée et mention de l'attribution historique correcte. La démonstration est claire et vérifiable.

Moments clés

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

Sources citées

  • Cayley's original paper (non fourni) — L'auteur mentionne l'article original de Cayley où la formule est énoncée, mais aucun lien n'est fourni.

Sources concordantes

Apport & nouveautés

La vidéo apporte une preuve visuelle et intuitive de la formule de Cayley, rendant accessible un résultat classique. Elle met en lumière la puissance des bijections en combinatoire et l’importance de la pondération par les symétries. La mention de la paternité de Borchardt corrige une idée reçue.

Pour aller plus loin :

  • Formule de Cayley — Article de Wikipédia détaillant la formule et ses preuves.
  • Théorie des graphes — Contexte général des arbres et graphes.
  • Combinatoire bijective — Méthode des bijections en combinatoire.

83 mots

Profil radar

Le profil radar montre un contenu très équilibré, avec une excellente qualité d'information et une fiabilité élevée, mais une quantité d'information modérée (vidéo courte). Le niveau technique est élevé, adapté à un public averti.

Fiabilité 9/10