A direct bijective proof of the hook-length formula

Jean-Christophe Novelli; Igor Pak; Alexander V. Stoyanovskii

doi:10.46298/dmtcs.239

Jean-Christophe Novelli ; Igor Pak ; Alexander V. Stoyanovskii - A direct bijective proof of the hook-length formula

dmtcs:239 - Discrete Mathematics & Theoretical Computer Science, January 1, 1997, Vol. 1 - https://doi.org/10.46298/dmtcs.239

A direct bijective proof of the hook-length formulaArticle

Authors: Jean-Christophe Novelli ¹; Igor Pak ²; Alexander V. Stoyanovskii ³

1 Laboratoire d'informatique Algorithmique : Fondements et Applications
2 Department of Mathematics [Cambridge]
3 Department of Mathematics [Moscou]

This paper presents a new proof of the hook-length formula, which computes the number of standard Young tableaux of a given shape. After recalling the basic definitions, we present two inverse algorithms giving the desired bijection. The next part of the paper presents the proof of the bijectivity of our construction. The paper concludes with some examples.

https://doi.org/10.46298/dmtcs.239

Source: HAL:hal-00955690v1

Volume: Vol. 1

Published on: January 1, 1997

Imported on: March 26, 2015

Keywords: Hook-length formula,bijective proof,inverse algorithms,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Bibliographic References

17 Documents citing this article

Daniel R. L. Brown, 2023, Plactic key agreement (insecure?), Journal of Mathematical Cryptology, 17, 1, 10.1515/jmc-2022-0010, https://doi.org/10.1515/jmc-2022-0010.

Alejandro H. Morales;Igor Pak;Greta Panova, 2022, Hook Formulas for Skew Shapes IV. Increasing Tableaux and Factorial Grothendieck Polynomials, Journal of mathematical sciences (Cham), 261, 5, pp. 630-657, 10.1007/s10958-022-05777-0, https://doi.org/10.1007/s10958-022-05777-0.

Matjaž Konvalinka, 2020, A bijective proof of the hook-length formula for skew shapes, arXiv (Cornell University), 88, pp. 103104, 10.1016/j.ejc.2020.103104, https://arxiv.org/abs/1703.08414.

Alejandro H. Morales;Igor Pak;Greta Panova, 2018, Hook formulas for skew shapes I. q-analogues and bijections, Journal of combinatorial theory. Series A (Print), 154, pp. 350-405, 10.1016/j.jcta.2017.09.002, https://doi.org/10.1016/j.jcta.2017.09.002.

Brian Y. Sun;Yingying Hu, 2018, A probabilistic method for the number of standard immaculate tableaux, Rocky Mountain Journal of Mathematics, 48, 6, 10.1216/rmj-2018-48-6-2087.

Matjaž Konvalinka, 2017, A bijective proof of the hook-length formula for skew shapes, arXiv (Cornell University), 61, pp. 765-771, 10.1016/j.endm.2017.07.034, http://arxiv.org/abs/1703.08414.

Chapman and Hall/CRC eBooks, Mean and Insensitive. Random Permutations, pp. 253-292, 2016, 10.1201/b12210-13.

Christoph Neumann;Robin Sulzgruber, 2015, A complexity theorem for the Novelli–Pak–Stoyanovskii algorithm, arXiv (Cornell University), 135, pp. 85-104, 10.1016/j.jcta.2015.04.001, https://arxiv.org/abs/1306.5134.

Ionuţ Ciocan-Fontanine;Matjaž Konvalinka;Igor Pak, 2012, Quantum cohomology of Hilbn(C2) and the weighted hook walk on Young diagrams, Journal of Algebra, 349, 1, pp. 268-283, 10.1016/j.jalgebra.2011.10.011, https://doi.org/10.1016/j.jalgebra.2011.10.011.

Ionu Ciocan-Fontanine;Matja Konvalinka;Igor Pak, 2011, The weighted hook length formula, arXiv (Cornell University), 118, 6, pp. 1703-1717, 10.1016/j.jcta.2011.02.004, https://arxiv.org/abs/1006.0043.

Martin Griffiths;Nick Lord, 2011, The hook-length formula and generalised Catalan numbers, The Mathematical Gazette, 95, 532, pp. 23-30, 10.1017/s002555720000228x, https://doi.org/10.1017/s002555720000228x.

Rong Zhang, 2010, On an identity of Glass and Ng concerning the hook length formula, Discrete mathematics, 310, 17-18, pp. 2440-2442, 10.1016/j.disc.2010.05.013.

Olivier Bodini;Éric Fusy;Carine Pivoteau, 2009, Random Sampling of Plane Partitions, arXiv (Cornell University), 19, 2, pp. 201-226, 10.1017/s0963548309990332.

F. Hivert;J.-C. Novelli;J.-Y. Thibon, 2005, The algebra of binary search trees, arXiv (Cornell University), 339, 1, pp. 129-165, 10.1016/j.tcs.2005.01.012, https://arxiv.org/abs/math/0401089.

Ilse Fischer, 2002, A Symmetry Theorem on a Modified Jeu De Taquin, European journal of combinatorics (Print), 23, 8, pp. 929-936, 10.1006/eujc.2002.0621, https://doi.org/10.1006/eujc.2002.0621.

C. Krattenthaler, 1999, Another Involution Principle-Free Bijective Proof of Stanley's Hook-Content Formula, Journal of Combinatorial Theory, Series A, 88, 1, pp. 66-92, 10.1006/jcta.1999.2979, https://doi.org/10.1006/jcta.1999.2979.

Christian Krattenthaler, 1998, An Involution Principle-Free Bijective Proof of Stanley's Hook-Content Formula, Discrete Mathematics & Theoretical Computer Science, Vol. 3 no. 1, 10.46298/dmtcs.258, https://doi.org/10.46298/dmtcs.258.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1296 times.

This article's PDF has been downloaded 1085 times.