On uniquely k-determined permutations

Sergey Avgustinovich; Sergey Kitaev

On uniquely k-determined permutations

Sergey Avgustinovich, Sergey Kitaev

Research output: Contribution to conference › Poster › peer-review

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 language	English
Number of pages	7
Publication status	Published - Jul 2007
Event	19th International Conference on Formal Power Series & Algebraic Combinatorics - Nankai University, Tianjin, China Duration: 2 Jul 2007 → 6 Jul 2007

Conference

Conference	19th International Conference on Formal Power Series & Algebraic Combinatorics
Abbreviated title	FPSAC'07
Country/Territory	China
City	Tianjin
Period	2/07/07 → 6/07/07

Keywords

k-determined permutations
consecutive patterns
permutations
graphs

Cite this

@conference{585e5d7a6eab4c96a3230bc6aaf38aac,

title = "On uniquely k-determined permutations",

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. Thoseprohibitions make the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.",

keywords = "k-determined permutations, consecutive patterns, permutations, graphs",

author = "Sergey Avgustinovich and Sergey Kitaev",

year = "2007",

month = jul,

language = "English",

note = "19th International Conference on Formal Power Series & Algebraic Combinatorics, FPSAC'07 ; Conference date: 02-07-2007 Through 06-07-2007",

}

TY - CONF

T1 - On uniquely k-determined permutations

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

PY - 2007/7

Y1 - 2007/7

N2 - 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. Thoseprohibitions make the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.

AB - 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. Thoseprohibitions make the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.

KW - k-determined permutations

KW - consecutive patterns

KW - permutations

KW - graphs

UR - http://www.fpsac.org/FPSAC07/SITE07/conpap.htm

M3 - Poster

T2 - 19th International Conference on Formal Power Series & Algebraic Combinatorics

Y2 - 2 July 2007 through 6 July 2007

ER -

On uniquely k-determined permutations

Abstract

Conference

Keywords

Other files and links

Fingerprint

Cite this