Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Cyclic Derangements. | Cyclic Derangements Sami H. Assaf Department of Mathematics MIT Cambridge MA 02139 USA sassaf@math.mit.edu Submitted Apr 16 2010 Accepted Oct 26 2010 Published Dec 3 2010 Mathematics Subject Classification 05A15 05A05 05A30 Abstract A classic problem in enumerative combinatorics is to count the number of derangements that is permutations with no fixed point. Inspired by a recent generalization to facet derangements of the hypercube by Gordon and McMahon we generalize this problem to enumerating derangements in the wreath product of any finite cyclic group with the symmetric group. We also give q- and q t -analogs for cyclic derangements generalizing results of Gessel Brenti and Chow. 1 Derangements A derangement is a permutation that leaves no letter fixed. Algebraically this is an element Ơ of the symmetric group n such that a i i for any i or equivalently no cycle of Ơ has length 1. Geometrically a derangement is an isometry in Rn-1 of the regular n 1 -simplex that leaves no facet unmoved. Combinatorially these are matrices with entries from 0 1 such that each row and each column has exactly one nonzero entry and no diagonal entry is equal to 1. Let Dn denote the set of derangements in Sn and let dn Dn . The problem of counting derangements is the quintessential example of the principle of Inclusion-Exclusion 20 dn nl wt 1 1 0 i For example the first few derangement numbers are 0 1 2 9 44 265. From 1 one can immediately compute that the probability that a random permutation has no fixed points is approximately 1 e. Another exercise that often accompanies counting derangements is to prove the following two term recurrence relation for n 2 dn n 1 dn-1 dn-2 2 Partially supported by NSF Mathematical Sciences Postdoctoral Research Fellowship DMS-0703567 THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R163 1 with initial conditions d0 1 and d1 0 see 20 . From 2 one can derive the following single term recurrence for derangement numbers dn ndn-i 1 n. 3 Recently Gordon .
