ABSTRACT
Ron Adin and Yuval Roichman Bar-Ilan University, Ramat-Gan, Israel
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896 14.1.1 Appetizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896 14.1.2 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898
14.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898 14.2.1 Diagrams and tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898 14.2.2 Connectedness and convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899 14.2.3 Invariance under symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900 14.2.4 Ordinary, skew and shifted shapes . . . . . . . . . . . . . . . . . . . . . . . . . . 901 14.2.5 Interpretations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903
14.2.5.1 The Young lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903 14.2.5.2 Ballot sequences and lattice paths . . . . . . . . . . . . 903 14.2.5.3 The order polytope . . . . . . . . . . . . . . . . . . . . . . . . . . 904 14.2.5.4 Other interpretations . . . . . . . . . . . . . . . . . . . . . . . . . 905
14.2.6 Miscellanea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905 14.3 Formulas for thin shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905
14.3.1 Hook shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905 14.3.2 Two-rowed shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906 14.3.3 Zigzag shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
14.4 Jeu de taquin and the RS correspondence . . . . . . . . . . . . . . . . . . . . . . . . . . . 908 14.4.1 Jeu de taquin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908 14.4.2 The Robinson-Schensted correspondence . . . . . . . . . . . . . . . . . . 910 14.4.3 Enumerative applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911
14.5 Formulas for classical shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913 14.5.1 Ordinary shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913 14.5.2 Skew shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916 14.5.3 Shifted shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918
14.6 More proofs of the hook length formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919 14.6.1 A probabilistic proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919 14.6.2 Bijective proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921
14.6.3 Partial difference operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926 14.7 Formulas for skew strips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 930
14.7.1 Zigzag shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 930 14.7.2 Skew strips of constant width . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 933
14.8 Truncated and other non-classical shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . 938 14.8.1 Truncated shifted staircase shape . . . . . . . . . . . . . . . . . . . . . . . . . . . 938 14.8.2 Truncated rectangular shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939 14.8.3 Other truncated shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 941 14.8.4 Proof approaches for truncated shapes . . . . . . . . . . . . . . . . . . . . . . 942
14.9 Rim hook and domino tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944 14.9.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944 14.9.2 The r-quotient and r-core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945
14.10 q-Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949 14.10.1 Permutation statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949 14.10.2 Statistics on tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950 14.10.3 Thin shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952
14.10.3.1 Hook shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952 14.10.3.2 Zigzag shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952 14.10.3.3 Two-rowed shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . 953
14.10.4 The general case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955 14.10.4.1 Counting by descents . . . . . . . . . . . . . . . . . . . . . . . . 955 14.10.4.2 Counting by major index . . . . . . . . . . . . . . . . . . . . . 956 14.10.4.3 Counting by inversions . . . . . . . . . . . . . . . . . . . . . . . 957
14.11 Counting reduced words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957 14.11.1 Coxeter generators and reduced words . . . . . . . . . . . . . . . . . . . . . 957 14.11.2 Ordinary and skew shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958 14.11.3 Shifted shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 960
14.12 Appendix 1: Representation theoretic aspects . . . . . . . . . . . . . . . . . . . . . . . 961 14.12.1 Degrees and enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961 14.12.2 Characters and q-enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963
14.13 Appendix 2: Asymptotics and probabilistic aspects . . . . . . . . . . . . . . . . . . 964 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 966
Consider throwing balls labeled 1,2, . . . ,n into a V-shaped bin with perpendicular sides.
