### Abstract

Language | English |
---|---|

Pages | 305-353 |

Number of pages | 49 |

Journal | Journal of Combinatorics |

Volume | 2 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2011 |

### Fingerprint

### Keywords

- pattern avoiding permutation
- enumerating permutations
- non-negative matrices

### Cite this

*Journal of Combinatorics*,

*2*(3), 305-353. https://doi.org/10.4310/JOC.2011.v2.n3.a1

}

*Journal of Combinatorics*, vol. 2, no. 3, pp. 305-353. https://doi.org/10.4310/JOC.2011.v2.n3.a1

**A spectral approach to consecutive pattern-avoiding permutations.** / Kitaev, Sergey; Ehrenborg, Richard; Perry, Peter.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A spectral approach to consecutive pattern-avoiding permutations

AU - Kitaev, Sergey

AU - Ehrenborg, Richard

AU - Perry, Peter

PY - 2011

Y1 - 2011

N2 - We consider the problem of enumerating permutations in the symmetric group on n elements which avoid a given set of consecutive patterns S, and in particular computing asymptotics as n tends to infinity. We develop a general method which solves this enumeration problem using the spectral theory of integral operators onL2([0,1]m), where the patterns in S have length m+1.Kre\u{\i}n and Rutman’s generalization of the Perron–Frobenius theory of non-negative matrices plays a central role. Our methods give detailed asymptotic expansions and allow for explicit computation of leading terms in many cases.As a corollary to our results,we settle a conjecture of Warlimont on asymptotics for the number of permutations avoiding a consecutive pattern.

AB - We consider the problem of enumerating permutations in the symmetric group on n elements which avoid a given set of consecutive patterns S, and in particular computing asymptotics as n tends to infinity. We develop a general method which solves this enumeration problem using the spectral theory of integral operators onL2([0,1]m), where the patterns in S have length m+1.Kre\u{\i}n and Rutman’s generalization of the Perron–Frobenius theory of non-negative matrices plays a central role. Our methods give detailed asymptotic expansions and allow for explicit computation of leading terms in many cases.As a corollary to our results,we settle a conjecture of Warlimont on asymptotics for the number of permutations avoiding a consecutive pattern.

KW - pattern avoiding permutation

KW - enumerating permutations

KW - non-negative matrices

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

U2 - 10.4310/JOC.2011.v2.n3.a1

DO - 10.4310/JOC.2011.v2.n3.a1

M3 - Article

VL - 2

SP - 305

EP - 353

JO - Journal of Combinatorics

T2 - Journal of Combinatorics

JF - Journal of Combinatorics

SN - 2156-3527

IS - 3

ER -