tailieunhanh - Báo cáo toán học: "Permutations Which Avoid 1243 and 2143, Continued Fractions, and Chebyshev Polynomials"

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: Permutations Which Avoid 1243 and 2143, Continued Fractions, and Chebyshev Polynomials | Permutations Which Avoid 1243 and 2143 Continued Fractions and Chebyshev Polynomials Eric S. Egge Department of Mathematics Gettysburg College Gettysburg PA 17325 USA eggee@ Toufik Mansour Department of Mathematics Chalmers University of Technology 412 96 Goteborg Sweden toufik@ Submitted Nov 11 2002 Accepted Jan 9 2003 Published Jan 22 2003 MR Subject Classifications Primary 05A05 05A15 Secondary 30B70 42C05 Abstract Several authors have examined connections between permutations which avoid 132 continued fractions and Chebyshev polynomials of the second kind. In this paper we prove analogues of some of these results for permutations which avoid 1243 and 2143. Using tools developed to prove these analogues we give enumerations and generating functions for permutations which avoid 1243 2143 and certain additional patterns. We also give generating functions for permutations which avoid 1243 and 2143 and contain certain additional patterns exactly once. In all cases we express these generating functions in terms of Chebyshev polynomials of the second kind. Keywords Restricted permutation pattern-avoiding permutation forbidden subsequence continued fraction Chebyshev polynomial 1 Introduction and Notation Let n denote the set of permutations of 1 . n written in one-line notation and suppose n E Sn and ơ E k. We say a subsequence of n has type Ơ whenever it has all of the same pairwise comparisons as Ơ. For example the subsequence 2869 of the permutation 214538769 has type 1324. We say n avoids Ơ whenever n contains no subsequence THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2003 R7 1 of type Ơ. For example the permutation 214538769 avoids 312 and 2413 but it has 2586 as a subsequence so it does not avoid 1243. If n avoids Ơ then Ơ is sometimes called a pattern or a forbidden subsequence and n is sometimes called a restricted permutation or a pattern-avoiding permutation. In this paper we will be interested in permutations which avoid .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
crossorigin="anonymous">
Đã 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.