×

zbMATH — the first resource for mathematics

A direct bijective proof of the hook-length formula. (English) Zbl 0934.05125
This is probably the most important recent contribution to bijective combinatorics. The hook-length formula states that the number of standard Young tableaux of a given shape \(\lambda\), where \(\lambda\) is a partition of \(n\) (viewed as a Ferrers diagram), is given by \(n!/\prod_\rho h_\rho\), where the product ranges over all cells \(\rho\) of \(\lambda\) and where \(h_\rho\) is the hook-length corresponding to \(\rho\). In view of such a nice, combinatorial formula, it is natural to ask for a “nice”, i.e., bijective, proof that would explain the form of the formula. That is, one is looking for a bijection which would explain the formula \[ \#(\text{SYT of shape }\lambda)\prod_\rho h_\rho= n!.\tag{\(*\)} \] There do already exist such “hook bijections”, by D. S. Franzblau and D. Zeilberger [J. Algorithms 3, No. 4, 317-343 (1982; Zbl 0498.68042)], J. B. Remmel [Linear Multlinear Algebra 11, No. 1, 45-100 (1982; Zbl 0485.05005)], D. Zeilberger [Discrete Math. 51, No. 1, 101-108 (1984; Zbl 0551.05010)], and the reviewer [Electron. J. Comb. 2, Research Paper R13 (1995; Zbl 0822.05065)]. However, none of them is regarded as really “satisfactory”. In contrast, the bijection presented in the paper under review (an announcement of the bijection, but without proof, is contained in I. M. Pak and A. V. Stoyanovskii [Funct. Anal. Appl. 26, No. 3, 216-218 (1992; Zbl 0796.05093); translation from Funct. Anal. Prilozh. 26, No. 3, 80-82 (1992)]) must be considered as the natural hook bijection. It fulfills the dream that one would start with an arbitrary filling of the shape \(\lambda\) with \(1,2,\dots,n\) (the number of such fillings being counted by the right-hand side of \((*)\)), sort the entries step by step by jeu de taquin moves in order to obtain a standard Young tableau in the end, and, simultaneously, record the moves by objects that are counted by the hook product (the second term on the left-hand side of \((*)\)). The recording, which of course is the non-obvious part in such a constrution, is tricky, but simple. The inverse of the algorithm also has a simple, but highly nontrivial description.
Reviewer’s remark: The reviewer combined the recording idea of this paper with a modified jeu de taquin from his earlier paper [Discrete Math. Theor. Comput. Sci. 3, No. 1, 11-32 (1998; Zbl 0934.05124)] to construct in [“Another involution principle-free bijective proof of Stanley’s hook-content formula”, J. Comb. Theory, Ser. A 88, No. 1, 66-92 (1999)] an equally natural bijective proof of the hook-content formula for the generating function for semistandard tableaux of a given shape with bounded entries, which, as a by-product, can also be used to generate such tableaux at random. A slight modification of this algorithm gives an algorithm for the random generation of plane partitions inside a given box.

MSC:
05E10 Combinatorial aspects of representation theory
05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
PDF BibTeX XML Cite
Full Text: EMIS EuDML