Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Consecutive Patterns: From Permutations to Column-Convex Polyominoes and Back"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Consecutive Patterns: From Permutations to Column-Convex Polyominoes and Back. | Consecutive Patterns From Permutations to Column-Convex Polyominoes and Back Don Rawlings Mathematics Department California Polytechnic State University San Luis Obispo Ca. 93407 drawling@calpoly.edu Mark Tiefenbruck Mathematics Department University of California San Diego Ca. 92093 mtiefenb@math.ucsd.edu Submitted Feb 24 2010 Accepted Apr 4 2010 Published Apr 19 2010 Mathematics Subject Classification 05A15 Abstract We expose the ties between the consecutive pattern enumeration problems associated with permutations compositions column-convex polyominoes and words. Our perspective allows powerful methods from the contexts of compositions column-convex polyominoes and of words to be applied directly to the enumeration of permutations by consecutive patterns. We deduce a host of new consecutive pattern results including a solution to the 2m 1 -alternating pattern problem on permutations posed by Kitaev. Keywords ascents consecutive pattern column-convex polyomino descents levels maxima peaks twin peaks up-down type valleys variation 1 Introduction The problems of enumerating permutations compositions and words by patterns formed by consecutive terms parts or letters have been widely studied and for the most part their stories are separate and parallel. In contrast the problem of enumerating column-convex polyominoes CCPs by consecutive patterns has received only scant and indirect consideration. Our primary purpose is to show that these problem sets are in fact intimately related. More precisely if PS PC PCCP and PW respectively denote the sets of consecutive pattern enumeration problems on permutations compositions column-convex polyominoes and words then PS c PC c PCCP c PW. 1 The significance of 1 is that it allows powerful methods from the larger problem sets to be applied to the smaller problem sets. To illustrate we will show how various THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R62 1 results on words as well as Bousquet-Melou s 4 adaptation of Temperley