Some equinumerous pattern-avoiding classes of permutations
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 o...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/356/pdf |
| _version_ | 1827323875347660800 |
|---|---|
| author | M. D. Atkinson |
| author_facet | M. D. Atkinson |
| author_sort | M. D. Atkinson |
| collection | DOAJ |
| description | 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 |
| first_indexed | 2024-04-25T01:59:41Z |
| format | Article |
| id | doaj.art-87196aa3ad3c47e0aa5a3aa43ed1f151 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:59:41Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-87196aa3ad3c47e0aa5a3aa43ed1f1512024-03-07T15:07:34ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01Vol. 710.46298/dmtcs.356356Some equinumerous pattern-avoiding classes of permutationsM. D. Atkinson0Department of Computer Science, Otago UniversitySuppose 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: 05A05https://dmtcs.episciences.org/356/pdfenumerationpermutationspatterns[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | M. D. Atkinson Some equinumerous pattern-avoiding classes of permutations Discrete Mathematics & Theoretical Computer Science enumeration permutations patterns [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Some equinumerous pattern-avoiding classes of permutations |
| title_full | Some equinumerous pattern-avoiding classes of permutations |
| title_fullStr | Some equinumerous pattern-avoiding classes of permutations |
| title_full_unstemmed | Some equinumerous pattern-avoiding classes of permutations |
| title_short | Some equinumerous pattern-avoiding classes of permutations |
| title_sort | some equinumerous pattern avoiding classes of permutations |
| topic | enumeration permutations patterns [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/356/pdf |
| work_keys_str_mv | AT mdatkinson someequinumerouspatternavoidingclassesofpermutations |