On uniquely k-determined permutations

Avgustinovich, Sergey and Kitaev, Sergey (2008) On uniquely k-determined permutations. Discrete Mathematics, 308 (9). pp. 1500-1507. ISSN 0012-365X (https://doi.org/10.1016/j.disc.2007.03.079)

Full text not available in this repository.Request a copy

Abstract

Motivated by a new point of view to study occurrences of consecutive patterns in permutations, we introduce the notion of uniquely k-determined permutations. We give two criteria for a permutation to be uniquely k-determined: one in terms of the distance between two consecutive elements in a permutation, and the other one in terms of directed hamiltonian paths in the certain graphs called path-schemes. Moreover, we describe a finite set of prohibitions that gives the set of uniquely k-determined permutations. Those prohibitions make the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.

CORE (COnnecting REpositories)