TAILIEUCHUNG - Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of

Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of Mathematics University of California, Berkeley Berkeley, CA 94720 asharma@ Submitted: Aug 15, 2008; Accepted: May 4, 2009; Published: May 15, 2009 Mathematics Subject Classifications: 05A15, 05C55. Abstract It is proved that the number of permutations of the set {1, 2, 3, . . . , n} that n avoid three term arithmetic progressions is at most () for n ≥ 11 and at 21 each end of any such permutation, at least ⌊ n ⌋−6 entries have the same parity. 2 1. Introduction Let S be an n-element set. | Enumerating permutations that avoid three term arithmetic progressions Arun Sharma Department of Mathematics University of California Berkeley Berkeley CA 94720 asharma@ Submitted Aug 15 2008 Accepted May 4 2009 Published May 15 2009 Mathematics Subject Classifications 05A15 05C55 Abstract It is proved that the number of permutations of the set 1 2 3 . n that 1 avoid three term arithmetic progressions is at most 21 for n 11 and at each end of any such permutation at least nJ 6 entries have the same parity. 1. Introduction Let S be an n-element set of positive integers. By a permutation of S we mean a one-to-one sequence ai a2 . an where ai G S for each i 1 i n. We use letters from the Greek alphabet to denote permutations. A permutation a ai a2 . an of S is said to contain a k-term arithmetic progression briefly a k-progression if there exists a set of indices ii i2 ik such that the subsequence ai1 ai2 . aik is either an increasing or a decreasing arithmetic progression. If a contains no k-progression we say it is k-free. The main goal of this paper is to examine the following Problem. How many permutations of the segment n 1 2 3 . n are 3-free This avoidance problem in Ramsey Theory on the integers was first raised in 4 where after a prodigious expenditure of computer time the number call it ớ n of such permutations was computed for n 20 see Appendix . Deeming the task of finding a formula for ỡ n to be hopelessly difficult the editor of the Problem Section of the Monthly observed that several conjectures concerning the behavior of the function ỡ n 0 n 1 suggested themselves. In particular he asked if it were true that lim 2. 11. u n More recently another intriguing question about ỡ n has been raised see 1 Problem asking whether lim ớ n exists. These questions are still open and apart n from the bounds for ỡ n found in 2 not much else is known about the behavior of ớ n . In this paper the method applied in 2 to obtain the lower bound

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.