Chapter 22
Young Tableaux, Compositions, and Vertices and Arcs
New structures and familiar ones arise as we continue to investigate some of the many places where the Catalan numbers surface.
Example 22.1: This example introduces a combinatorial structure called a 2 by n Young Tableaux. These structures are named for the English clergyman and mathematician Alfred Young (1873–1940) and are made up of 2n cells divided into 2 rows and n columns. In using such a tableau, we want to count the number of ways we can place the integers from 1 to 2n into the 2n cells so that the entries in each row are in ascending order and, for each of the n columns, the entry in row 1 is smaller than the entry in row 2. For n = 3, we find that there are five such 2 by 3 Young Tableaux:
To set up a one-to-one correspondence between the Dyck paths in Fig. 21.1 and these 2 by 3 Young Tableaux, consider the Dyck path in Fig. 21.1 (a). Where are the D (
) steps in this path? They are the first, second, and third steps in the path—and so we place 1, 2, and 3 (in order) in the first row of the tableau. Likewise, we now consider the locations of the D* (
) steps in this path. Their locations, listed in order of occurrence, give us the results in the second row of the tableau—namely, 4, 5, 6. Applying this idea to ...
