TAILIEUCHUNG - Báo cáo toán học: Lattice Paths between Diagonal Boundaries

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: c. | The permutation classes equinumerous to the Smooth class Miklos Bóna LACIM Universitó du Quebec à Montróal Montreal Quebec Canada bona@ Submitted April 8 1998 Accepted June 14 1998 AMS Classification numbers 05A05 05E10 Abstract We determine all permutation classes defined by pattern avoidance which are equinumerous to the class of permutations whose Schubert variety is smooth. We also provide a lattice path interpretation for the numbers of such permutations. 1 Introduction Let q q1 q2 . qk 2 Sk be a permutation and let k n. We say that the permutation p p1 p2 pn 2 Sn contains a subsequence or pattern of type q if there is a set of indices 1 iqi iq2 iqk n such that p i1 p i2 p ik . Otherwise we say that p is q-avoiding. For example a permutation is 132-avoiding if it doesn t contain three not necessarily consecutive elements among which the leftmost is the smallest and the middle one is the largest. The enumeration of permutations of length n or in what follows n-permutations avoiding one given pattern q is a difficult problem and has recently generated a fairly extensive research. See 2 3 for an overview of these results. 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 5 1998 R31 2 A similar problem is to determine the number of n-permutations avoiding two given patterns at the same time. This is of course a much stronger restriction on the permutations so we can expect more precise results. The cases of pairs of patterns Qi q2 where q1 q2 3 or q1 3 and q2 4 are completely solved. The first instance of this problem which is not arranged yet is when q1 q2 4. In this case numerical evidence shows that the sequences Sn q1 q2 are mostly different for different inequivalent pairs q1 q2 . Two pairs of patterns are said to be equivalent if one can be transformed into the other by reversing complementing inverse-taking or a sequence of these simple transformations . There are however some exceptions. One of them is that there are some inequivalent classes counted

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