<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Pattern Avoidance in Alternating Sign Matrices
Robert Johansson and Svante Linusson
Department of Mathematics, KTH-Royal Institute of Technology, SE-100 44 Stockholm, Sweden
robjo381@student.liu.se, linusson@math.kth.se
Annals of Combinatorics 11 (3-4) p.471-480 September, 2007
AMS Subject Classification:05A15
Abstract:
We generalize the definition of a pattern from permutations to alternating sign matrices. The number of alternating sign matrices avoiding 132 is proved to be counted by the large Schröder numbers, 1, 2, 6, 22, 90, 394, …. We give a bijection between 132-avoiding alternating sign matrices and Schröder paths, which gives a refined enumeration. We also show that the 132-, 123-avoiding alternating sign matrices are counted by every second Fibonacci number.
Keywords: alternating sign matrix, pattern avoidance, restricted permutations, Schröder numbers

References:

1. D.M. Bressoud, Proofs and Confirmations: The Story of the Alternating-Sign Matrix Conjecture, Cambridge University Press, Cambridge, 1999.

2. A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (1) (2004) 153--160.

3. Z. Füredi and P. Hajnal, Davenport-Schinzel theory of matrices, Discrete Math. 103 (3) (1992) 233--251.

4. E.S. Egge and T. Mansour, Permutations which avoid 1243 and 2143, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 9 (2) (2003) #R7.

5. E.S. Egge, Restricted signed permutations counted by the Schröder numbers, Discrete Math. 306 (6) (2006) 552--563.

6. R.P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge University Press, Cambridge, 1999.

7. N.J.A Sloane, The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences/.

8. D. Zeilberger, Proof of the alternating sign matrix conjecture, Electron. J. Combin. 3 (2) (1996) #R13.

9. R. Johansson, Pattern Avoidance in Alternating Sign Matrices, Linköping University Electronic Press, Linköpings, 2006. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-7936 .