Restricted patience sorting and barred pattern avoidance  pp. 233-258

Restricted patience sorting and barred pattern avoidance

By Alexander Burstein and Isaiah Lankham

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert and M. D. Atkinson . Simple permutations and pattern restricted permutations. Discrete Math., 300(1-3):1–15, 2005.
[2] M. H. Albert , M. D. Atkinson , and R. Brignall . Permutation classes of polynomial growth. Ann. Comb., 11(3–4):249–264, 2007.
[3] M. H. Albert , M. Elder , A. Rechnitzer , P. Westcott , and M. Zabrocki . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.
[4] M. H. Albert and S. Linton . Growing at a perfect speed. Combin. Probab. Comput., 18:301–308, 2009.
[5] M. H. Albert , S. Linton , and N. Ruškuc . The insertion encoding of permutations. Electron. J. Combin., 12(1):Research paper 47, 31 pp., 2005.
[6] V. E. Alekseev . Range of values of entropy of hereditary classes of graphs. Diskret. Mat., 4(2):148–157, 1992.
[7] J.-P. Allouche and J. Shallit . Automatic sequences. Cambridge University Press, Cambridge, 2003.
[8] G. E. Andrews . The theory of partitions. Addison-Wesley Publishing Co., Reading, Mass.Mass.-London-Amsterdam, 1976.
[9] R. Arratia . On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6:Note, N1, 4 pp., 1999.
[10] M. D. Atkinson , M. M. Murphy , and N. Ruškuc . Partially well-ordered closed sets of permutations. Order, 19(2):101–113, 2002.
[11] J. Balogh and B. Bollobás . Hereditary properties of words. Theor. Inform. Appl., 39(1):49–65, 2005.
[12] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of ordered graphs. In M. Klazar , J. Kratochvíl , M. Loebl , J. Matoušek , R. Thomas , and P. Valtr , editors, Topics in discrete mathematics, volume 26 of Algorithms Combin., pages 179–213. Springer, Berlin, 2006.
[13] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of partitions, ordered graphs and ordered hypergraphs. European J. Combin., 27(8):1263–1281, 2006.
[14] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of combinatorial structures: posets and oriented graphs. J. Graph Theory, 56(4):311–332, 2007.
[15] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of tournaments. Electron. J. Combin., 14(1):Research Paper 60, 25 pp., 2007.
[16] J. Balogh , B. Bollobás , M. Saks , and V. T. Sós . The unlabeled speed of a hereditary graph property. Preprint.
[17] J. Balogh , B. Bollobás , and M. Simonovits . The number of graphs without forbidden subgraphs. J. Combin. Theory Ser. B, 91(1):1–24, 2004.
[18] J. Balogh , B. Bollobás , and D. Weinreich . The speed of hereditary properties of graphs. J. Combin. Theory Ser. B, 79(2):131–156, 2000.
[19] J. Balogh , B. Bollobás , and D. Weinreich . The penultimate rate of growth for graph properties. European J. Combin., 22(3):277–289, 2001.
[20] J. Balogh , B. Bollobás , and D. Weinreich . Measures on monotone properties of graphs. Discrete Appl. Math., 116(1-2):17–36, 2002.
[21] J. Balogh , B. Bollobás , and D. Weinreich . A jump to the Bell number for hereditary graph properties. J. Combin. Theory Ser. B, 95(1):29–48, 2005.
[22] E. Barcucci , A. Del Lungo , A. Frosini , and S. Rinaldi . From rational functions to regular languages. In Formal power series and algebraic combinatorics (Moscow, 2000), pages 633–644. Springer, Berlin, 2000.
[23] A. Barvinok . The complexity of generating functions for integer points in polyhedra and beyond. In International Congress of Mathematicians. Vol. III, pages 763–787. Eur. Math. Soc., Zürich, 2006.
[24] A. Barvinok and K. Woods . Short rational generating functions for lattice point problems. J. Amer. Math. Soc., 16(4):957–979, 2003.
[25] M. Beck and S. Robins . Computing the continuous discretely. Undergraduate Texts in Mathematics. Springer, New York, 2007.
[26] O. Bernardi , M. Noy , and D. Welsh . On the growth rate of minor-closed classes of graphs. arXiv:06710.2995 [math.CO].
[27] C. Blatter and E. Specker . Le nombre de structures finies d'une théorie à caractère fini. Sci. Math. Fonds Nat. Rec. Sci. Bruxelles, pages 41–44, 1981.
[28] C. Blatter and E. Specker . Modular periodicity of combinatorial sequences. Abstract Amer. Math. Soc., 4:313, 1983.
[29] C. Blatter and E. Specker . Recurrence relations for the number of labeled structures on a finite set. In E. Börger , G. Hasenjaeger , and D. Rödding , editors, Logic and Machines, pages 43–61, 1983.
[30] B. Bollobás . Hereditary and monotone properties of combinatorial structures. In A. Hilton and J. Talbot , editors, Surveys in Combinatorics 2007, number 346 in London Mathematical Society Lecture Note Series, pages 1–39. Cambridge University Press, 2007.
[31] B. Bollobás and A. Thomason . Projections of bodies and hereditary properties of hypergraphs. Bull. London Math. Soc., 27(5):417–424, 1995.
[32] B. Bollobás and A. Thomason . Hereditary and monotone properties of graphs. In The mathematics of Paul Erdős, II, volume 14 of Algorithms Combin., pages 70–78. Springer, Berlin, 1997.
[33] M. Bóna . Permutations avoiding certain patterns: the case of length 4 and some generalizations. Discrete Math., 175(1-3):55–67, 1997.
[34] M. Bóna . Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
[35] Y. Boudabbous and M. Pouzet . The morphology of infinite tournaments. application to the growth of their profile. arXiv:0801.4069 [math.CO].
[36] M. Bousquet-Mélou . Algebraic generating functions in enumerative combinatorics and context-free languages. In STACS 2005, volume 3404 of Lecture Notes in Comput. Sci., pages 18–35. Springer, Berlin, 2005.
[37] M. Bousquet-Mélou . Rational and algebraic series in combinatorial enumeration. In International Congress of Mathematicians. Vol. III, pages 789–826. Eur. Math. Soc., Zürich, 2006.
[38] M. R. Bridson and R. H. Gilman . Context-free languages of sub-exponential growth. J. Comput. System Sci., 64(2):308–310, 2002.
[39] R. Brignall . A survey of simple permutations. In this volume, 41–65.
[40] R. Brignall , S. Huczynska , and V. Vatter . Simple permutations and algebraic generating functions. J. Combin. Theory Ser. A, 115(3):423–441, 2008.
[41] R. Brignall , N. Ruškuc , and V. Vatter . Simple permutations: decidability and unavoidable substructures. Theoret. Comput. Sci., 391(1–2):150–163, 2008.
[42] S. N. Burris . Number theoretic density and logical limit laws, volume 86 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.
[43] P. J. Cameron . Oligomorphic permutation groups, volume 152 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1990.
[44] P. J. Cameron . Some counting problems related to permutation groups. Discrete Math., 225(1-3):77–92, 2000.
[45] T. Ceccherini-Silberstein . Growth and ergodicity of context-free languages. II. The linear case. Trans. Amer. Math. Soc., 359(2):605–618, 2007.
[46] T. Ceccherini-Silberstein , A. Machi , and F. Scarabotti . On the entropy of regular languages. Theoret. Comput. Sci., 307(1):93–102, 2003.
[47] T. Ceccherini-Silberstein and W. Woess . Growth and ergodicity of context-free languages. Trans. Amer. Math. Soc., 354(11):4597–4625, 2002.
[48] T. Ceccherini-Silberstein and W. Woess . Growth-sensitivity of context-free languages. Theoret. Comput. Sci., 307(1):103–116, 2003.
[49] N. Chomsky and M. P. Schützenberger . The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963.
[50] L. Comtet . Advanced combinatorics. D. Reidel Publishing Co., Dordrecht, 1974.
[51] F. D'Alessandro , B. Intrigila , and S. Varricchio . On the structure of the counting function of sparse context-free languages. Theoret. Comput. Sci., 356(1-2):104–117, 2006.
[52] P. de la Harpe . Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000.
[53] E. Deutsch and B. E. Sagan . Congruences for Catalan and Motzkin numbers and related sequences. J. Number Theory, 117(1):191–215, 2006.
[54] V. Domocoş . Minimal coverings of uniform hypergraphs and P-recursiveness. Discrete Math., 159(1-3):265–271, 1996.
[55] H.-D. Ebbinghaus and J. Flum . Finite model theory. Springer Monographs in Mathematics. Springer-Verlag, Berlin, enlarged edition, 2006.
[56] E. Ehrhart . Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris, 254:616–618, 1962.
[57] M. Elder and V. Vatter . Problems and conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7–11, 2005. arXiv:0505504 [math.CO].
[58] S.-P. Eu , S.-C. Liu , and Y.-N. Yeh . Catalan and Motzkin numbers modulo 4 and 8. European J. Combin., 29(6):1449–1466, 2008.
[59] E. Fischer . The Specker-Blatter theorem does not hold for quaternary relations. J. Combin. Theory Ser. A, 103(1):121–136, 2003.
[60] E. Fischer and J. A. Makowsky . The Specker-Blatter theorem revisited. In Computing and combinatorics, volume 2697 of Lecture Notes in Comput. Sci., pages 90–101. Springer, Berlin, 2003.
[61] E. Fischer and J. A. Makowsky . On spectra of sentences of monadic second order logic with counting. J. Symbolic Logic, 69(3):617–640, 2004.
[62] P. Flajolet . Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci., 49(2-3):283–309, 1987.
[63] P. Flajolet and R. Sedgewick . Analytic combinatorics. Cambridge University Press, Cambridge, 2009.
[64] R. Fraïssé . Sur quelques classifications des systèmes de relations. PhD thesis, Université de Paris, 1953.
[65] R. Fraïssé . Sur l'extension aux relations de quelques propriétés des ordres. Ann. Sci. Ecole Norm. Sup. (3), 71:363–388, 1954.
[66] R. Fraïssé . Theory of relations, volume 145 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, revised edition, 2000.
[67] I. M. Gessel . Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A, 53(2):257–285, 1990.
[68] I. P. Goulden and D. M. Jackson . Labelled graphs with small vertex degrees and P-recursiveness. SIAM J. Algebraic Discrete Methods, 7(1):60–66, 1986.
[69] R. Grigorchuk and I. Pak . Groups of intermediate growth: an introduction. Enseign. Math. (2), 54(3-4):251–272, 2008.
[70] R. I. Grigorchuk . On the Milnor problem of group growth. Dokl. Akad. Nauk SSSR, 271(1):30–33, 1983.
[71] G. Higman . Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326–336, 1952.
[72] S. Huczynska and V. Vatter . Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin., 13:Research paper 54, 14 pp., 2006.
[73] R. Incitti . The growth function of context-free languages. Theoret. Comput. Sci., 255(1-2):601–605, 2001.
[74] Y. Ishigami . The number of hypergraphs and colored hypergraphs with hereditary properties. arXiv:0712.0425v1 [math.CO].
[75] V. Jelínek and M. Klazar . Generalizations of Khovanski's theorems on the growth of sumsets in abelian semigroups. Adv. in Appl. Math., 41(1):115–132, 2008.
[76] T. Kaiser and M. Klazar . On growth rates of closed permutation classes. Electron. J. Combin., 9(2):Research paper 10, 20 pp., 2003.
[77] M. Klazar . Counting pattern-free set partitions. I. A generalization of Stirling numbers of the second kind. European J. Combin., 21(3):367–378, 2000.
[78] M. Klazar . Counting pattern-free set partitions. II. Noncrossing and other hypergraphs. Electron. J. Combin., 7:Research Paper 34, 25 pp., 2000.
[79] M. Klazar . Extremal problems for ordered (hyper) graphs: applications of Davenport-Schinzel sequences. European J. Combin., 25(1):125–140, 2004.
[80] M. Klazar . On the least exponential growth admitting uncountably many closed permutation classes. Theoret. Comput. Sci., 321(2-3):271–281, 2004.
[81] M. Klazar . On growth rates of permutations, set partitions, ordered graphs and other objects. Electron. J. Combin., 15(1):Research paper 75, 22 pp., 2008.
[82] W. F. Lunnon , P. A. B. Pleasants , and N. M. Stephens . Arithmetic properties of Bell numbers to a composite modulus. I. Acta Arith., 35(1):1–16, 1979.
[83] I. G. Macdonald . The volume of a lattice polyhedron. Proc. Cambridge Philos. Soc., 59:719–726, 1963.
[84] I. G. Macdonald . Polynomials associated with finite cell-complexes. J. London Math. Soc. (2), 4:181–192, 1971.
[85] H. D. Macpherson . Growth rates in infinite graphs and permutation groups. Proc. London Math. Soc. (3), 51(2):285–294, 1985.
[86] H. D. Macpherson . Orbits of infinite permutation groups. Proc. London Math. Soc. (3), 51(2):246–284, 1985.
[87] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[88] D. Marinov and R. Radoičić . Counting 1324-avoiding permutations. Electron. J. Combin., 9(2):Research paper 13, 9 pp., 2003.
[89] C. McDiarmid , A. Steger , and D. J. A. Welsh . Random graphs from planar and other addable classes. In Topics in discrete mathematics, volume 26 of Algorithms Combin., pages 231–246. Springer, Berlin, 2006.
[90] M. Mishna . Automatic enumeration of regular objects. J. Integer Seq., 10(5):Article 07.5.5, 18 pp., 2007.
[91] M. J. Mishna . Une approche holonome à la combinatoire algébrique. PhD thesis, Univ. Québec à Montréal, 2003.
[92] M. Morse and G. A. Hedlund . Symbolic Dynamics. Amer. J. Math., 60(4):815–866, 1938.
[93] S. Norine , P. Seymour , R. Thomas , and P. Wollan . Proper minor-closed families are small. J. Combin. Theory Ser. B, 96(5):754–757, 2006.
[94] C. H. Papadimitriou . Computational complexity. Addison-Wesley Publishing Company, Reading, MA, 1994.
[95] M. Pouzet . Sur la théorie des relations. PhD thesis, Université Claude-Bernard, Lyon 1, 1978.
[96] M. Pouzet . Application de la notion de relation presque-enchaînable au dénombrement des restrictions finies d'une relation. Z. Math. Logik Grundlag. Math., 27(4):289–332, 1981.
[97] M. Pouzet . The profile of relations. Glob. J. Pure Appl. Math., 2(3):237–272, 2006.
[98] M. Pouzet and N. M. Thiéry . Some relational structures with polynomial growth and their associated algebras. arXiv:0601256v1 [math.CO].
[99] C. R. Read . Enumeration. In L. W. Beineke and R. J. Wilson , editors, Graph connections, pages 13–33, New York, 1997. The Clarendon Press Oxford University Press.
[100] N. Robertson and P. Seymour . Graph minors i–xx. J. Combinatorial Theory Ser. B, 1983–2004.
[101] A. Salomaa . Formal languages. Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1973. ACM Monograph Series.
[102] A. Salomaa and M. Soittola . Automata-theoretic aspects of formal power series. Springer-Verlag, New York, 1978. Texts and Monographs in Computer Science.
[103] E. R. Scheinerman and J. Zito . On the size of hereditary classes of graphs. J. Combin. Theory Ser. B, 61(1):16–39, 1994.
[104] S. Shelah . Spectra of monadic second order sentences. Sci. Math. Jpn., 59(2):351–355, 2004.
[105] S. Shelah and M. Doron . Bounded m-ary patch-width are equivalent for m > 2. arXiv:math/0607375v1 [math.LO].
[106] R. Simion . Noncrossing partitions. Discrete Math., 217(1-3):367–409, 2000. Formal power series and algebraic combinatorics (Vienna, 1997).
[107] E. Specker . Application of logic and combinatorics to enumeration problems. In Trends in theoretical computer science (Udine, 1984), volume 12 of Principles Comput. Sci. Ser., pages 143–169. Computer Sci. Press, Rockville, MD, 1988.
[108] E. Specker . Modular counting and substitution of structures. Combin. Probab. Comput., 14(1-2):203–210, 2005.
[109] J. Spencer . The strange logic of random graphs, volume 22 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2001.
[110] R. P. Stanley . Solution to problem E2546. Amer. Math. Monthly, 83(10):813–814, 1976.
[111] R. P. Stanley . Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997.
[112] R. P. Stanley . Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.
[113] V. I. Trofimov . Growth functions of some classes of languages. Cybernetics, 17:727–731, 1982. translated from Kibernetika (1981), 9–12.
[114] V. Vatter . Permutation classes of every growth rate above 2.48188. Mathematika, 56:182–192, 2010.
[115] V. Vatter . Small permutation classes. arXiv:0712.4006v2 [math.CO].
[116] V. Vatter . Enumeration schemes for restricted permutations. Combin. Probab. Comput., 17:137–159, 2008.
[117] H. S. Wilf . What is an answer? Amer. Math. Monthly, 89(5):289–292, 1982.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert and M. D. Atkinson . Simple permutations and pattern restricted permutations. Discrete Math., 300(1-3):1–15, 2005.
[2] M. H. Albert , M. D. Atkinson , and M. Klazar . The enumeration of simple permutations. J. Integer Seq., 6(4):Article 03.4.4, 18 pp., 2003.
[3] M. D. Atkinson . Restricted permutations. Discrete Math., 195(1-3):27–38, 1999.
[4] M. D. Atkinson , N. Ruškuc , and R. Smith . Substitution-closed pattern classes. Preprint.
[5] M. D. Atkinson and T. Stitt . Restricted permutations and the wreath product. Discrete Math., 259(1-3):19–36, 2002.
[6] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of partitions, ordered graphs and ordered hypergraphs. European J. Combin., 27(8):1263–1281, 2006.
[7] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of combinatorial structures: posets and oriented graphs. J. Graph Theory, 56(4):311–332, 2007.
[8] J. Balogh , B. Bollobás , and R. Morris . Hereditary properties of tournaments. Electron. J. Combin., 14(1):Research Paper 60, 25 pp., 2007.
[9] E. A. Bender and L. B. Richmond . An asymptotic expansion for the coefficients of some power series. II. Lagrange inversion. Discrete Math., 50(2–3):135–141, 1984.
[10] A. Bergeron , C. Chauve , F. de Montgolfier , and M. Raffinot . Computing common intervals of κ permutations, with applications to modular decomposition of graphs. In Algorithms – ESA 2005, volume 3669/2005 of Lecture Notes in Computer Science, pages 779–790. Springer Berlin, Heidelberg, 2005.
[11] B. Bollobás . Hereditary properties of graphs: asymptotic enumeration, global structure, and colouring. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), Extra Vol. III, pages 333–342, 1998.
[12] B. Bollobás . Hereditary and monotone properties of combinatorial structures. In A. Hilton and J. Talbot , editors, Surveys in Combinatorics 2007, number 346 in London Mathematical Society Lecture Note Series, pages 1–39. Cambridge University Press, 2007.
[13] M. Bóna . The number of permutations with exactly r 132-subsequences is P-recursive in the size! Adv. in Appl. Math., 18(4):510–522, 1997.
[14] P. Bose , J. F. Buss , and A. Lubiw . Pattern matching for permutations. Inform. Process. Lett., 65(5):277–283, 1998.
[15] M. Bouvel and D. Rossin . Longest common pattern between two permutations. arXiv:math/0611679v1 [math.CO].
[16] R. Brignall , S. Huczynska , and V. Vatter . Decomposing simple permutations, with enumerative consequences. Combinatorica, 28:385–400, 2008.
[17] R. Brignall , S. Huczynska , and V. Vatter . Simple permutations and algebraic generating functions. J. Combin. Theory Ser. A, 115(3):423–441, 2008.
[18] R. Brignall , N. Ruškuc , and V. Vatter . Simple extensions of combinatorial structures. arXiv:math/0911.4378v1 [math.CO].
[19] R. Brignall , N. Ruškuc , and V. Vatter . Simple permutations: decidability and unavoidable substructures. Theoret. Comput. Sci., 391(1–2):150–163, 2008.
[20] L. Comtet . Advanced combinatorics. D. Reidel Publishing Co., Dordrecht, 1974.
[21] S. Corteel , G. Louchard , and R. Pemantle . Common intervals of permutations. Discrete Math. Theor. Comput. Sci., 8(1):189–214, 2006.
[22] A. Cournier and M. Habib . A new linear algorithm for modular decomposition. In Trees in algebra and programming–CAAP '94 (Edinburgh, 1994), volume 787 of Lecture Notes in Comput. Sci., pages 68–84. Springer, Berlin, 1994.
[23] P. Erdős , E. Fried , A. Hajnal , and E. C. Milner . Some remarks on simple tournaments. Algebra Universalis, 2:238–245, 1972.
[24] P. Erdős , A. Hajnal , and E. C. Milner . Simple one-point extensions of tournaments. Mathematika, 19:57–62, 1972.
[25] R. Fraïssé . On a decomposition of relations which generalizes the sum of ordering relations. Bull. Amer. Math. Soc., 59:389, 1953.
[26] T. Gallai . Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar, 18:25–66, 1967.
[27] T. Gallai . A translation of T. Gallai's paper: “Transitiv orientierbare Graphen”, pages 25–66. Wiley-Intersci. Ser. Discrete Math. Optim. Wiley, Chichester, 2001.
[28] V. Giakoumakis . On the closure of graphs under substitution. Discrete Math., 177(1-3):83–97, 1997.
[29] J. Gustedt . Finiteness theorems for graphs and posets obtained by compositions. Order, 15:203–220, 1999.
[30] G. Higman . Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3), 2:326–336, 1952.
[31] I. Kaplansky . The asymptotic distribution of runs of consecutive elements. Ann. Math. Statistics, 16:200–203, 1945.
[32] T. Mansour and A. Vainshtein . Counting occurrences of 132 in a permutation. Adv. in Appl. Math., 28(2):185–195, 2002.
[33] R. M. McConnell and J. P. Spinrad . Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), pages 536–545, New York, 1994. ACM.
[34] R. H. Möhring . On the distribution of locally undecomposable relations and independence systems. In Colloquium on Mathematical Methods of Operations Research (Aachen, 1980), volume 42 of Methods Oper. Res., pages 33–48. Athenäum/Hain/Hanstein, Königstein/Ts., 1981.
[35] R. H. Möhring . Algorithmic aspects of the substitution decomposition in optimization over relations, sets systems and Boolean functions. Ann. Oper. Res., 4(1-4):195–225, 1985.
[36] R. H. Möhring and F. J. Radermacher . Substitution decomposition for discrete structures and connections with combinatorial optimization. In Algebraic and combinatorial methods in operations research, volume 95 of North-Holland Math. Stud., pages 257–355. North-Holland, Amsterdam, 1984.
[37] M. M. Murphy . Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting. PhD thesis, Univ. of St Andrews, 2002.
[38] C. S. J. A. Nash-Williams . On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc., 59:833–835, 1963.
[39] J. H. Schmerl and W. T. Trotter . Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discrete Math., 113(1-3):191–205, 1993.
[40] N. J. A. Sloane . The On-line Encyclopedia of Integer Sequences. Available online at http://www.research.att.com/∼njas/sequences/.
[41] T. Uno and M. Yagiura . Fast algorithms to enumerate all common intervals of two permutations. Algorithmica, 26(2):290–309, 2000.
[42] J. Wolfowitz . Note on runs of consecutive elements. Ann. Math. Statistics, 15:97–98, 1944.
[43] I. Zverovich . A finiteness theorem for primal extensions. Discrete Math., 296(1):103–116, 2005.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , R. E. L. Aldred , M. D. Atkinson , H. P. van Ditmarsch , C. C. Handley , D. A. Holton , and D. J. McCaughan . Compositions of pattern restricted sets of permutations. Australas. J. Combin., 37:43–56, 2007.
[2] M. H. Albert , M. D. Atkinson , and S. Linton . Permutations generated by stacks and deques. Ann. Comb., 14(1):3–16, 2010.
[3] M. H. Albert , S. Linton , and N. Ruškuc . On the permutational power of token passing networks. In this volume, 317–338.
[4] M. H. Albert , S. Linton , and N. Ruškuc . The insertion encoding of permutations. Electron. J. Combin., 12(1):Research paper 47, 31 pp., 2005.
[5] R. E. L. Aldred , M. D. Atkinson , H. P. van Ditmarsch , C. C. Handley , D. A. Holton , and D. J. McCaughan . Permuting machines and priority queues. Theoret. Comput. Sci., 349(3):309–317, 2005.
[6] M. D. Atkinson , M. J. Livesey , and D. Tulley . Permutations generated by token passing in graphs. Theoret. Comput. Sci., 178(1–2):103–118, 1997.
[7] M. D. Atkinson and M. Thiyagarajah . The permutational power of a priority queue. BIT, 33(1):2–6, 1993.
[8] A. Björner . Orderings of Coxeter groups. In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math., pages 175–195. Amer. Math. Soc., Providence, RI, 1984.
[9] M. Bóna . A survey of stack-sorting disciplines. Electron. J. Combin., 9(2):Article 1, 16 pp., 2003.
[10] T. Chow and J. West . Forbidden subsequences and Chebyshev polynomials. Discrete Math., 204(1–3):119–128, 1999.
[11] M. Elder . Permutations generated by a stack of depth 2 and an infinite stack in series. Electron. J. Combin., 13:Research paper 68, 12 pp., 2006.
[12] P. Erdős and G. Szekeres . A combinatorial problem in geometry. Compos. Math., 2:463–470, 1935.
[13] S. Even and A. Itai . Queues, stacks, and graphs. In Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), pages 71–86. Academic Press, New York, 1971.
[14] J. D. Gilbey and L. H. Kalikow . Parking functions, valet functions and priority queues. Discrete Math., 197/198:351–373, 1999. 16th British Combinatorial Conference (London, 1997).
[15] D. E. Knuth . The art of computer programming. Vol. 1: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass., 1969.
[16] M. M. Murphy . Restricted Permutations, Antichains, Atomic Classes, and Stack Sorting. PhD thesis, Univ. of St Andrews, 2002.
[17] V. R. Pratt . Computing permutations with double-ended queues, parallel stacks and parallel queues. In STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing, pages 268–277, New York, NY, USA, 1973. ACM Press.
[18] P. Rosenstiehl and R. E. Tarjan . Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations. J. Algorithms, 5(3):375–390, 1984.
[19] R. Simion and F. W. Schmidt . Restricted permutations. European J. Combin., 6(4):383–406, 1985.
[20] R. Tarjan . Sorting using networks of queues and stacks. J. Assoc. Comput. Mach., 19:341–346, 1972.
[21] S. Waton . On Permutation Classes Defined by Token Passing Networks, Gridding Matrices and Pictures: Three Flavours of Involvement. PhD thesis, Univ. of St Andrews, 2007.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , M. Elder , A. Rechnitzer , P. Westcott , and M. Zabrocki . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.
[2] R. Arratia . On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6:Note, N1, 4 pp., 1999.
[3] E. Babson and E. Steingrímsson . Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin., 44:Article B44b, 18 pp., 2000.
[4] J. Baik , P. Deift , and K. Johansson . On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc., 12(4):1119–1178, 1999.
[5] M. Bóna . Exact and asymptotic enumeration of permutations with subsequence conditions. PhD thesis, M.I.T., 1997.
[6] M. Bóna . Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J. Combin. Theory Ser. A, 80(2):257–272, 1997.
[7] M. Bóna . Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
[8] M. Bóna . Generalized descents and normality. Electron. J. Combin., 15(1):Note 21, 8, 2008.
[9] M. Bóna . Where the monotone pattern (mostly) rules. Discrete Math., 308(23):5782–5788, 2008.
[10] S. Elizalde . Asymptotic enumeration of permutations avoiding generalized patterns. Adv. in Appl. Math., 36(2):138–155, 2006.
[11] S. Elizalde and M. Noy . Consecutive patterns in permutations. Adv. in Appl. Math., 30(1–2):110–125, 2003.
[12] J. Fulman . Stein's method and non-reversible Markov chains. In Stein's method: expository lectures and applications, volume 46 of IMS Lecture Notes Monogr. Ser., pages 69–77. Inst. Math. Statist., Beachwood, OH, 2004.
[13] I. M. Gessel . Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A, 53(2):257–285, 1990.
[14] D. M. Jackson and R. C. Read . A note on permutations without runs of given length. Aequationes Math., 17(2–3):336–343, 1978.
[15] D. M. Jackson and J. W. Reilly . Permutations with a prescribed number of p-runs. Ars Combinatoria, 1(1):297–305, 1976.
[16] S. Janson . Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs. Ann. Probab., 16(1):305–312, 1988.
[17] I. Kaplansky . The asymptotic distribution of runs of consecutive elements. Ann. Math. Statistics, 16:200–203, 1945.
[18] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[19] A. N. Myers . Counting permutations by their rigid patterns. J. Combin. Theory Ser. A, 99(2):345–357, 2002.
[20] A. Regev . Asymptotic values for degrees associated with strips of Young diagrams. Adv. in Math., 41(2):115–136, 1981.
[21] J. Riordan . Permutations without 3-sequences. Bull. Amer. Math. Soc., 51:745–748, 1945.
[22] A. Ruciński . Proving normality in combinatorics. In Random graphs, Vol. 2 (Poznań, 1989), Wiley-Intersci. Publ., pages 215–231. Wiley, New York, 1992.
[23] R. Simion and F. W. Schmidt . Restricted permutations. European J. Combin., 6(4):383–406, 1985.
[24] R. von Mises . über die wahrscheinlichkeit seltener ereignisse. Z. Angew. Math. Mech., 1(2):121–124, 1921.
[25] R. Warlimont . Permutations avoiding consecutive patterns. Ann. Univ. Sci. Budapest. Sect. Comput., 22:373–393, 2003.
[26] R. Warlimont . Permutations avoiding consecutive patterns. II. Arch. Math. (Basel), 84(6):496–502, 2005.
[27] J. West . Permutations with forbidden subsequences and stack-sortable permutations. PhD thesis, M.I.T., 1990.
[28] J. Wolfowitz . Note on runs of consecutive elements. Ann. Math. Statistics, 15:97–98, 1944.

