The standard factorization of Lyndon words: an average point of view

A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a two-letter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.     

Unbordered factors and Lyndon words

A primitive word w is a Lyndon word if w is minimal among all its conjugates with respect to some lexicographic order. A word w is bordered if there is a nonempty word u such that w=uvu for some word v. A right extension of a word w of length n is a word wu where all factors longer than n are bordered. A right extension wu of w is called trivial if there exists a positive integer k such that w^k=uv for some word v.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word w which has a nontrivial right extension of length 2|w|-2.     

Necklaces of beads in k colors and k-ary de Bruijn sequences

This paper constructs a decreasing lexicographic list of necklaces of length n in beads of k colors. This list, somewhat modified, produces a k-ary de Bruijn sequence of length kⁿ.     

Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2)

Many applications call for exhaustive lists of strings subject to various constraints, such as inequivalence under group actions. A k-ary necklace is an equivalence class of k-ary strings under rotation (the cyclic group). A k-ary unlabeled necklace is an equivalence class of k-ary strings under rotation and permutation of alphabet symbols. We present new, fast, simple, recursive algorithms for generating (i.e., listing) all necklaces and binary unlabeled necklaces. These algorithms have optimal running times in the sense that their running times are proportional to the number of necklaces produced. The algorithm for generating necklaces can be used as the basis for efficiently generating many other equivalence classes of strings under rotation and has been applied to generating bracelets, fixed density necklaces, and chord diagrams. As another application, we describe the implementation of a fast algorithm for listing all degree n irreducible and primitive polynomials over GF(2).     

Binary bubble languages and cool-lex order

A bubble language is a set of binary strings with a simple closure property: The first 01 of any string can be replaced by 10 to obtain another string in the set. Natural representations of many combinatorial objects are bubble languages. Examples include binary string representations of k-ary trees, unit interval graphs, linear-extensions of B-posets, binary necklaces and Lyndon words, and feasible solutions to knapsack problems. In co-lexicographic order, fixed-weight binary strings are ordered so that their suffixes of the form i¹⁰ occur (recursively) in the order i=max,max−1,…,min+1,min for some values of max and min. In cool-lex order the suffixes occur (recursively) in the order max−1,…,min+1,min,max. This small change has significant consequences. We prove that the strings in any bubble language appear in a Gray code order when listed in cool-lex order. This Gray code may be viewed from two different perspectives. On one hand, successive binary strings differ by one or two transpositions, and on the other hand, they differ by a shift of some substring one position to the right. This article also provides the theoretical foundation for many efficient generation algorithms, as well as the first construction of fixed-weight binary de Bruijn sequences; results that will appear in subsequent articles.     

Necklaces,symmetries and self-reciprocal polynomials

The connection between a certain class of necklaces and self-reciprocal polynomials over finite fields is shown. For n?2, self-reciprocal polynomials of degree 2n arising from monic irreducible polynomials of degree n are shown to be either irreducible or the product or two irreducible factors which are necessarily reciprocal polynomials. Using DeBruijn's method we count the number of necklaces in this class and hence obtain a formula for the number of irreducible self-reciprocal polynomials showing that they exist for every even degree. Thus every extension of a finite field of even degree can be obtained by adjoining a root of an irreducible self-reciprocal polynomial.     

Counting and ordering periodic stationary solutions of lattice Nagumo equations

We study the rich structure of periodic stationary solutions of Nagumo reaction diffusion equation on lattices. By exploring the relationship with Nagumo equations on cyclic graphs we are able to divide these periodic solutions into equivalence classes that can be partially ordered and counted. In order to accomplish this, we use combinatorial concepts such as necklaces, bracelets and Lyndon words.     

The lexicographically smallest universal cycle for binary strings with minimum specified weight

H. Fredricksen, I.J. Kessler and J. Maiorana discovered a simple but elegant construction of a universal cycle for binary strings of length n: Concatenate the aperiodic prefixes of length n binary necklaces in lexicographic order. We generalize their construction to binary strings of length n whose weights are in the range $c,c+1,\dots ,n$ by simply omitting the necklaces with weight less than c. We also provide an efficient algorithm that generates the universal cycles in constant amortized time per bit using $O(n)$ space. Our universal cycles have the property of being the lexicographically smallest universal cycle for the set of binary strings of length n with weight ≥c.     

Two-sided estimates for essential height in Shirshov’s Height Theorem

The paper is focused on two-sided estimates for the essential height in Shirshov??s Height Theorem. The concepts of the selective height and strong n-divisibility directly related to the height and n-divisibility are introduced. We prove lower and upper bounds for the selective height over nonstrongly n-divisible words of length 2. For any n and sufficiently large l these bounds differ at most twice. The case of words of length 3 is also studied. The case of words of length 2 can be generalized to the proof of an upper exponential estimate in Shirshov??s Height Theorem. The proof uses the idea of V.N. Latyshev related to the application of Dilworth??s theorem to the study of non n-divisible words.     

