ABSTRACT
This chapter is devoted to the connections between permutations and various other objects in combinatorics. This is certainly a huge topic, and we can therefore only skim the surface of a few selected areas. Our goal is to give the reader an overview of some main lines of research to aid the decision of what literature to consult next. In the first section, we present the famous Robinson-Schensted-Knuth cor-
respondence that connects the combinatorics of permutations and the combinatorics of Standard Young Tableaux. There are several excellent books [224], [143] devoted entirely or mostly to the fascinating subject of Young Tableaux, and we will not try to parallel them. Instead, we will be concentrating on those parts of the area that are most directly connected to the enumeration of permutations. The Robinson-Schensted-Knuth correspondence provides a direct bijective
proof for Theorem 6.11, showing once again that the number of pairs of SYT of the same shape, consisting of n boxes each, is n!. This is achieved by a bijection risk from the set of all n-permutations onto that of such pairs. (There is no risk involved, but when pronounced, that word is shorter than, say, RSK.) In addition, the bijection has a very rich collection of interesting properties, such as turning natural parameters of permutations into natural parameters of SYT. To start, let π = π1π2 · · ·πn be an n-permutation. We are going to construct
a pair of Standard Young Tableaux risk(π) = (P,Q). The two tableaux will have the same shape. The two tableaux will be constructed together, in n steps, but according to different rules. In the P -tableau, some entries will move after they are placed, while this will not happen in the Q-tableau. We will call our tableaux P and Q throughout the procedure, but if we want to emphasize that they are not completely built yet, we call them Pi and Qi to show that only i steps of their construction have been carried out. We are going to describe the bijection risk step by step, and we will illus-
trate each step by the example of π = 52314.
