Browse issues
no. 4
An elaborate new proof of Cayley’s formula
Banaian, Esther1; Hoang, Anh Trong Nam2; Kelley, Elizabeth3; Miller, Weston4; Stack, Jason5; Stephen, Carolyn6; Williams, Nathan7
1 University of California - Riverside Department of Mathematics 900 University Ave Riverside, CA 92521
2 Northeastern University Department of Mathematics, 567 Lake Hall 360 Huntington Avenue Boston, MA 02115
3 University of Oklahoma Department of Mathematics 601 Elm Ave Norman, OK, 73019
4 University of California - San Diego Department of Mathematics 9500 Gilman Drive La Jolla, CA 92093
5 University of Texas at Dallas Mathematical Sciences 800 West Campbell Road Richardson, TX 75080
6 University of Minnesota School of Mathematics, 550 Vincent Hall 206 Church Street SE Minneapolis, MN 55455
7 University of Texas at Dallas Mathematical Sciences, FO 35 800 West Campbell Road Richardson, TX 75080-3021
Algebraic Combinatorics, Volume 8 (2025) no. 4, pp. 971-995.

We construct a bijection between certain Deodhar components of a braid variety constructed from an affine Kac–Moody group of type $A_{n-1}$ and vertex-labeled trees on $n$ vertices. By an argument of Galashin, Lam, and Williams using Opdam’s trace formula in the affine Hecke algebra and an identity due to Haglund, we obtain an elaborate new proof for the enumeration of the number of vertex-labeled trees on $n$ vertices.

Received:
Accepted:
Published online:
DOI: 10.5802/alco.429
Classification: 05E10, 05E16
Keywords: braid variety, affine symmetric group, Opdam trace formula, affine Hecke algebra, Cayley’s theorem, tree, Deodhar decomposition

Banaian, Esther 1; Hoang, Anh Trong Nam 2; Kelley, Elizabeth 3; Miller, Weston 4; Stack, Jason 5; Stephen, Carolyn 6; Williams, Nathan 7

1 University of California - Riverside Department of Mathematics 900 University Ave Riverside, CA 92521
2 Northeastern University Department of Mathematics, 567 Lake Hall 360 Huntington Avenue Boston, MA 02115
3 University of Oklahoma Department of Mathematics 601 Elm Ave Norman, OK, 73019
4 University of California - San Diego Department of Mathematics 9500 Gilman Drive La Jolla, CA 92093
5 University of Texas at Dallas Mathematical Sciences 800 West Campbell Road Richardson, TX 75080
6 University of Minnesota School of Mathematics, 550 Vincent Hall 206 Church Street SE Minneapolis, MN 55455
7 University of Texas at Dallas Mathematical Sciences, FO 35 800 West Campbell Road Richardson, TX 75080-3021
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2025__8_4_971_0,
     author = {Banaian, Esther and Hoang, Anh Trong Nam and Kelley, Elizabeth and Miller, Weston and Stack, Jason and Stephen, Carolyn and Williams, Nathan},
     title = {An elaborate new proof of {Cayley{\textquoteright}s} formula},
     journal = {Algebraic Combinatorics},
     pages = {971--995},
     publisher = {The Combinatorics Consortium},
     volume = {8},
     number = {4},
     year = {2025},
     doi = {10.5802/alco.429},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.429/}
}
TY  - JOUR
AU  - Banaian, Esther
AU  - Hoang, Anh Trong Nam
AU  - Kelley, Elizabeth
AU  - Miller, Weston
AU  - Stack, Jason
AU  - Stephen, Carolyn
AU  - Williams, Nathan
TI  - An elaborate new proof of Cayley’s formula
JO  - Algebraic Combinatorics
PY  - 2025
SP  - 971
EP  - 995
VL  - 8
IS  - 4
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.429/
DO  - 10.5802/alco.429
LA  - en
ID  - ALCO_2025__8_4_971_0
ER  - 
%0 Journal Article
%A Banaian, Esther
%A Hoang, Anh Trong Nam
%A Kelley, Elizabeth
%A Miller, Weston
%A Stack, Jason
%A Stephen, Carolyn
%A Williams, Nathan
%T An elaborate new proof of Cayley’s formula
%J Algebraic Combinatorics
%D 2025
%P 971-995
%V 8
%N 4
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.429/
%R 10.5802/alco.429
%G en
%F ALCO_2025__8_4_971_0
Banaian, Esther; Hoang, Anh Trong Nam; Kelley, Elizabeth; Miller, Weston; Stack, Jason; Stephen, Carolyn; Williams, Nathan. An elaborate new proof of Cayley’s formula. Algebraic Combinatorics, Volume 8 (2025) no. 4, pp. 971-995. doi : 10.5802/alco.429. https://alco.centre-mersenne.org/articles/10.5802/alco.429/

