Discrete Mathematics & Theoretical Computer Science |
Let s_k(n) denote the sum of the digits in the base-k representation of n. In a celebrated paper, Thue showed that the infinite word (s_2(n) \bmod 2)_n≥ 0 is \emphoverlap-free, i.e., contains no subword of the form axaxa where x is any finite word and a is a single symbol. Let k,m be integers with k>2, m≥ 1. In this paper, generalizing Thue's result, we prove that the infinite word t_k,m := (s_k(n) \bmod m)_n≥ 0 is overlap-free if and only if m≥ k. We also prove that t_k,m contains arbitrarily long squares (i.e., subwords of the form xx where x is nonempty), and contains arbitrarily long palindromes if and only if m≤ 2.
We present an algorithm for unification of higher-order patterns modulo simple syntactic equational theories as defined by Kirchner [14]. The algorithm by Miller [17] for pattern unification, refined by Nipkow [18] is first modified in order to behave as a first-order unification algorithm. Then the mutation rule for syntactic theories of Kirchner [13,14] is adapted to pattern E-unification. If the syntactic algorithm for a theory E terminates in the first-order case, then our algorithm will also terminate for pattern E-unification. The result is a DAG-solved form plus some equations of the form λ øverlinex.F(øverlinex) = λ øverlinex. F(øverlinex^π ) where øverlinex^π is a permutation of øverlinex When all function symbols are decomposable these latter equations can be discarded, otherwise the compatibility of such equations with the solved form remains open.
A permutation π is said to be τ -avoiding if it does not contain any subsequence having all the same pairwise comparisons as τ . This paper concerns the characterization and enumeration of permutations which avoid a set F^j of subsequences increasing both in number and in length at the same time. Let F^j be the set of subsequences of the form σ (j+1)(j+2), σ being any permutation on \1,...,j\. For j=1 the only subsequence in F^1 is 123 and the 123-avoiding permutations are enumerated by the Catalan numbers; for j=2 the subsequences in F^2 are 1234 2134 and the (1234,2134)avoiding permutations are enumerated by the Schröder numbers; for each other value of j greater than 2 the subsequences in F^j are j! and their length is (j+2) the permutations avoiding these j! subsequences are enumerated by a number sequence \a_n\ such that C_n ≤ a_n ≤ n!, C_n being the nth Catalan number. For each j we determine the generating function of permutations avoiding the subsequences in F^j according to the length, to the number of left minima and of non-inversions.
A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules. Finding a transitive orientation and finding the modular decomposition are in some sense dual problems. In this paper, we describe a simple O(n + m \log n) algorithm that uses this duality to find both a transitive orientation and the modular decomposition. Though the running time is not optimal, this algorithm is much simpler than any previous algorithms that are not Ω (n^2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques.
Let (A_v)_v ∈ V be a finite family of sets. We establish an improved inclusion-exclusion identity for each closure operator on the power set of V having the unique base property. The result generalizes three improvements of the inclusion-exclusion principle as well as Whitney's broken circuit theorem on the chromatic polynomial of a graph.
We find an explicit expression for the generating function of the number of permutations in S_n avoiding a subgroup of S_k generated by all but one simple transpositions. The generating function turns out to be rational, and its denominator is a rook polynomial for a rectangular board.