Shuffle of parenthesis systems and Baxter permutations. (English) Zbl 0662.05004

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 F. R. K. Chung, R. L. Graham, V. E. Hoggat jun. and 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 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 W. T. Tutte, Can. J. Math. 14, 402-417 (1962; Zbl 0105.17601)] and R. C. Mullin [Pac. J. Math. 16, 139-145 (1966; Zbl 0137.43001)]. Quite recently 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).


05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices
05C05 Trees
20B05 General theory for finite permutation groups
Full Text: DOI


[1] Andre, D, Développements de sec x et tan x, C. R. acad. sci. Paris, Sér. I math., 88, 965-967, (1879) · JFM 11.0187.01
[2] Andre, D, Sur LES permutations alternées, J. math. pures appl., 7, 167-184, (1881) · JFM 13.0152.02
[3] Baxter, G, On fixed points of the composite of commuting functions, (), 851-855 · Zbl 0126.38701
[4] Chung, F; Graham, R; Hoggatt, V; Kleiman, M, The number of Baxter permutations, J. combin. theory ser. A, 24, 382-394, (1978) · Zbl 0398.05003
[5] Foata, D; Schützenberger, M.P; Foata, D; Schützenberger, M.P, Nombres d’Euler et permutations alternantes, (), 173-187, (1971), University of Florida Gainesville, first part published · Zbl 0271.05005
[6] Foata, D; Strehl, V, Rearrangements of the symetric group and enumerative properties of the tangent and secant numbers, Math. Z, 137, 257-264, (1973) · Zbl 0274.05007
[7] Françon, J, Arbres binaires de recherche: propriétés combinatoires et applications, R.A.I.R.O. inform. théor., 10, 35-50, (1978) · Zbl 0344.05103
[8] Lothaire, M, Combinatorics on words, (1983), Addison-Wesley Reading, Mass., · Zbl 0514.20045
[9] Mallows, C.L, Baxter permutations rise again, J. combin. theory Sér. A, 27, 394-396, (1979) · Zbl 0427.05005
[10] Mullin, R.C, The enumeration of Hamiltonian polygons in triangular maps, Pacific J. math., 16, 139-145, (1966) · Zbl 0137.43001
[11] Tutte, W.T, A census of Hamiltonian polygons, Canad. J. math., 14, 402-417, (1962) · Zbl 0105.17601
[12] Viennot, G, Quelques algorithmes de permutations, (), 275-293 · Zbl 0363.05004
[13] Viennot, G, A bijective proof for the number of Baxter permutations, preprint and lecture at the “Séminaire lothagingien,”, (1981), Le Klebach
[14] {\scG. Viennot}, Interprétations combinatoires des nombres d’Euler et de Genocchi, in “Séminaire de Théorie des Nombres 1981-1982,” exposé no 11, Publ. Univ. Bordeaux I, pp. 1-94.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.