Change search
ReferencesLink to record
Permanent link

Direct link
Wilf-equivalence for singleton classes
Stockholm University, Faculty of Science, Department of Mathematics.
2007 (English)In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 38, no 2, 133-148 p.Article in journal (Refereed) Published
Abstract [en]

Write p(1)p(2)(...)pm for the permutation matrix (delta p(i) j)(m x m). Let S-n(M) be the set of n x n permutation matrices which do not contain the m x m permutation matrix M as a submatrix. In [R. Simion, F.W. Schmidt, Restricted permutations, European J. Combin. 6 (1985) 383-406] Simion and Schmidt show bijectively that vertical bar S-n (123)vertical bar = vertical bar S-n (213)vertical bar. In the present work, we give a bi jection from S-n ( p(m)) to S-n (t...21 p(t+1)...p(m)). This result was established for t = 2 in [J. West, Permutations with forbidden subsequences and stack-sortable permutations, PhD thesis, MIT, Cambridge, MA, 1990] and for t = 3 in [E. Babson, J. West, The permutations 123p(4)... p(t) and 321 p(4)...p(t) are Wilf-equivalent, Graphs Combin. 16 (2001) 373-3801. Moreover, if we think of n x n permutation matrices as transversals of the n by n square diagram, then we generalise this result to transversals of Young diagrams.

Place, publisher, year, edition, pages
2007. Vol. 38, no 2, 133-148 p.
Keyword [en]
permutations, permutation matrices, forbidden subsequences, bijection, Wilf-equivalence
National Category
URN: urn:nbn:se:su:diva-57103DOI: 10.1016/j.aam.2004.11.006ISI: 000244217900001OAI: diva2:415740
authorCount :3Available from: 2011-05-09 Created: 2011-05-03 Last updated: 2011-05-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Backelin, Jörgen
By organisation
Department of Mathematics
In the same journal
Advances in Applied Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 31 hits
ReferencesLink to record
Permanent link

Direct link