tailieunhanh - Báo cáo toán hoc:"Locally Restricted Compositions II. General Restrictions and Infinite Matrices"

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: Locally Restricted Compositions II. General Restrictions and Infinite Matrices. | Locally Restricted Compositions II. General Restrictions and Infinite Matrices Edward A. Bender E. Rodney Canfield Department of Mathematics Department of Computer Science University of California San Diego University of Georgia La Jolla CA 92093-0112 Athens GA 30602 ebender@ erc@ Submitted Feb 11 2009 Accepted Aug 14 2009 Published Aug 21 2009 AMS Subject Classification 05A15 05A16 Abstract We study compositions c ci . ck of the integer n in which the value c of the ith part is constrained based on previous parts within a fixed distance of ci. The constraints may depend on i modulo some fixed integer m. Periodic constraints arise naturally when m-rowed compositions are written in a single row. We show that the number of compositions of n is asymptotic to Ar n for some A and r and that many counts can be expected to have a joint normal distribution with means vector and covariance matrix asymptotically proportional to n. Our method of proof relies on infinite matrices and does not readily lead to methods for accurate estimation of the various parameters. We obtain information about the longest run. In many cases we obtain almost sure asymptotic estimates for the maximum part and number of distinct parts. 1 Introduction Carlitz compositions are compositions in which adjacent parts are distinct. We were led to this work by proposing a generalization of ordinary and Carlitz compositions which we call regular locally restricted compositions. Roughly speaking locally restricted compositions are defined by looking at pairs of parts in a moving window and regularity deals with the recurrence of patterns in a composition. Precise definitions are given in the next two sections. Example 1 Carlitz-type compositions In 2 we studied compositions in which the difference between adjacent parts must lie in a set D. Such compositions are locally Research supported by NSA Mathematical Sciences Program. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R108 1 .