On uniquely k-determined permutations

Sergey Avgustinovich, Sergey Kitaev

Research output: Contribution to conferencePosterpeer-review


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


Conference19th International Conference on Formal Power Series & Algebraic Combinatorics
Abbreviated titleFPSAC'07


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


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

Cite this