Segmental partially ordered generalized patterns
We continue the study of partially ordered generalized patterns (POGPs) considered in [E. Babson, E. Steingrimsson, Generalized permutation patterns and a classification of the Mahonian statistics, Seminaire Lotharingien de Combinatoire, 2000, B44b:18pp] for permutations and in [A. Burstein, T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electron. J. Combin. 9 (2) (2002) #R3] for words. We deal with segmental POGPs (SPOGPs). We state some general results and treat a number of patterns of length 4. We prove a result from [S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math. 260 (2003) 89-100] in a much simpler way and also establish a connection between SPOGPs and walks on lattice points starting from the origin and remaining in the positive quadrant. We give a combinatorial interpretation of the powers of the (generalized) Fibonacci numbers. The entire distribution of the maximum number of non-overlapping occurrences of a generalized pattern with no dashes in permutations or words studied in [S. Kitaev, Partially ordered generalized patterns, Discrete Math. to appear, S. Kitaev, T. Mansour, Partially ordered generalized patterns and k-ary words, Ann. Combin. 7 (2003) 191-200], respectively, has its counterpart in case of SPOGPs. (c) 2005 Elsevier B.V. All rights reserved.
permutations words walks on lattice points distribution pattern avoidance segmental patterns