Shuffle of parenthesis systems and Baxter permutations (Q1113902): Difference between revisions

Baxter permutations are permutations \(\sigma =\sigma_ 1\sigma_ 2...\sigma_ n\) of \([n]=\{1,2,...,n\}\) satisfying for any quadruple \(1\leq i<j<k<\ell \leq n\) the following two conditions: (B1) if \(\sigma_ i+1=\sigma_{\ell}<\sigma_ j\), then \(\sigma_ k>\sigma_{\ell}\), (B2) if \(\sigma_{\ell}+1=\sigma_ i<\sigma_ k\), then \(\sigma_ j>\sigma_ i\). They appeared in the study of fixed points of the compositions of two commuting continuous mappings of the unit interval into itself. An article by \textit{F. R. K. Chung}, \textit{R. L. Graham}, \textit{V. E. Hoggat jun.} and \textit{M. Kleiman} [ibid., Ser. A 24, No.3, 382-394 (1978; Zbl 0398.05003)] gives some background and proves a nice formula for the number of these permutations. In the article under review, the class of alternating Baxter permutations is studied, i.e. permutations which satisfy (B1) and (B2) above and which are at the same time alternating in the classical sense, as introduced by \textit{D. André} [J. Math. Pures Appl. (3) 7, 167-184 (1881; JFM 13.0152.02)]: they follow the up-down pattern \(\sigma_ 1<\sigma_ 2>\sigma_ 3<\sigma_ 4>... \). The main result is a beautiful formula for the number of alternating Baxter permutations on [2n] [resp. \([2n+1]]:\) it is \(C^ 2_ n\) [resp. \(C_ n\cdot C_{n+1}]\), where the \(C_ n=\left( \begin{matrix} 2n\\ n\end{matrix} \right)/(n+1)\) are the familiar Catalan numbers. The article is nicely written in the spirit of bijective combinatorics: the main result is obtained by (1) establishing a one-to-one correspondence between alternating Baxter permutations and a certain class of labeled binary trees; (2) analyzing these trees in a twofold way, regarding the tree-structure and the labeling of the leaves separately. The combination of (1) and (2) shows that alternating Baxter permutations of [2] are in one-to-one correspondence with pairs of Dyck words (over a 2-letter alphabet) of length 2n (and similarly for the odd case). (1) alone also shows that alternating Baxter permutations can be coded via a shuffle of two Dyck languages over disjoint 2-letter alphabets. This furnishes a bijective proof of the (known) identity \[ C_ n\cdot C_{n+1}=\sum^{n}_{k=0}\left( \begin{matrix} 2n\\ 2k\end{matrix} \right)C_ k\cdot C_{n-k}. \] It is remarkable that the numbers \(C^ 2_ n\) and \(C_ n\cdot C_{n+1}\) of the main result also show up in the enumeration of certain families of planar maps [see \textit{W. T. Tutte}, Can. J. Math. 14, 402-417 (1962; Zbl 0105.17601)] and \textit{R. C. Mullin} [Pac. J. Math. 16, 139-145 (1966; Zbl 0137.43001)]. Quite recently \textit{D. Gouyou-Beauchamps} has shown that these numbers also count certain lattice paths in the plane [Combinatoire enumerative, Proc. Colloq., Montreal/Can. 1985, Lect. Notes Math. 1234, 112-125 (1986; Zbl 0611.05003)], and that \(C^ 2_ n\) [resp. \(C_ n\cdot C_{n+1}]\) equals the number of standard Young tableaux with at most 4 rows and 2n-1 [resp. 2n] cells [``Standard Young tableaux of highet 4 and 5'', Eur. J. Comb. 10, No.1, 69-82 (1989; Zbl 0672.05012).