Ranking and unranking of B-trees

Algorithms are presented for the ranking, unranking, and generation of all B-trees of order m with n leaves. The algorithms take time proportional to the sizes of their output. It is shown how a search graph can be constructed to aid in the ranking and unranking of B-trees.     

Omnibus Sequences, Coupon Collection, and Missing Word Counts

In this paper, we study the properties of k-omnisequences of length n, defined to be strings of length n that contain all strings of smaller length k embedded as (not necessarily contiguous) subsequences. We start by proving an elementary result that relates our problem to the classical coupon collector problem. After a short survey of relevant results in coupon collection, we focus our attention on the number M of strings (or words) of length k that are not found as subsequences of an n string, showing that there is a gap between the probability threshold for the emergence of an omnisequence and the zero-infinity threshold for ${\mathbb E}(M)$ .     

Combinatorics on partial word correlations

Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, we consider the period and weak period sets of partial words of length n over a finite alphabet, and study the combinatorics of specific representations of them, called correlations, which are binary and ternary vectors of length n indicating the periods and weak periods. We characterize precisely which vectors represent the period and weak period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under suitably defined partial orderings. We show that there is a well-defined minimal set of generators for any binary correlation of length n and demonstrate that these generating sets are the primitive subsets of {1,2,…,n−1}. We also investigate the number of partial word correlations of length n. Finally, we compute the population size, that is, the number of partial words sharing a given correlation, and obtain recurrences to compute it. Our results generalize those of Guibas, Odlyzko, Rivals and Rahmann.     

Lexicographic compositions and deBruijn sequences

In this paper we give an algorithm to generate a new deBruijn sequence. The amount of storage required is only linear in n, the span of the sequence. We make use of the lexicographic compositions of a positive integer which we relate to binary necklaces of beads in two colors. We give a fast algorithm for generating the necklaces. Finally we relate the deBruijn sequence we generate to another sequence.     

On the number of antipodal bicolored necklaces

Let ν(2n) be the number of antipodal bicolored necklaces with 2n pearls. In this note, we find the first two terms of the asymptotic expansion of ν(2n). As a byproduct of this result, we also show that the sequence (ν(2n)) _n≥1 is non-holonomic, i.e., it satisfies no linear recurrence of a fixed finite order k with polynomial coefficients.     

Some combinatorial properties of words in discrete dynamical systems from antisymmetric cubic maps

In this paper, we study the combinatorial properties ol words m chscrete dynamical systems from antisymmetric cubic maps. We also discuss the relationship of primitive kneading sequences of length n and period-doubling kneading sequences of length 2n, and then determine the number of all kneading sequences of length n.     

Solving necklace constraint problems

Some constraint problems have a combinatorial structure where the constraints allow the sequence of variables to be rotated (necklaces), if not also the domain values to be permuted (unlabelled necklaces), without getting an essentially different solution. We bring together the fields of combinatorial enumeration, where efficient algorithms have been designed for (special cases of) some of these combinatorial objects, and constraint programming, where the requisite symmetry breaking has at best been done statically so far. We design the first search procedure and identify the first symmetry-breaking constraints for the general case of unlabelled necklaces. Further, we compare dynamic and static symmetry breaking on real-life scheduling problems featuring (unlabelled) necklaces.     

Segments,rectangles, contours

Two sets H and V of horizontal and vertical segments, respectively, determine a subdivision M of the plane into regions. A nontrivial region is one whose boundary contains an end-portion of nonzero length of at least one segment, and the nontrivial contour of M is the collection of boundaries of nontrivial regions. In this paper we consider several problems pertaining to H and V, such as the construction of the nontrivial contour of M, of the external contour of M, and of a path between two points in the plane avoiding the segments (route-in-a-maze). We show that, if |H| + |V| = n, all of these problems are solved in time O(n log n), by making use of a static data structure, called the adjacency map, which can be searched in time O(log n) and can be constructed in time O(n log n). The algorithms for the nontrivial and external contour are shown to be optimal.     

Self-dual codes over GF(5)

It is shown that a self-orthogonal code over GF(5) which is generated by words of weight 4 has a decomposition into components belonging to three infinite families: d_n (n = 4, 5, 6, 7, 8, 10, 12,…), e_n (n = 6, 8, 10,…) and F_n (n = 6, 8, 10,…). All maximal self-orthogonal (and self-dual) codes of length ? 12 are classified, and a number of interesting codes of greater length are constructed.     

Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks

We develop a number of statistical aspects of symmetric groups (mostly dealing with the distribution of cycles in various subsets of Sn), asymptotic properties of (ordinary) characters of symmetric groups, and estimates for the multiplicities of root number functions of these groups. As main applications, we present an estimate for the subgroup growth of an arbitrary Fuchsian group, a finiteness result for the number of Fuchsian presentations of such a group (resolving a long-standing problem of Roger Lyndon), as well as a proof of a well-known conjecture of Roichman concerning the mixing time of random walks on symmetric groups.