M. D. Atkinson - Some equinumerous pattern-avoiding classes of permutations

dmtcs:356 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 - https://doi.org/10.46298/dmtcs.356
Some equinumerous pattern-avoiding classes of permutationsArticle

Authors: M. D. Atkinson 1

  • 1 Department of Computer Science, Otago University

Suppose that p,q,r,s are non-negative integers with m=p+q+r+s. The class X(p,q,r,s) of permutations that contain no pattern of the form α β γ where |α |=r, |γ |=s and β is any arrangement of \1,2,\ldots,p\∪ \m-q+1, m-q+2, \ldots,m\ is considered. A recurrence relation to enumerate the permutations of X(p,q,r,s) is established. The method of proof also shows that X(p,q,r,s)=X(p,q,1,0)X(1,0,r,s) in the sense of permutational composition.\par 2000 MATHEMATICS SUBJECT CLASSIFICATION: 05A05

Volume: Vol. 7
Published on: January 1, 2005
Imported on: March 26, 2015
Keywords: enumeration,Permutations,patterns,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 290 times.
This article's PDF has been downloaded 207 times.