Abstract We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator ${{\mathbf{M}}}$ . This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule ${{\mathbf{M}}} \mathsf{x}_1 \to \mathsf{x}_1 \mathsf{x}_1$ . We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on ${{\mathbf{M}}}$ and that all connected components of its rewrite graph are Hasse diagram of lattices. This last result is based on the introduction of new lattices on duplicative forests, which are sorts of treelike structures. These lattices are not graded, not self-dual, and not semi-distributive. We present some enumerative properties of these lattices like the enumeration of their elements, of the edges of their Hasse diagrams, and of their intervals. These results are derived from formal power series on terms and on duplicative forests endowed with particular operations.

The additive x-disorder of a permutation is the sum of the absolute differences of all pairs of consecutive elements. We show that the additive x-disorder of a permutation of S(n), n ≥ 2, ranges from n-1 to ⌊n²/2⌋ - 1, and we give a complete characterization of permutations having extreme such values. Moreover, for any positive integers n and d such that n ≥ 2 and n-1 ≤ d ≤ ⌊n²/2⌋ - 1, we propose a linear-time algorithm to compute a permutation π ∈ S(n) with additive x-disorder d.

A permutation is said to be a square if it can be obtained by shuffling two order-isomorphic patterns. The definition is intended to be the natural counterpart to the ordinary shuffle of words and languages. In this paper, we tackle the problem of recognizing square permutations from both the point of view of algebra and algorithms. On the one hand, we present some algebraic and combinatorial properties of the shuffle product of permutations. We follow an unusual line consisting in defining the shuffle of permutations by means of an unshuffling operator, known as a coproduct. This strategy allows to obtain easy proofs for algebraic and combinatorial properties of our shuffle product. We besides exhibit a bijection between square ( 213 , 231 ) -avoiding permutations and square binary words. On the other hand, by using a pattern avoidance criterion on directed perfect matchings, we prove that recognizing square permutations is NP -complete.