Reference Title: References

Reference Type: bibliography

[1] E. Babson and E. Steingrímsson . Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin., 44:Article B44b, 18 pp., 2000.
[2] A. Björner and M. L. Wachs . Permutation statistics and linear extensions of posets. J. Combin. Theory Ser. A, 58(1):85–114, 1991.
[3] M. Bóna . Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
[4] P. Brändén , A. Claesson , and E. Steingrímsson . Catalan continued fractions and increasing subsequences in permutations. Discrete Math., 258(1-3):275–287, 2002.
[5] A. Burstein and S. Kitaev . Partially ordered generalized patterns and their combinatorial interpretation. The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7–11, 2005.
[6] A. Claesson . Generalized pattern avoidance. European J. Combin., 22(7):961–971, 2001.
[7] R. C. Entringer . Enumeration of permutations of (1, …, n) by number of maxima. Duke Math. J., 36:575–579, 1969.
[8] G. Firro and T. Mansour . Restricted permutations and polygons. The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7–11, 2005.
[9] I. P. Goulden and D. M. Jackson . Combinatorial enumeration. Dover Publications Inc., Mineola, NY, 2004.
[10] M. T. Hardarson . Avoidance of partially ordered generalized patterns of the form κ-σ-κ. arXiv:0805.1872v1 [math.CO].
[11] S. Heubach , S. Kitaev , and T. Mansour . Avoidance of partially ordered patterns in compositions. Pure Math. Appl. (PU.M.A.), 17(1-2):123–134, 2006.
[12] S. Heubach and T. Mansour . Counting rises, levels, and drops in compositions. Integers, 5(1):A11, 24 pp., 2005.
[13] Q.-H. Hou and T. Mansour . Horse paths, restricted 132-avoiding permutations, continued fractions, and chebyshev polynomials. Discrete Appl. Math., 154(8):1183–1197, 2006.
[14] S. Kitaev . Multi-avoidance of generalised patterns. Discrete Math., 260(1-3):89–100, 2003.
[15] S. Kitaev . Partially ordered generalized patterns. Discrete Math., 298(1-3):212–229, 2005.
[16] S. Kitaev . Segmental partially ordered generalized patterns. Theoret. Comput. Sci., 349(3):420–428, 2005.
[17] S. Kitaev . Introduction to partially ordered patterns. Discrete Appl. Math., 155(8):929–944, 2007.
[18] S. Kitaev and T. Mansour . A survey on certain pattern problems. Available online at http://www.math.haifa.ac.il/toufik/preprint.html.
[19] S. Kitaev and T. Mansour . Partially ordered generalized patterns and k-ary words. Ann. Comb., 7(2):191–200, 2003.
[20] S. Kitaev , T. B. McAllister , and T. K. Petersen . Enumerating segmented patterns in compositions and encoding by restricted permutations. Integers, 6:A34, 16 pp., 2006.
[21] S. Kitaev and A. Pyatkin . On avoidance of υ- and λ-patterns in permutations. Ars Combin., to appear.
[22] D. Knuth . The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions. Addison-Wesley Professional, 1 edition, 2005.
[23] T. Mansour . Restricted 1-3-2 permutations and generalized patterns. Ann. Comb., 6(1):65–76, 2002.
[24] T. Mansour and A. Vainshtein . Restricted 132-avoiding permutations. Adv. in Appl. Math., 26(3):258–269, 2001.
[25] A. Mendes and J. B. Remmel . Generating functions via symmetric functions. In preparation.
[26] A. Mendes , J. B. Remmel , and A. Riehl . A generalization of the generating function for descent statistic. The Fifth International Conference on Permutation Patterns, St Andrews, Scotland, UK, June 11–15, 2007.
[27] R. Parviainen . Cycles and patterns in permutations. arXiv:math/0610616v3 [math.CO].
[28] R. G. Rieper and M. Zeleke . Valleyless sequences. In Proceedings of the Thirtyfirst Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), volume 145, pages 33–42, 2000.
[29] N. J. A. Sloane . The On-line Encyclopedia of Integer Sequences. Available online at http://www.research.att.com/∼njas/sequences/.
[30] D. Warren and E. Seneta . Peaks and Eulerian numbers in a random sequence. J. Appl. Probab., 33(1):101–114, 1996.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , M. Elder , A. Rechnitzer , P. Westcott , and M. Zabrocki . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.
[2] D. André . Développements de sec x et de tang x. C. R. Math. Acad. Sci. Paris, 88:965–967, 1879.
[3] D. André . Sur les permutations alternées. J. Math. Pures Appl., 7:167–184, 1881.
[4] E. Babson and E. Steingrímsson . Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin., 44:Article B44b, 18 pp., 2000.
[5] A. Bernini , L. Ferrari , and R. Pinzani . Enumeration of some classes of words avoiding two generalized patterns of length three. arXiv:0711.3387v1 [math.CO].
[6] A. Bernini , L. Ferrari , and R. Pinzani . Enumerating permutations avoiding three Babson-Steingrímsson patterns. Ann. Comb., 9(2):137–162, 2005.
[7] A. Bernini and E. Pergola . Enumerating permutations avoiding more than three Babson-Steingrímsson patterns. J. Integer Seq., 10(6):Article 07.6.4, 21 pp., 2007.
[8] M. Bóna . Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J. Combin. Theory Ser. A, 80(2):257–272, 1997.
[9] M. Bousquet-Mélou and S. Butler . Forest-like permutations. Ann. Comb., 11(3–4):335–354, 2007.
[10] W. G. Brown and W. T. Tutte . On the enumeration of rooted non-separable planar maps. Canad. J. Math., 16:572–577, 1964.
[11] A. Burstein and I. Lankham . Restricted patience sorting and barred pattern avoidance. In this volume, 233–257.
[12] A. Burstein and T. Mansour . Words restricted by 3-letter generalized multipermutation patterns. Ann. Comb., 7(1):1–14, 2003.
[13] D. Callan . A Wilf equivalence related to two stack sortable permutations. arXiv:math/0510211v1 [math.CO].
[14] D. Callan . A combinatorial interpretation of the eigensequence for composition. J. Integer Seq., 9(1):Article 06.1.4, 12 pp., 2006.
[15] F. R. K. Chung , R. L. Graham , V. E. Hoggatt , Jr., and M. Kleiman . The number of Baxter permutations. J. Combin. Theory Ser. A, 24(3):382–394, 1978.
[16] A. Claesson . Generalized pattern avoidance. European J. Combin., 22(7):961–971, 2001.
[17] A. Claesson , S. Kitaev , and E. Steingrímsson . Stack sorting, trees, and pattern avoidance. arXiv:0801.4037v1 [math.CO].
[18] A. Claesson and T. Mansour . Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations. Adv. in Appl. Math., 29(2):293–310, 2002.
[19] A. Claesson and T. Mansour . Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns. Ars Combin., 77:17–31, 2005.
[20] R. J. Clarke , E. Steingrímsson , and J. Zeng . New Euler-Mahonian statistics on permutations and words. Adv. in Appl. Math., 18(3):237–270, 1997.
[21] S. Corteel . Crossings and alignments of permutations. Adv. in Appl. Math., 38(2):149–163, 2007.
[22] S. Corteel and P. Nadeau . Bijections for permutation tableaux. European J. Combin., 30(1):295–310, 2009.
[23] S. Corteel and L. K. Williams . A Markov chain on permutations which projects to the PASEP. Int. Math. Res. Not. IMRN, 2007(17):Art. ID rnm055, 27, 2007.
[24] S. Corteel and L. K. Williams . Tableaux combinatorics for the asymmetric exclusion process. Adv. in Appl. Math., 39(3):293–310, 2007.
[25] S. Dulucq , S. Gire , and J. West . Permutations with forbidden subsequences and nonseparable planar maps. Discrete Math., 153(1-3):85–103, 1996.
[26] S. Elizalde . Asymptotic enumeration of permutations avoiding generalized patterns. Adv. in Appl. Math., 36(2):138–155, 2006.
[27] S. Elizalde and M. Noy . Consecutive patterns in permutations. Adv. in Appl. Math., 30(1-2):110–125, 2003.
[28] P. Flajolet . Combinatorial aspects of continued fractions. Discrete Math., 32(2):125–161, 1980.
[29] D. Foata and A. Randrianarivony . Two oiseau decompositions of permutations and their application to Eulerian calculus. European J. Combin., 27(3):342–363, 2006.
[30] D. Foata and D. Zeilberger . Denert's permutation statistic is indeed Euler-Mahonian. Stud. Appl. Math., 83(1):31–59, 1990.
[31] D. Foata and D. Zeilberger . Babson–Steingrímsson statistics are indeed Mahonian (and sometimes even Euler–Mahonian). Adv. in Appl. Math., 27(2–3):390–404, 2001.
[32] J. Françon and G. Viennot . Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d'Euler et nombres de Genocchi. Discrete Math., 28(1):21–35, 1979.
[33] I. M. Gessel . Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A, 53(2):257–285, 1990.
[34] S. Gire . Arbres, permutations à motifs exclus et cartes planaires: quelques problèmes algorithmique et combinatoire. PhD thesis, Université Bordeaux I, 1993.
[35] I. P. Goulden and D. M. Jackson . Combinatorial enumeration. Dover Publications Inc., Mineola, NY, 2004.
[36] J. Haglund . q-rook polynomials and matrices over finite fields. Adv. in Appl. Math., 20(4):450–487, 1998.
[37] M. T. Hardarson . personal communication. 2008.
[38] M. T. Hardarson . Avoidance of partially ordered generalized patterns of the form κ-σ-κ. arXiv:0805.1872v1 [math.CO].
[39] B. Jacquard and G. Schaeffer . A bijective census of nonseparable planar maps. J. Combin. Theory Ser. A, 83(1):1–20, 1998.
[40] S. Kitaev . Generalized pattern avoidance with additional restrictions. Sém. Lothar. Combin., 48:Article B48e, 19 pp., 2002.
[41] S. Kitaev . Multi-avoidance of generalised patterns. Discrete Math., 260(1-3):89–100, 2003.
[42] S. Kitaev . Partially ordered generalized patterns. Discrete Math., 298(1-3):212–229, 2005.
[43] S. Kitaev and T. Mansour . On multi-avoidance of generalized patterns. Ars Combin., 76:321–350, 2005.
[44] S. Kitaev and T. Mansour . Simultaneous avoidance of generalized patterns. Ars Combin., 75:267–288, 2005.
[45] P. A. MacMahon . Combinatory Analysis. Cambridge University Press, London, 1915/16.
[46] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[47] A. Mendes . Building generating functions brick by brick. PhD thesis, University of California, San Diego, 2004.
[48] A. Mendes and J. B. Remmel . Permutations and words counted by consecutive patterns. Adv. in Appl. Math., 37(4):443–480, 2006.
[49] J. Noonan and D. Zeilberger . The enumeration of permutations with a prescribed number of “forbidden” patterns. Adv. in Appl. Math., 17(4):381–407, 1996.
[50] E. Ouchterlony . On Young tableaux involutions and patterns in permutations. PhD thesis, Matematiska institutionen Linköpings Universitet, Linköping, Sweden, 2005.
[51] R. Parviainen . Lattice path enumeration of permutations with k occurrences of the pattern 2-13. J. Integer Seq., 9(3):Article 06.3.2, 8 pp., 2006.
[52] R. Simion and F. W. Schmidt . Restricted permutations. European J. Combin., 6(4):383–406, 1985.
[53] R. Simion and D. Stanton . Octabasic Laguerre polynomials and permutation statistics. J. Comput. Appl. Math., 68(1-2):297–329, 1996.
[54] E. Steingrímsson and L. K. Williams . Permutation tableaux and permutation patterns. J. Combin. Theory Ser. A, 114(2):211–234, 2007.
[55] J. West . Permutations with forbidden subsequences and stack-sortable permutations. PhD thesis, M.I.T., 1990.
[56] L. K. Williams . Enumeration of totally positive Grassmann cells. Adv. Math., 190(2):319–342, 2005.
[57] A. Woo and A. Yong . When is a Schubert variety Gorenstein? Adv. Math., 207(1):205–220, 2006.
[58] D. Zeilberger . The umbral transfer-matrix method. I. Foundations. J. Combin. Theory Ser. A, 91(1-2):451–463, 2000.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert . Aspects of separability. Abstract for Permutation Patterns 2007.
[2] M. H. Albert and M. D. Atkinson . Simple permutations and pattern restricted permutations. Discrete Math., 300(1-3):1–15, 2005.
[3] M. H. Albert , M. D. Atkinson , and M. Klazar . The enumeration of simple permutations. J. Integer Seq., 6(4):Article 03.4.4, 18 pp., 2003.
[4] M. H. Albert , M. D. Atkinson , and N. Ruškuc . Regular closed sets of permutations. Theoret. Comput. Sci., 306(1-3):85–100, 2003.
[5] M. H. Albert , M. Elder , A. Rechnitzer , P. Westcott , and M. Zabrocki . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.
[6] M. H. Albert and S. Linton . Growing at a perfect speed. Combin. Probab. Comput., 18:301–308, 2009.
[7] M. H. Albert , S. Linton , and N. Ruškuc . The insertion encoding of permutations. Electron. J. Combin., 12(1):Research paper 47, 31 pp., 2005.
[8] R. Arratia . On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6:Note, N1, 4 pp., 1999.
[9] M. D. Atkinson , M. J. Livesey , and D. Tulley . Permutations generated by token passing in graphs. Theoret. Comput. Sci., 178(1-2):103–118, 1997.
[10] M. D. Atkinson , M. M. Murphy , and N. Ruškuc . Partially well-ordered closed sets of permutations. Order, 19(2):101–113, 2002.
[11] M. D. Atkinson and T. Stitt . Restricted permutations and the wreath product. Discrete Math., 259(1-3):19–36, 2002.
[12] S. Bacchelli , E. Barcucci , E. Grazzini , and E. Pergola . Exhaustive generation of combinatorial objects by ECO. Acta Inform., 40(8):585–602, 2004.
[13] C. Banderier , M. Bousquet-Mélou , A. Denise , P. Flajolet , D. Gardy , and D. Gouyou-Beauchamps . Generating functions for generating trees. Discrete Math., 246(1-3):29–55, 2002.
[14] E. Barcucci , A. Del Lungo , E. Pergola , and R. Pinzani . From Motzkin to Catalan permutations. Discrete Math., 217(1-3):33–49, 2000.
[15] E. Barcucci , A. Del Lungo , E. Pergola , and R. Pinzani . Permutations avoiding an increasing number of length-increasing forbidden subsequences. Discrete Math. Theor. Comput. Sci., 4(1):31–44, 2000.
[16] M. Bousquet-Mélou . Four classes of pattern-avoiding permutations under one roof: generating trees with two labels. Electron. J. Combin., 9(2):Research paper 19, 31 pp., 2003.
[17] R. Brignall . Wreath products of permutation classes. Electron. J. Combin., 14(1):Research paper 46, 15 pp., 2007.
[18] R. Brignall , S. Huczynska , and V. Vatter . Decomposing simple permutations, with enumerative consequences. Combinatorica, 28:385–400, 2008.
[19] R. Brignall , S. Huczynska , and V. Vatter . Simple permutations and algebraic generating functions. J. Combin. Theory Ser. A, 115(3):423–441, 2008.
[20] R. Brignall , N. Ruškuc , and V. Vatter . Simple permutations: decidability and unavoidable substructures. Theoret. Comput. Sci., 391(1–2):150–163, 2008.
[21] N. Chomsky and M. P. Schützenberger . The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963.
[22] T. Chow and J. West . Forbidden subsequences and Chebyshev polynomials. Discrete Math., 204(1-3):119–128, 1999.
[23] E. Duchi , J.-M. Fedou , and S. Rinaldi . From object grammars to ECO systems. Theoret. Comput. Sci., 314(1-2):57–95, 2004.
[24] P. Erdős and G. Szekeres . A combinatorial problem in geometry. Compos. Math., 2:463–470, 1935.
[25] P. Flajolet and R. Sedgewick . Analytic combinatorics. Cambridge University Press, Cambridge, 2009.
[26] I. P. Goulden and D. M. Jackson . Combinatorial enumeration. Dover Publications Inc., Mineola, NY, 2004.
[27] O. Guibert , E. Pergola , and R. Pinzani . Vexillary involutions are enumerated by Motzkin numbers. Ann. Comb., 5(2):153–147, 2001.
[28] J. E. Hopcroft and J. D. Ullman . Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass., 1979. Addison-Wesley Series in Computer Science.
[29] S. Huczynska and V. Vatter . Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin., 13:Research paper 54, 14 pp., 2006.
[30] T. Kaiser and M. Klazar . On growth rates of closed permutation classes. Electron. J. Combin., 9(2):Research paper 10, 20 pp., 2003.
[31] D. E. Knuth . The art of computer programming. Vol. 1: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass., 1969.
[32] D. Kremer and W. C. Shiu . Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math., 268(1-3):171–183, 2003.
[33] M. Lipson . Completion of the Wilf-classification of 3-5 pairs using generating trees. Electron. J. Combin., 13(1):Research paper 31, 19 pp., 2006.
[34] T. Mansour and A. Vainshtein . Restricted 132-avoiding permutations. Adv. in Appl. Math., 26(3):258–269, 2001.
[35] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[36] V. Vatter . Permutation classes of every growth rate above 2.48188. Mathematika, 56:182–192, 2010.
[37] V. Vatter . Small permutation classes. arXiv:0712.4006v2 [math.CO].
[38] V. Vatter . Finitely labeled generating trees and restricted permutations. J. Symbolic Comput., 41(5):559–572, 2006.
[39] J. West . Generating trees and the Catalan and Schröder numbers. Discrete Math., 146(1-3):247–262, 1995.
[40] J. West . Generating trees and forbidden subsequences. Discrete Math., 157(1-3):363–374, 1996.

