DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: More Probabilistic Proofs of Hook Length Formulas Involving Trees

Speaker: David Grabiner, National Security Agency

Date: Thursday, March 31, 2011 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Han discovered two hook length formulas involving binary trees in which the hook lengths appear as exponents, rather than only as divisors as they do in most hook length formulas. Sagan gave a probabilistic proof of one of the formulas, and of generalizations to ordered trees and to finite subtrees of infinite rooted trees. We present another algorithm, choosing a random labeled tree by using each hook-length factor as a probability. Our algorithm gives a single proof of Han's first formula and both generalizations, and we show how both our algorithm and Sagan's algorithm can be modified to prove Han's second formula as well.