Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

Strathprints

Pattern avoidance in partial permutations

Claesson, A. and Jelinek, V. and Jelinkova, E. and Kitaev, S. (2011) Pattern avoidance in partial permutations. The Electronic Journal of Combinatorics, 18 (1). ISSN 1077-8926

[img]
Preview
 PDF
partial_permutations.pdf - Accepted Author Manuscript
Download (432kB) | Preview

Abstract

Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A partial permutation of length n with k holes is a sequence of symbols $\pi = \pi_1\pi_2 ... \pi_n$ in which each of the symbols from the set {1,2,...,n-k} appears exactly once, while the remaining k symbols of $\pi$ are "holes". We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length k correspond to a Wilf-type equivalence class with respect to partial permutations with (k-2) holes. Lastly, we enumerate the partial permutations of length n with k holes avoiding a given pattern of length at most four, for each n >= k >= 1.

Item type: Article
ID code: 40421
Keywords: Wilf-equivalence, generating function, pattern avoidance, partial permutation, Stanley-Wilf conjecture, bijection, partial words, fillings, Baxter permutation, Electronic computers. Computer science, Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Depositing user: Pure Administrator
Date deposited: 17 Jul 2012 11:54
Last modified: 21 Sep 2017 11:02
Related URLs:
URI: https://strathprints.strath.ac.uk/id/eprint/40421
Export data:
CORE (COnnecting REpositories)