Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Enumeration of derangements with descents in prescribed positions. | Enumeration of derangements with descents in prescribed positions Niklas Eriksen Ragnar Freij Johan Wastlund Department of Mathematical Sciences Chalmers University of Technology and University of Gothenburg S-412 96 Goteborg Sweden ner@ wastlund@ Submitted Nov 6 2008 Accepted Feb 25 2009 Published Mar 4 2009 Mathematics Subject Classification Primary 05A05 05A15. Abstract We enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result and derive several explicit formulas. To this end we consider fixed point A-coloured permutations which are easily enumerated. Several formulae regarding these numbers are given as well as a generalisation of Euler s difference tables. We also prove that except in a trivial special case if a permutation n is chosen uniformly among all permutations on n elements the events that n has descents in a set S of positions and that n is a derangement are positively correlated. In a permutation n G Sn a descent is a position i such that ni ni 1 and an ascent is a position where ni ni 1. A fixed point is a position i where ni i. If ni i then i is called an excedance while if ni i i is a deficiency. Richard Stanley 10 conjectured that permutations in S2n with descents at and only at odd positions commonly known as alternating permutations and n fixed points are equinumerous with permutations in n without fixed points commonly known as derangements. The conjecture was given a bijective proof by Chapman and Williams in 2007 1 . The solution is quite straightforward If n G 2n is an alternating permutation and F c 2n is the set of fixed points with F n then removing the fixed points gives a permutation T in S 2n F without fixed points and n can be easily reconstructed from T. For instance removing the fixed points in n 326451 gives T 361 or T 231 if we reduce it to S3. To recover n we .
