On square-free permutations

Sergey Avgustinovich, Sergey Kitaev, Artem Pyatkin, Alexander Valyuzhenich

Research output: Contribution to journalArticle

Abstract

A permutation is square-free if it does not contain two consecutive factors of length more than one that coincide in the reduced form (as patterns). We prove that the number of square-free permutations of length n is nn(1􀀀"n) where "n ! 0 when n ! 1. A permutation of length n is crucial with respect to squares if it avoids squares but any extension of it to the right, to a permutation of length n+1, contains a square. A permutation is maximal with respect to squares if both the permutation and its reverse are crucial with respect
to squares. We prove that there exist crucial permutations with respect to squares of any length at least 7, and there exist maximal permutations with respect to squares of odd lengths 8k+1; 8k+5; 8k+7 for k 1.
LanguageEnglish
Pages3-10
Number of pages8
JournalJournal of Automata, Languages and Combinatorics
Volume16
Issue number1
Publication statusPublished - 2011

Fingerprint

Square free
Permutation
Consecutive
Reverse
Odd

Keywords

  • square freeness
  • consecutive pattern
  • enumeration
  • crucial word
  • maximal word
  • permutation

Cite this

Avgustinovich, S., Kitaev, S., Pyatkin, A., & Valyuzhenich, A. (2011). On square-free permutations. Journal of Automata, Languages and Combinatorics, 16(1), 3-10.
Avgustinovich, Sergey ; Kitaev, Sergey ; Pyatkin, Artem ; Valyuzhenich, Alexander. / On square-free permutations. In: Journal of Automata, Languages and Combinatorics. 2011 ; Vol. 16, No. 1. pp. 3-10.
@article{5b563bd196634dbebb00e2622d6e6aac,
title = "On square-free permutations",
abstract = "A permutation is square-free if it does not contain two consecutive factors of length more than one that coincide in the reduced form (as patterns). We prove that the number of square-free permutations of length n is nn(1􀀀{"}n) where {"}n ! 0 when n ! 1. A permutation of length n is crucial with respect to squares if it avoids squares but any extension of it to the right, to a permutation of length n+1, contains a square. A permutation is maximal with respect to squares if both the permutation and its reverse are crucial with respectto squares. We prove that there exist crucial permutations with respect to squares of any length at least 7, and there exist maximal permutations with respect to squares of odd lengths 8k+1; 8k+5; 8k+7 for k 1.",
keywords = "square freeness, consecutive pattern, enumeration, crucial word, maximal word, permutation",
author = "Sergey Avgustinovich and Sergey Kitaev and Artem Pyatkin and Alexander Valyuzhenich",
year = "2011",
language = "English",
volume = "16",
pages = "3--10",
journal = "Journal of Automata, Languages and Combinatorics",
issn = "1430-189X",
number = "1",

}

Avgustinovich, S, Kitaev, S, Pyatkin, A & Valyuzhenich, A 2011, 'On square-free permutations' Journal of Automata, Languages and Combinatorics, vol. 16, no. 1, pp. 3-10.

On square-free permutations. / Avgustinovich, Sergey; Kitaev, Sergey; Pyatkin, Artem; Valyuzhenich, Alexander.

In: Journal of Automata, Languages and Combinatorics, Vol. 16, No. 1, 2011, p. 3-10.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On square-free permutations

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

AU - Pyatkin, Artem

AU - Valyuzhenich, Alexander

PY - 2011

Y1 - 2011

N2 - A permutation is square-free if it does not contain two consecutive factors of length more than one that coincide in the reduced form (as patterns). We prove that the number of square-free permutations of length n is nn(1􀀀"n) where "n ! 0 when n ! 1. A permutation of length n is crucial with respect to squares if it avoids squares but any extension of it to the right, to a permutation of length n+1, contains a square. A permutation is maximal with respect to squares if both the permutation and its reverse are crucial with respectto squares. We prove that there exist crucial permutations with respect to squares of any length at least 7, and there exist maximal permutations with respect to squares of odd lengths 8k+1; 8k+5; 8k+7 for k 1.

AB - A permutation is square-free if it does not contain two consecutive factors of length more than one that coincide in the reduced form (as patterns). We prove that the number of square-free permutations of length n is nn(1􀀀"n) where "n ! 0 when n ! 1. A permutation of length n is crucial with respect to squares if it avoids squares but any extension of it to the right, to a permutation of length n+1, contains a square. A permutation is maximal with respect to squares if both the permutation and its reverse are crucial with respectto squares. We prove that there exist crucial permutations with respect to squares of any length at least 7, and there exist maximal permutations with respect to squares of odd lengths 8k+1; 8k+5; 8k+7 for k 1.

KW - square freeness

KW - consecutive pattern

KW - enumeration

KW - crucial word

KW - maximal word

KW - permutation

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/square-free-perms2.pdf

M3 - Article

VL - 16

SP - 3

EP - 10

JO - Journal of Automata, Languages and Combinatorics

T2 - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

SN - 1430-189X

IS - 1

ER -

Avgustinovich S, Kitaev S, Pyatkin A, Valyuzhenich A. On square-free permutations. Journal of Automata, Languages and Combinatorics. 2011;16(1):3-10.