tailieunhanh - Báo cáo toán học: "Asymptotics of Permutations with Nearly Periodic Patterns of Rises and Falls"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Asymptotics of Permutations with Nearly Periodic Patterns of Rises and Falls. | Asymptotics of Permutations with Nearly Periodic Patterns of Rises and Falls Edward A. Bender Department of Mathematics University of California San Diego La Jolla CA 92093-0112 ebender@ William J. Helton Department of Mathematics University of California San Diego La Jolla CA 92093-0112 helton@ L. Bruce Richmond Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario CANADA N2L 3G1 lbrichmond@ MR Subject Classifications 05A16 45C05 60C05 Submitted May 20 2003 Accepted Oct 1 2003 Published Oct 23 2003 Abstract Ehrenborg obtained asymptotic results for nearly alternating permutations and conjectured an asymptotic formula for the number of permutations that have a nearly periodic run pattern. We prove a generalization of this conjecture rederive the fact that the asymptotic number of permutations with a periodic run pattern has the form Cr-nn and show how to compute the various constants. A reformulation in terms of iid random variables leads to an eigenvalue problem for a Fredholm integral equation. Tools from functional analysis establish the necessary properties. Partially supported by the NSF and the Ford Motor Company. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R40 1 1 Introduction Definition 1 words A word is a sequence of symbols. If v and w are words then vw is the concatenation and wk is the concatenation of k copies of w. The length w of w is the number of symbols in the sequence. The descent word of a sequence Ơ1 . ơn of numbers is a a1 an-1 G d up 1 where ai d if ơi ơi 1 and ai u otherwise. If a permutation has descent word a then its run word is a sequence L of positive integers where Li is the length of the ith run in a. The size L of a run word L is the sum of its parts plus 1. Thus its size is one more than the length of the corresponding descent word. In other words it is the size of the set being permuted. Let Run N be the number of permutations that begin with an ascent and have run word