On the sub-permutations of pattern avoiding permutations

There is a deep connection between permutations and trees. Certain sub-structures of permutations, called sub-permutations, bijectively map to sub-trees of binary increasing trees. This opens a powerful tool set to study enumerative and probabilistic properties of sub-permutations and to investigate the relationships between 'local' and 'global' features using the concept of pattern avoidance. First, given a pattern mu, we study how the avoidance of mu in a permutation pi affects the presence of other patterns in the sub-permutations of pi. More precisely, considering patterns of length 3, we solve instances of the following problem: given a class of permutations K and a pattern mu, we ask for the number of permutations pi is an element of Av(n)(mu) whose sub-permutations in K satisfy certain additional constraints on their size. Second, we study the probability for a generic pattern to be contained in a random permutation pi of size n without being present in the sub-permutations of pi generated by the entry 1 <= k <= n. These theoretical results can be useful to define efficient randomized pattern-search procedures based on classical algorithms of pattern-recognition, while the general problem of pattern-search is NP-complete. (C) 2014 Elsevier B.V. All rights reserved.