Reference Title: References

Reference Type: bibliography

[1] A. Burstein . On some properties of permutation tableaux. Ann. Comb., 11(3-4):355–368, 2007.
[2] R. Chapman and L. K. Williams . A conjecture of Stanley on alternating permutations. Electron. J. Combin., 14(1):Note 16, 7 pp., 2007.
[3] S. Corteel . Crossings and alignments of permutations. Adv. in Appl. Math., 38(2):149–163, 2007.
[4] S. Corteel and P. Nadeau . Bijections for permutation tableaux. European J. Combin., 30(1):295–310, 2009.
[5] S. Corteel and L. K. Williams . A Markov chain on permutations which projects to the PASEP. Int. Math. Res. Not. IMRN, 2007(17):Art. ID rnm055, 27, 2007.
[6] S. Corteel and L. K. Williams . Tableaux combinatorics for the asymmetric exclusion process. Adv. in Appl. Math., 39(3):293–310, 2007.
[7] K. Eriksson . Strongly convergent games and Coxeter groups. PhD thesis, KTH Royal Institute of Technology, 1993.
[8] A. Postnikov . Webs in totally positive Grassmann cells. Manuscript, 2001.
[9] N. J. A. Sloane . The On-line Encyclopedia of Integer Sequences. Available online at http://www.research.att.com/∼njas/sequences/.
[10] E. Steingrímsson and L. K. Williams . Permutation tableaux and permutation patterns. J. Combin. Theory Ser. A, 114(2):211–234, 2007.
[11] L. K. Williams . Enumeration of totally positive Grassmann cells. Adv. Math., 190(2):319–342, 2005.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , R. E. L. Aldred , M. D. Atkinson , C. Handley , and D. Holton . Permutations of a multiset avoiding permutations of length 3. European J. Combin., 22(8):1021–1031, 2001.
[2] P. Brändén and T. Mansour . Finite automata and pattern avoidance in words. J. Combin. Theory Ser. A, 110(1):127–145, 2005.
[3] A. Burstein . Enumeration of Words with Forbidden Patterns. PhD thesis, University of Pennsylvania, 1998.
[4] G. Firro . Distanced patterns. PhD thesis, University of Haifa, 2007.
[5] G. Firro and T. Mansour . Three-letter-pattern-avoiding permutations and functional equations. Electron. J. Combin., 13(1):Research Paper 51, 14 pp., 2006.
[6] G. Firro and T. Mansour . Restricted k-ary words and functional equations. Discrete Appl. Math., 157(4):602–616, 2009.
[7] L. Pudwell . Enumeration schemes for words avoiding patterns with repeated letters. Integers, 8:A40, 19, 2008.
[8] V. Vatter . Enumeration schemes for restricted permutations. Combin. Probab. Comput., 17:137–159, 2008.
[9] D. Zeilberger . Enumeration schemes and, more importantly, their automatic generation. Ann. Comb., 2(2):185–195, 1998.
[10] D. Zeilberger . On Vince Vatter's brilliant extension of Doron Zeilberger's enumeration schemes for Herb Wilf's classes. The Personal Journal of Ekhad and Zeilberger, published electronically at http://www.math.rutgers.edu/∼zeilberg/pj.html, 2006.

