Introduction to partially ordered patterns. (English) Zbl 1118.05001
Summary: We review selected known results on partially ordered patterns (POPs) that include co-unimodal, multi- and shuffle patterns, peaks and valleys ((modified) maxima and minima) in permutations, the horse permutations and others. We provide several new results on a class of POPs built on an arbitrary flat poset, obtaining, as corollaries, the bivariate generating function for the distribution of peaks (valleys) in permutations, links to Catalan, Narayana, and Pell numbers, as well as generalizations of a few results in the literature including the descent distribution. Moreover, we discuss a \(q\)-analogue for a result on nonoverlapping segmented POPs. Finally, we suggest several open problems for further research.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 68R15 | Combinatorics on words |
| 11B75 | Other combinatorial number theory |
Keywords:
nonoverlapping occurrences; peak; valley; \(q\)-analogue; flat poset; co-unimodal pattern; bijection; (exponential bivariate) generating function; distribution; Catalan numbers; Narayana numbers; Pell numbersSoftware:
OEISOnline Encyclopedia of Integer Sequences:
Avoiding the pattern 11’22’. To avoid 11’22’ means not to have four consecutive letters such that the first letter is less than the third one and the second letter is less than the fourth one.Avoiding the pattern 121’2’. To avoid 121’2’ means not to have four consecutive letters such that the first letter is less than the second one and the third letter is less than the fourth one.
Avoiding the pattern 11’2’2.To avoid 11’2’2 means not to have four consecutive letters such that the first letter is less than the last one and the second letter is less than the third one.
Avoiding the pattern 12’1’2.To avoid 12’1’2 means not to have four consecutive letters such that the first one is less than the fourth letter and the second letter is larger than the third one.
Avoiding the pattern 121’3. To avoid 121’3 means not to have four consecutive letters such that the first letter and the third one is less than the second and the fourth letter and the second one is less than and the fourth one.
Avoiding the pattern 231’1. To avoid 231’1 means not to have four consecutive letters such that if the third letter is removed, then in the obtained 3 letter word the smallest letter is the last one, and the largest letter is the second one.
Number of permutations of 1..n avoiding adjacent step pattern up, down, up.
Permutations avoiding the consecutive patterns 4312 and 4213.
Number of permutations of 1..n avoiding adjacent step pattern up, down, down.
Suppose e<f, e<h, g<f and g<h. To avoid egfh means not to have four consecutive letters such that the first and the second letters are less than the third and the fourth letters.
Suppose e<f, e<h, g<f and g<h. To avoid efgh means not to have four consecutive letters such that the first and the third letters are less than the second and the fourth letters.
Suppose e<f, e<h, g<f and g<h. To avoid fegh means not to have four consecutive letters such that the second and the third letters are less than the first and the fourth letters.
References:
| [1] | L. Aceto, Private communication, 2006.; L. Aceto, Private communication, 2006. |
| [2] | E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire, B44b, 2000, 18pp.; E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire, B44b, 2000, 18pp. · Zbl 0957.05010 |
| [3] | Brändén, P.; Claesson, A.; Steingrímsson, E., Catalan continued fractions and increasing subsequences in permutations, Discrete Math., 258, 275-287 (2002) · Zbl 1014.05003 |
| [4] | Björner, A.; Wachs, M. L., Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A, 58, 85-114 (1991) · Zbl 0742.05084 |
| [5] | A. Burstein, S. Kitaev, Partially ordered generalized patterns and their combinatorial interpretation, in: The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7-11, 2005.; A. Burstein, S. Kitaev, Partially ordered generalized patterns and their combinatorial interpretation, in: The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7-11, 2005. · Zbl 1088.05002 |
| [6] | Claesson, A., Generalised pattern avoidance, Eur. J. Combin., 22, 961-971 (2001) · Zbl 0994.05004 |
| [7] | Comtet, L., Advanced Combinatorics (1974), D. Reidel Publishing Co.: D. Reidel Publishing Co. Dordrecht · Zbl 0283.05001 |
| [8] | Elizalde, S.; Noy, M., Consecutive patterns in permutations, Adv. Appl. Math., 30, 110-125 (2003) · Zbl 1016.05002 |
| [9] | Entringer, R., Enumeration of permutations of \((1, \ldots, n)\) by number of maxima, Duke Math. J., 36, 575-579 (1969) · Zbl 0186.01502 |
| [10] | G. Firro, T. Mansour, Restricted permutations and polygons, in: The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7-11, 2005.; G. Firro, T. Mansour, Restricted permutations and polygons, in: The Third International Conference on Permutation Patterns, University of Florida, Gainesville, Florida, March 7-11, 2005. |
| [11] | Flajolet, P.; Sedgewick, R., An Introduction to the Analysis of Algorithms (1996), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0841.68059 |
| [12] | I. Gessel, R. Stanley, Algebraic enumeration, Handbook of Combinatorics, vol. 2, 1996, pp. 1021-1061.; I. Gessel, R. Stanley, Algebraic enumeration, Handbook of Combinatorics, vol. 2, 1996, pp. 1021-1061. · Zbl 0853.05002 |
| [13] | Golden, I.; Jackson, D., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001 |
| [14] | Kitaev, S., Multi-avoidance of generalised patterns, Discrete Math., 260, 89-100 (2003) · Zbl 1013.05005 |
| [15] | Kitaev, S., Partially ordered generalized patterns, Discrete Math., 298, 212-229 (2005) · Zbl 1070.05002 |
| [16] | Kitaev, S., Segmented partially ordered generalized patterns, Theoret. Comput. Sci., 349, 3, 420-428 (2005) · Zbl 1086.05005 |
| [17] | Kitaev, S.; Mansour, T., Partially ordered generalized patterns and \(k\)-ary words, Ann. Comb., 7, 191-200 (2003) · Zbl 1020.05001 |
| [18] | S. Kitaev, T. McAllister, K. Petersen, Enumerating segmented patterns in compositions and encoding with restricted permutations, preprint.; S. Kitaev, T. McAllister, K. Petersen, Enumerating segmented patterns in compositions and encoding with restricted permutations, preprint. · Zbl 1107.05002 |
| [19] | D.E. Knuth, The Art of Computer Programming, vol. 4, Fascicle 3, Generating All Combinations and Partitions, 2005, vi+150pp, ISBN 0-201-85394-9.; D.E. Knuth, The Art of Computer Programming, vol. 4, Fascicle 3, Generating All Combinations and Partitions, 2005, vi+150pp, ISBN 0-201-85394-9. · Zbl 1127.68068 |
| [20] | Mansour, T., Restricted \(1 - 3 - 2\) permutations and generalized patterns, Ann. Comb., 6, 65-76 (2002) · Zbl 1009.05002 |
| [21] | Hou, Q.; Mansour, T., Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials, Discrete Appl. Math., 154, 8, 1183-1197 (2006) · Zbl 1161.05301 |
| [22] | Mansour, T.; Vainshtein, A., Restricted 132-avoiding permutations, Adv. Appl. Math., 126, 258-269 (2001) · Zbl 0982.05002 |
| [23] | Mendes, A.; Remmel, J. B., Permutations and words counted by consecutive patterns, Adv. Appl. Math., 37, 443-480 (2006) · Zbl 1110.05005 |
| [24] | Rieper, R.; Zeleke, M., Valleyless sequences, Congr. Numerant., 145, 33-42 (2000) · Zbl 0974.05005 |
| [25] | Sloane’s On-Line Encyclopedia of Integer Sequences, published electronically at \(\langle;\) http://www.research.att.com/\( \sim;\) njas/sequences \(\rangle;\).; Sloane’s On-Line Encyclopedia of Integer Sequences, published electronically at \(\langle;\) http://www.research.att.com/\( \sim;\) njas/sequences \(\rangle;\). |
| [26] | Warren, D.; Seneta, E., Peaks and Eulerian numbers in a random sequence, J. Appl. Probab., 33, 1, 101-114 (1996) · Zbl 0845.60035 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
