I'm interested in two 'natural bijections' that involve labeled forests and Young tableaux. Let me give the definition for labeled forests. By this, we mean a pair $\cal{F} = (F,f)$ where $F$ is an $n$-vertex forest, and $f$ is a labeling of its nodes from $1$ to $n$. We say that:
- $\cal{F}$ is standard if $f$ is bijective,
- $\cal{F}$ is sorted if the numbering is increasing along each root-to-leaf path,
- $\cal{F}$ is subexcedant if for each node $u$, $f(u)$ is at most the number of nodes of the subtree rooted at $u$.
Let $T_n,O_n,U_n$ denote the sets arising from these three cases, for a fixed size $n$. It is not too difficult to show the existence of a bijection $Sort_n : T_n \rightarrow O_n \times U_n$, which implies a well-known 'hook length' formula due to Knuth. One unpleasant aspect of this bijection lies in its assymetry: we would like to get a pair of similar objects in order to get extra symmetry properties (e.g. what would happen if we switch the two objects and then apply the reverse bijection?)
Therefore, I'm asking naively if you think that the symmetry could be restored by considering more general structures. I'm not optimistic on this question though: there might be a positive but difficult answer that so far eludes me. A side remark: this bijection $Sort_n$ already enjoys some interesting symmetry properties in connection with the Schützenberger involution, but we would need something stronger to get an interesting algebraic object (possibly a Hopf algebra?)