Reference Title: References

Reference Type: bibliography

[1] M. Bóna . Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.

Reference Title: References

Reference Type: bibliography

[1] H. Davenport and A. Schinzel . A combinatorial problem connected with differential equations. Amer. J. Math., 87:684–694, 1965.
[2] R. L. Graham , D. E. Knuth , and O. Patashnik . Concrete mathematics. Addison-Wesley Publishing Company, Reading, MA, second edition, 1994.
[3] V. Jelínek and T. Mansour . On pattern-avoiding partitions. Electron. J. Combin., 15(1):Research paper 39, 52, 2008.
[4] M. Klazar . On abab-free and abba-free set partitions. European J. Combin., 17(1):53–68, 1996.
[5] M. Klazar . On trees and noncrossing partitions. Discrete Appl. Math., 82(1-3):263–269, 1998.
[6] P. A. MacMahon . Combinatory Analysis. Cambridge University Press, London, 1915/16.
[7] R. C. Mullin and R. G. Stanton . A map-theoretic approach to Davenport-Schinzel sequences. Pacific J. Math., 40:167–172, 1972.
[8] B. E. Sagan . Pattern avoidance in set partitions. arXiv:math/0604292v1 [math.CO].
[9] R. P. Stanley . Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997.
[10] M. Wachs and D. White . p, q-Stirling numbers and set partition statistics. J. Combin. Theory Ser. A, 56(1):27–46, 1991.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , S. Linton , and N. Ruškuc . The insertion encoding of permutations. Electron. J. Combin., 12(1):Research paper 47, 31 pp., 2005.
[2] D. Aldous and P. Diaconis . Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. (N.S.), 36(4):413–432, 1999.
[3] S. Bespamyatnikh and M. Segal . Enumerating longest increasing subsequences and patience sorting. Inform. Process. Lett., 76(1-2):7–11, 2000.
[4] M. Bóna . Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
[5] A. Burstein and I. Lankham . Combinatorics of patience sorting piles. Sém. Lothar. Combin., 54A:Art. B54Ab, 19 pp., 2005/07.
[6] A. Burstein and I. Lankham . A geometric form for the extended patience sorting algorithm. Adv. in Appl. Math., 36(2):106–117, 2006.
[7] A. Claesson . Generalized pattern avoidance. European J. Combin., 22(7):961–971, 2001.
[8] A. Claesson and T. Mansour . Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations. Adv. in Appl. Math., 29(2):293–310, 2002.
[9] A. Claesson and T. Mansour . Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns. Ars Combin., 77:17–31, 2005.
[10] S. Dulucq , S. Gire , and O. Guibert . A combinatorial proof of J. West's conjecture. Discrete Math., 187(1-3):71–96, 1998.
[11] S. Dulucq , S. Gire , and J. West . Permutations with forbidden subsequences and nonseparable planar maps. Discrete Math., 153(1-3):85–103, 1996.
[12] C. L. Mallows . Problem 62-2, patience sorting. SIAM Review, 4:148–149, 1962. Solution in Vol. 5 (1963), 375–376.
[13] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[14] A. Price . Packing densities of layered patterns. PhD thesis, Univ. of Pennsylvania, 1997.
[15] B. E. Sagan . The Symmetric Group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001.
[16] L. W. Shapiro , S. Getu , W. J. Woan , and L. C. Woodson . The Riordan group. Discrete Appl. Math., 34(1-3):229–239, 1991.
[17] N. J. A. Sloane . The On-line Encyclopedia of Integer Sequences. Available online at http://www.research.att.com/∼njas/sequences/.
[18] R. P. Stanley . Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.
[19] G. Viennot . Une forme géométrique de la correspondance de Robinson-Schensted. In Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), pages 29–58. Lecture Notes in Math., Vol. 579. Springer, Berlin, 1977.
[20] J. West . Permutations with forbidden subsequences and stack-sortable permutations. PhD thesis, M.I.T., 1990.
[21] A. Woo and A. Yong . When is a Schubert variety Gorenstein? Adv. Math., 207(1):205–220, 2006.
[22] A. Woo and A. Yong . Governing singularities of Schubert varieties. J. Algebra, 320(2):495–520, 2008.

