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,…,p}∪{m-q+1, m-q+2, …,m} is considered. A recurrence relation to enumerate the permutations of X(...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/62 |
| _version_ | 1818491476907130880 |
|---|---|
| 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,…,p}∪{m-q+1, m-q+2, …,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. 2000 MATHEMATICS SUBJECT CLASSIFICATION: 05A05 |
| first_indexed | 2024-12-10T17:31:20Z |
| format | Article |
| id | doaj.art-118e4757910a4f0db770fb787bef2c92 |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-12-10T17:31:20Z |
| publishDate | 2005-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-118e4757910a4f0db770fb787bef2c922022-12-22T01:39:40ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80502005-12-0171Some equinumerous pattern-avoiding classes of permutationsM. D. AtkinsonSuppose 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,…,p}∪{m-q+1, m-q+2, …,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. 2000 MATHEMATICS SUBJECT CLASSIFICATION: 05A05http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/62 |
| spellingShingle | M. D. Atkinson Some equinumerous pattern-avoiding classes of permutations Discrete Mathematics & Theoretical Computer Science |
| 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 |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/62 |
| work_keys_str_mv | AT mdatkinson someequinumerouspatternavoidingclassesofpermutations |