On uniquely k-determined permutations

Sergey Avgustinovich, Sergey Kitaev

Research output: Contribution to conferencePoster

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 ¯nite 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.
Original languageEnglish
Number of pages7
Publication statusPublished - Jul 2007
Event19th International Conference on Formal Power Series & Algebraic Combinatorics - Nankai University, Tianjin, China
Duration: 2 Jul 20076 Jul 2007

Conference

Conference19th International Conference on Formal Power Series & Algebraic Combinatorics
Abbreviated titleFPSAC'07
CountryChina
CityTianjin
Period2/07/076/07/07

Keywords

  • k-determined permutations
  • consecutive patterns
  • permutations
  • graphs

Fingerprint Dive into the research topics of 'On uniquely k-determined permutations'. Together they form a unique fingerprint.

  • Cite this

    Avgustinovich, S., & Kitaev, S. (2007). On uniquely k-determined permutations. Poster session presented at 19th International Conference on Formal Power Series & Algebraic Combinatorics, Tianjin, China.