Lyndon words, permutations and trees. (English) Zbl 1058.68086

From the introduction: A well-known combinatorial construction, that has many applications in Computer Science, maps bijectively permutations in \(S_n\) onto binary, planary trees, with labels in \(\{1,\dots,n\}\), increasing from root to leaves. On the other hand, to each Lyndon word a binary, planar, complete tree is associated, with leaves labelled by the letters of the word; again the inverse mapping is the projection. Both constructions lead to bases of the free Lie algebra consisting of the collection of all Lie polynomials defined by Lyndon words. We show that this second construction reduces to the first: indeed, one can associate to each (Lyndon) word a permutation, that we call its suffix standard permutation. This permutation then gives a tree, as in the first construction. This tree, once completed, gives the tree of the Lyndon word, by writing the letters on the leaves.


68R15 Combinatorics on words
68Q45 Formal languages and automata
Full Text: DOI


[1] Chen, K.-T.; Fox, R.; Lyndon, R., Free differential calculus IV. the quotient group of the lower central series, Ann. math., 68, 81-95, (1958) · Zbl 0142.22304
[2] M. Crochemore, T. Hancart, T. Lecroq, Algorithmique du texte, Vuibert, 2001.
[3] Donaghey, R., Alternating permutations and binary increasing trees, J. combin. theory A, 18, 141-148, (1975) · Zbl 0304.05101
[4] Duval, J.-P., Factorizing words over an ordered alphabet, J. algorithms, 4, 363-381, (1983) · Zbl 0532.68061
[5] D. Foata, M.-P. Schützenberger, Nombres d’Euler et permutations alternantes, University of Florida, Gainesville, Department of Mathematics, 1971, preprint.
[6] Françon, J., Arbres binaires de recherchepropriétés combinatoires et applications, RAIRO inform. théor., 10, 37-50, (1976) · Zbl 0344.05103
[7] Gessel, I.; Reutenauer, C., Counting permutations with given cycle structure and descent set, J. combin. theory A, 64, 189-215, (1993) · Zbl 0793.05004
[8] Kundu, S., Sorting tree, nestling tree and inverse permutation, Inform. process. lett., 6, 94-96, (1977) · Zbl 0357.05036
[9] M. Lothaire, Combinatorics on Words, 2nd Ed., Addison-Wesley, Reading, MA, 1983; Cambridge University Press, Cambridge, 1997. · Zbl 0514.20045
[10] McCreight, E., A space-economical suffix tree construction algorithm, J. assoc. comput. Mach., 23, 262-272, (1976) · Zbl 0329.68042
[11] Melançon, G., Combinatorics of Hall trees and Hall words, J. combin. theory A, 59, 285-308, (1992) · Zbl 0761.05033
[12] Melançon, G.; Reutenauer, C., Lyndon words, free algebras and shuffles, Canad. J. math., 41, 577-591, (1989) · Zbl 0694.17003
[13] Schensted, C., Longest increasing and decreasing subsequences, Canad. J. math., 13, 179-191, (1961) · Zbl 0097.25202
[14] M.-P. Schützenberger, Sur une propriété combinatoire des algèbres de lie libres pouvant être utilisée dans un problème de mathématiques appliquées, Séminaire P. Dubreil, Paris, Faculté des Sciences, 1958.
[15] Sedgewick, R.; Flajolet, P., An introduction to the analysis of algorithms, (1996), Addison-Wesley Reading, MA
[16] R. Stanley, Enumerative Combinatorics, Vol. A, Wadsworth and Brooks/Cole, 1986. · Zbl 0608.05001
[17] G. Viennot, Quelques algorithmes de permutation, in: Journées algorithmiques, Paris, Society for Mathematics of France, Astérisque, 1976, pp. 38-39, pp. 275-293.
[18] J. Vuillemin, A unifying look at data structures, Comm. ACM 23, 1980, pp. 229-239. · Zbl 0434.68047
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.