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

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.

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

Pages (from-to) | 3-10 |

Number of pages | 8 |

Journal | Journal of Automata, Languages and Combinatorics |

Volume | 16 |

Issue number | 1 |

Publication status | Published - 2011 |

### Fingerprint

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