Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Words restricted by patterns with at most 2 distinct letters | Words restricted by patterns with at most 2 distinct letters Alexander Burstein Toufik Mansour Department of Mathematics Iowa State University Ames IA 50011-2064 UsA burstein@ LaBRI Université Bordeaux 351 cours de la Libération 33405 Talence Cedex France toufik@ Submitted Oct 26 2001 Accepted Jun 12 2002 Published Oct 31 2002 MR Subject Classifications 05A05 05A15 Abstract We find generating functions for the number of words avoiding certain patterns or sets of patterns with at most 2 distinct letters and determine which of them are equally avoided. We also find exact numbers of words avoiding certain patterns and provide bijective proofs for the resulting formulae. Let k 1 2 . k be a totally ordered alphabet on k letters. We call the elements of k n words. Consider two words Ơ 2 k n and T 2 m. In other words Ơ is an n-long k-ary word and T is an m-long -ary word. Assume additionally that T contains all letters 1 through . We say that Ơ contains an occurrence of T or simply that Ơ contains T if Ơ has a subsequence order-isomorphic to T . if there exist 1 i1 . im n such that for any relation Ộ 2 and indices 1 a b m ơ ia ỘƠ ib if and only if T a ỘT b . In this situation the word T is called a pattern. If Ơ contains no occurrences of T we say that Ơ avoids T. Up to now most research on forbidden patterns dealt with cases where both Ơ and T are permutations . have no repeated letters. Some papers Albert et al. AH Burstein B Regev R also dealt with cases where only T is a permutation. In this paper we consider some cases where forbidden patterns T contain repeated letters. Just like B this paper is structured in the manner of Simion and Schmidt SS which was the first to systematically investigate forbidden patterns and sets of patterns. 1 Preliminaries Let k n T denote the set of n-long k-ary words which avoid pattern T. If T is a set of patterns let k n T denote the set of n-long k-ary words which simultaneously avoid all patterns in T .