Reference Title: References

Reference Type: bibliography

[1] D. André . Développements de sec x et de tang x. C. R. Math. Acad. Sci. Paris, 88:965–967, 1879.
[2] D. André . Sur les permutations alternées. J. Math. Pures Appl., 7:167–184, 1881.
[3] G. E. Andrews and D. Foata . Congruences for the q-secant numbers. European J. Combin., 1(4):283–287, 1980.
[4] G. E. Andrews and I. Gessel . Divisibility properties of the q-tangent numbers. Proc. Amer. Math. Soc., 68(3):380–384, 1978.
[5] F. Brenti . Permutation enumeration symmetric functions, and unimodality. Pacific J. Math., 157(1):1–28, 1993.
[6] L. Carlitz . The coefficients of cosh x/cos x. Monatsh. Math., 69:129–135, 1965.
[7] L. Carlitz . Sequences and inversions. Duke Math. J., 37:193–198, 1970.
[8] Ö. Eğecioğlu and J. B. Remmel . Brick tabloids and the connection matrices between bases of symmetric functions. Discrete Appl. Math., 34(1-3):107–120, 1991.
[9] J.-M. Fédou and D. Rawlings . Statistics on pairs of permutations. Discrete Math., 143(1-3):31–45, 1995.
[10] D. Foata . Further divisibility properties of the q-tangent numbers. Proc. Amer. Math. Soc., 81(1):143–148, 1981.
[11] I. M. Gessel . Some congruences for generalized Euler numbers. Canad. J. Math., 35(4):687–709, 1983.
[12] V. J. W. Guo and J. Zeng . Some arithmetic properties of the q-Euler numbers and q-Salié numbers. European J. Combin., 27(6):884–895, 2006.
[13] T. M. Langley and J. B. Remmel . Enumeration of m-tuples of permutations and a new class of power bases for the space of symmetric functions. Adv. in Appl. Math., 36(1):30–66, 2006.
[14] D. J. Leeming and R. A. MacLeod . Some properties of generalized Euler numbers. Canad. J. Math., 33(3):606–617, 1981.
[15] I. G. Macdonald . Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995.
[16] A. Mendes . Building generating functions brick by brick. PhD thesis, University of California, San Diego, 2004.
[17] A. Mendes and J. B. Remmel . Generating functions for statistics on Ck ≀ Sn . Sém. Lothar. Combin., 54A:Art. B54At, 40 pp., 2005/07.
[18] A. Mendes and J. B. Remmel . Permutations and words counted by consecutive patterns. Adv. in Appl. Math., 37(4):443–480, 2006.
[19] H. Prodinger . Combinatorics of geometrically distributed random variables: new q-tangent and q-secant numbers. Int. J. Math. Math. Sci., 24(12):825–838, 2000.
[20] H. Prodinger . q-enumeration of Salié permutations. Ann. Comb., 11(2):213–225, 2007.
[21] J. B. Remmel and A. Riehl . Generating functions for permutations which contain a given descent set. Electron. J. Combin., 17(1):Research Paper 27, 33 pp., 2010.
[22] B. E. Sagan and P. Zhang . Arithmetic properties of generalized Euler numbers. Southeast Asian Bull. Math., 21(1):73–78, 1997.
[23] R. P. Stanley . Binomial posets, Möbius inversion, and permutation enumeration. J. Combinatorial Theory Ser. A, 20(3):336–356, 1976.
[24] R. P. Stanley . Enumerative combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997.
[25] J. D. Wagner . The permutation enumeration of wreath products Ck ≀ Sn of cyclic and symmetric groups. Adv. in Appl. Math., 30(1-2):343–368, 2003.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert . personal communication. 2007.
[2] M. H. Albert , M. D. Atkinson , C. C. Handley , D. A. Holton , and W. Stromquist . On packing densities of permutations. Electron. J. Combin., 9(1):Research Paper 5, 20 pp., 2002.
[3] R. Brignall . A survey of simple permutations. In this volume, pages 41–65.
[4] C. B. Presutti . Determining lower bounds for packing densities of non-layered patterns using weighted templates. Electron. J. Combin., 15(1):Research paper 50, 10, 2008.
[5] D. Warren . Optimizing the packing behavior of layered permutation patterns. PhD thesis, University of Florida, 2005.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , M. D. Atkinson , and N. Ruškuc . Regular closed sets of permutations. Theoret. Comput. Sci., 306(1-3):85–100, 2003.
[2] M. D. Atkinson , M. J. Livesey , and D. Tulley . Permutations generated by token passing in graphs. Theoret. Comput. Sci., 178(1-2):103–118, 1997.
[3] V. Auletta , A. Monti , M. Parente , and P. Persiano . A linear-time algorithm for the feasibility of pebble motion on trees. Algorithmica, 23(3):223–245, 1999.
[4] V. Auletta and P. Persiano . Optimal pebble motion on a tree. Inform. and Comput., 165(1):42–68, 2001.
[5] D. E. Knuth . The art of computer programming. Vol. 1: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass., 1969.
[6] C. H. Papadimitriou , P. Raghavan , M. Sudan , and H. Tamaki . Motion planning on a graph (extended abstract). In S. Goldwasser , editor, 35th Annual Symposium on Foundations of Computer Science, pages 511–520. IEEE, 1994.
[7] V. R. Pratt . Computing permutations with double-ended queues, parallel stacks and parallel queues. In STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing, pages 268–277, New York, NY, USA, 1973. ACM Press.
[8] D. Ratner and M. Warmuth . The (n2 – 1)-puzzle and related relocation problems. J. Symbolic Comput., 10(2):111–137, 1990.
[9] R. Tarjan . Sorting using networks of queues and stacks. J. Assoc. Comput. Mach., 19:341–346, 1972.
[10] R. M. Wilson . Graph puzzles, homotopy, and the alternating group. J. Combinatorial Theory Ser. B, 16:86–96, 1974.

