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 ...