# Bijection between noncrossing matchings on $2b$ points and Standard Young Tableaux of size $2 \times b$

I'm currently reading a review article called Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance by Jessica Striker. In this article, Striker writes that there is a ''nice'' bijection between the set of noncrossing matchings of $2b$ points and $SYT(2 \times b)$, the set of standard Young tableaux of size $2 \times b$. Here are two examples of the bijection:

Unfortunately, I cannot seem to understand how exactly this bijection works.

As can be seen in the figure, given any pair $(i, j)$ with $i<j$ in the noncrossing matching, we want to map this to this to a tableau with $i$ on the first row and $j$ on the second row. But it is neither clear to me why this map should be injective nor surjective.

• They both correspond to Dyck paths (or Dyck words) of length 2b in an easy way. For noncrossing matchings write U when an arc starts at a number and D when an arc ends at a number- this gives a bijection to Dyck words. For SYT the U letters are in the first row and the D letters are in the second row. – Sam Hopkins May 29 '18 at 15:45
• (There are Catalan number many of these objects.) – Sam Hopkins May 29 '18 at 15:45
• I'll pm you on Facebook if you need to discuss the code in my answer below. Or we can meet in my office some day (KTH). – Per Alexandersson May 29 '18 at 18:22
• Following up on @SamHopkins, here are the citations in Richard Stanley's Catalan Numbers (Cambridge, 2015). Two-row standard Young tableaux are interpretation 168 (p44) and non crossing matchings (drawn in a line) are number 61 (p28). – Brian Hopkins May 30 '18 at 12:36

If you can understand Mathematica, the following code does what you wish. It first convert the SSYT to a Dyck path (0 and 1), always starting with a 0, and then from there, convert to perfect matching.

SSYTToDyckWord[tab_List] := Module[{n = Length[tab[[1]]]},
Table[Boole[! MemberQ[tab[[1]], k]], {k, 2 n}]
];
DyckWordToNoncrossingMatching[dw_List] :=
Module[{n = Length@dw, dw2 = dw, pm = {}, rem, p},
rem = Range[n];
While[Length[dw2] > 0,
p = Position[dw2, 0, 1][[-1, 1]];
AppendTo[pm, {rem[[p]], rem[[p + 1]]}];
rem = Delete[rem, {{p}, {p + 1}}];
dw2 = Delete[dw2, {{p}, {p + 1}}];
];
Sort@pm
];
DyckWordToNoncrossingMatching@
SSYTToDyckWord[{{1, 2, 3, 4, 7}, {5, 6, 8, 9, 10}}]


This returns {{1, 10}, {2, 9}, {3, 6}, {4, 5}, {7, 8}}