ABSTRACT

We present a probabilistic proof of the hooklength formula, and of Schensted's theorem. The expectation and variance of numerous permutation statistics are computed. New to this edition are results related to the fringe of decreasing binary trees and other rooted trees related to permutations. In that work, we compute the limiting probability that a randomly selected vertex of a random tree of size https://www.w3.org/1998/Math/MathML"> n https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_13.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> has rank https://www.w3.org/1998/Math/MathML"> k https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_14.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> , that is, that its descending distance from the closest leaf is https://www.w3.org/1998/Math/MathML"> k https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_15.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> . It turns out that for large https://www.w3.org/1998/Math/MathML"> n https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9780429274107/76d8f3df-fdac-4af3-ad29-e5f6ca3c54a5/content/math0_16.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> , about 99.75 percent of all vertices of decreasing binary trees are of rank five or less.