### Abstract

Original language | English |
---|---|

Pages (from-to) | 1500-1507 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 9 |

Early online date | 6 Apr 2007 |

DOIs | |

Publication status | Published - May 2008 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Mathematics*,

*308*(9), 1500-1507. https://doi.org/10.1016/j.disc.2007.03.079

}

*Discrete Mathematics*, vol. 308, no. 9, pp. 1500-1507. https://doi.org/10.1016/j.disc.2007.03.079

**On uniquely k-determined permutations.** / Avgustinovich, Sergey; Kitaev, Sergey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On uniquely k-determined permutations

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

PY - 2008/5

Y1 - 2008/5

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 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.

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 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.

KW - de Bruijn graph

KW - consecutive pattern

KW - set of prohibitions

KW - permutations

KW - reconstruction

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/un-k-determ-perms.pdf

U2 - 10.1016/j.disc.2007.03.079

DO - 10.1016/j.disc.2007.03.079

M3 - Article

VL - 308

SP - 1500

EP - 1507

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 9

ER -