[1] Armstrong, Drew; Garsia, Adriano; Haglund, James; Rhoades, Brendon; Sagan, Bruce Combinatorics of Tesler matrices in the theory of parking functions and diagonal harmonics, J. Comb., Volume 3 (2012) no. 3, pp. 451-494 | DOI | MR | Zbl

[2] Bao, Huanchen; He, Xuhua Flag manifolds over semifields, Algebra Number Theory, Volume 15 (2021) no. 8, pp. 2037-2069 | DOI | MR | Zbl

[3] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv+363 pages | MR | Zbl

[4] Cayley, Arthur A theorem on trees., Quart. J., Volume 23 (1888), pp. 376-378 | Zbl

[5] Deodhar, Vinay V. On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells, Invent. Math., Volume 79 (1985) no. 3, pp. 499-511 | DOI | MR | Zbl

[6] Galashin, Pavel; Lam, Thomas; Trinh, Minh-Tâm; Williams, Nathan Rational noncrossing Coxeter-Catalan combinatorics, Proc. Lond. Math. Soc. (3), Volume 129 (2024) no. 4, Paper no. e12643, 50 pages | DOI | MR | Zbl

[7] Goulden, Ian; Jackson, David Transitive factorisations into transpositions and holomorphic mappings on the sphere, Proc. Amer. Math. Soc., Volume 125 (1997) no. 1, pp. 51-60 | DOI | MR | Zbl

[8] Goulden, Ian; Yong, Alexander Tree-like properties of cycle factorizations, J. Combin. Theory Ser. A, Volume 98 (2002) no. 1, pp. 106-117 | DOI | MR | Zbl

[9] Haglund, James A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants, Adv. Math., Volume 227 (2011) no. 5, pp. 2092-2106 | DOI | MR | Zbl

[10] Kazhdan, David; Lusztig, George Representations of Coxeter groups and Hecke algebras, Invent. Math., Volume 53 (1979) no. 2, pp. 165-184 | DOI | MR | Zbl

[11] Leinster, Tom The probability that an operator is nilpotent, Amer. Math. Monthly, Volume 128 (2021) no. 4, pp. 371-375 | DOI | MR | Zbl

[12] Lewis, Joel Brewster; McCammond, Jon; Petersen, T. Kyle; Schwer, Petra Computing reflection length in an affine Coxeter group, Trans. Amer. Math. Soc., Volume 371 (2019) no. 6, pp. 4097-4127 | DOI | MR | Zbl

[13] McCammond, Jon; Petersen, T. Kyle Bounding reflection length in an affine Coxeter group, J. Algebraic Combin., Volume 34 (2011) no. 4, pp. 711-719 | DOI | MR | Zbl

[14] Opdam, Eric M. A generating function for the trace of the Iwahori-Hecke algebra, Studies in memory of Issai Schur (Chevaleret/Rehovot, 2000) (Progr. Math.), Volume 210, Birkhäuser Boston, Boston, MA, 2003, pp. 301-323 | DOI | MR | Zbl

[15] The Sage-Combinat community Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008 (http://combinat.sagemath.org)

[16] The Sage Developers SageMath, the Sage Mathematics Software System (Version 9.4) (2021) (https://www.sagemath.org)

[17] Stanley, Richard P. Parking functions and noncrossing partitions, Electron. J. Combin., Volume 4 (1997) no. 2, Paper no. 20, 14 pages | DOI | MR | Zbl

[18] Williams, Nathan Combinatorics and braid varieties, Open problems in algebraic combinatorics (Proc. Sympos. Pure Math.), Volume 110, Amer. Math. Soc., Providence, RI, 2024, pp. 93-112 | DOI | MR

Cited by Sources: