From Dyck paths to standard Young tableaux

Abstract

The number of Dyck paths of semilength \(n\) is certainly not equal to the number of standard Young tableaux (SYT) with \(n\) boxes. We investigate several ways to add structure or restrict these sets so as to obtain equinumerous sets. Our most sophisticated bijective proof starts with Dyck paths whose \(k\)-ascents for \(k>1\) are labeled by connected matchings on \([k]\) and arrives at SYT with at most \(2k-1\) rows. Along the way, this bijection visits \(k\)-noncrossing and \(k\)-nonnesting partial matchings, oscillating tableaux and involutions with decreasing subsequences of length at most \(2k-1\). In addition, we present bijections from eight other types of Dyck and Motzkin paths to certain classes of SYT.