On uniquely k-determined permutations

Sergey Avgustinovich, Sergey Kitaev

Research output: Contribution to journalArticle

8 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)1500-1507
Number of pages8
JournalDiscrete Mathematics
Volume308
Issue number9
Early online date6 Apr 2007
DOIs
Publication statusPublished - May 2008

Keywords

  • de Bruijn graph
  • consecutive pattern
  • set of prohibitions
  • permutations
  • reconstruction

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

  • Cite this