Reference Title: References

Reference Type: bibliography

[1] M. H. Albert , R. E. L. Aldred , M. D. Atkinson , H. P. van Ditmarsch , B. D. Handley , C. C. Handley , and J. Opatrny . Longest subsequences in permutations. Australas. J. Combin., 28:225–238, 2003.
[2] M. H. Albert , M. D. Atkinson , R. Brignall , N. Ruškuc , R. Smith , and J. West . Growth rates for subclasses of Av(321). arXiv:0903.1999 [math.CO].
[3] M. H. Albert , M. Elder , A. Rechnitzer , P. Westcott , and M. Zabrocki . On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. in Appl. Math., 36(2):95–105, 2006.
[4] M. H. Albert and S. Linton . Growing at a perfect speed. Combin. Probab. Comput., 18:301–308, 2009.
[5] R. Arratia . On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6:Note, N1, 4 pp., 1999.
[6] M. D. Atkinson , M. M. Murphy , and N. Ruškuc . Sorting with two ordered stacks in series. Theoret. Comput. Sci., 289(1):205–223, 2002.
[7] E. Babson and E. Steingrímsson . Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin., 44:Article B44b, 18 pp., 2000.
[8] E. Babson and J. West . The permutations 123p4 … pm and 321p4 … pm are Wilf-equivalent. Graphs Combin., 16(4):373–380, 2000.
[9] J. Backelin , J. West , and G. Xin . Wilf-equivalence for singleton classes. Adv. in Appl. Math., 38(2):133–148, 2007.
[10] M. Bóna . Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J. Combin. Theory Ser. A, 80(2):257–272, 1997.
[11] M. Bóna . A survey of stack-sorting disciplines. Electron. J. Combin., 9(2):Article 1, 16 pp., 2003.
[12] M. Bóna . The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns. J. Combin. Theory Ser. A, 110(2):223–235, 2005.
[13] A. Burstein and W. Stromquist . Dumont permutations of the third kind. Extended abstract, FPSAC 2007.
[14] M. Elder and V. Vatter . Problems and conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7–11, 2005. arXiv:0505504 [math.CO].
[15] M. T. Hardarson . Avoidance of partially ordered generalized patterns of the form κ-σ-κ. arXiv:0805.1872v1 [math.CO].
[16] A. Marcus and G. Tardos . Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[17] V. R. Pratt . Computing permutations with double-ended queues, parallel stacks and parallel queues. In STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing, pages 268–277, New York, NY, USA, 1973.
[18] N. Ray and J. West . Posets of matrices and permutations with forbidden subsequences. Ann. Comb., 7(1):55–88, 2003.
[19] A. Regev . Asymptotic values for degrees associated with strips of Young diagrams. Adv. in Math., 41(2):115–136, 1981.
[20] C. Schensted . Longest increasing and decreasing subsequences. Canad. J. Math., 13:179–191, 1961.
[21] Z. Stankova and J. West . A new class of Wilf-equivalent permutations. J. Algebraic Combin., 15(3):271–290, 2002.
[22] Z. E. Stankova . Forbidden subsequences. Discrete Math., 132(1-3):291–316, 1994.
[23] V. Vatter . Permutation classes of every growth rate above 2.48188. Mathematika, 56:182–192, 2010.
[24] J. West . Permutations with forbidden subsequences and stack-sortable permutations. PhD thesis, M.I.T., 1990.
[25] J. West . Sorting twice through a stack. Theoret. Comput. Sci., 117(1-2):303–313, 1993.