tailieunhanh - Báo cáo toán học: "RESTRICTED PERMUTATIONS, CONTINUED FRACTIONS, AND CHEBYSHEV POLYNOMIALS"

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: RESTRICTED PERMUTATIONS, CONTINUED FRACTIONS, AND CHEBYSHEV POLYNOMIALS. | RESTRICTED PERMUTATIONS CONTINUED FRACTIONS AND CHEBYSHEV POLYNOMIALS Toufik Mansour and Alek Vainshtein Department of Mathematics t Department of Mathematics and Department of Computer Science University of Haifa Haifa Israel 31905 tmansur@ alek@ Submitted December 21 1999 Accepted February 27 2000. Abstract. Let fnr k be the number of 132-avoiding permutations on n letters that contain exactly r occurrences of 12 . . k and let Fr x k and F x y k be the generating functions defined by Fr x k Vn 0 fr k xn and F x y k Vr 0 Fr x k yr. We find an explicit expression for F x y k in the form of a continued fraction. This allows us to express Fr x k for 1 c r k via Chebyshev polynomials of the second kind. 2000 Mathematics Subject Classification Primary 05A05 05A15 Secondary 30B70 42C05 Typeset by Ạ 5-TpX 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 7 2000 R17 2 1. Introduction Let p 1 . pg denote a totally ordered alphabet on p letters and let a 1 . am 2 pi m 3 31 . 3m 2 p2 m. We say that a is order-isomorphic to 3 if for all 1 6 i j 6 m one has ai j if and only if 3i 3j . For two permutations T 2 n and T 2 k an occurrence of T in T is a subsequence 1 6 i1 i2 ik 6 n such that Ti1 . Tik is order-isomorphic to T in such a context T is usually called the pattern We say that T avoids T or is T-avoiding if there is no occurrence of T in T. The set of all T-avoiding permutations of all possible sizes including the empty permutation is denoted S t Pattern avoidance proved to be a useful language in a variety of seemingly unrelated problems from stack sorting 5 to singularities of Schubert varieties 6 . A complete study of pattern avoidance for the case T 2 3 is carried out in 11 . For the case T 2 S see 14 11 12 1 . A natural generalization of pattern avoidance is the restricted pattern inclusion when a prescribed number of occurrences of T in T is required. Papers 8 and 3 contain simple expressions for the number of permutations containing .

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.