<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Fibonacci Numbers, Reduced Decompositions, and 321=3412 Pattern Classes
Daniel Daly
Department of Mathematics, Southeast Missouri State University, One University Plaza, Cape Girardeau, Missouri 63701, USA
Annals of Combinatorics 14 (1) pp.53-64 Springer, 2010
AMS Subject Classification: 05
We provide a bijection between the permutations in Sn that avoid 3412 and contain exactly one 321 pattern with the permutations in Sn+1 that avoid 321 and contain exactly one 3412 pattern. The enumeration of these classes is obtained from their classification via reduced decompositions. The results are extended to involutions in the above pattern classes using reduced ecompositions reproducing a result of Egge.
Keywords: permutation patterns, reduced decompositions, combinatorics, Fibonacci numbers


1. Billey, S.C., Jockusch,W., Stanley, R.P.: Some combinatorial properties of Schubert polynomials. J. Algebraic Combin. 2(4), 345--–374 (1993)

2. Björner, A., Brenti, F.: Combinatorics of Coxeter groups. Graduate Texts in Mathematics Vol. 231, Springer, New York (2005)

3. Daly, D.: Reduced decompositions with one repetition and permutation pattern avoidance. Avaible at: http://www.math.du.edu/~ddaly.

4. Egge, E.S.: Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials. Adv. Appl. Math. 33(3), 451--–475 (2004)

5. Hammett, A., Pittel, B.: How often are two permutations comparable?. Trans. Amer. Math. Soc. 360(9), 4541--–4568 (2008)

6. Humphries, J.E.: Reection Groups and Coxeter Groups. Cambridge Studies in Advanced Mathematics Vol. 29, Cambridge University Press, Cambridge (1990)

7. Manivel, L.: Symmetric Functions, Schubert Polynomials and Degeneracy Loci. SMF/AMS Texts and Monographs Vol. 6, AMS, Providence, RI (2001)

8. Tenner, B.E.: Reduced decompositions and permutation patterns. J. Algebraic Combin. 24(3), 263--–284 (2006)

9. Tenner, B.E.: Pattern avoidance and the Bruhat order. J. Combin. Theory Ser. A 114(5), 888--–905 (2007)