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: DIAGONAL CHECKER-JUMPING AND EULERIAN NUMBERS FOR COLOR-SIGNED PERMUTATIONS. | DIAGONAL CHECKER-JUMPING AND EULERIAN NUMBERS FOR COLOR-SIGNED PERMUTATIONS Niklas Eriksen Henrik Eriksson 1 Kimmo Eriksson t niklas@ henrik@ Department of Mathematics KTH SE-100 44 Stockholm Sweden 1 NADA KTH SE-100 44 Stockholm Sweden Í IMa Malardalens hogskola Box 883 SE-721 23 Vãsterảs Sweden Submitted September 2 1999 Accepted January 26 2000. Abstract. We introduce color-signed permutations to obtain a very explicit combinatorial interpretation of the Ợ-Eulerian identities of Brenti and some generalizations. In particular we prove an identity involving the golden ratio which allows us to compute upper bounds on how high a checker can reach in a classical checkerjumping problem when the rules are relaxed to allow also diagonal jumps. 1. Introduction This paper has two themes. First we will present a notion of color-signed permutations that is signed permutations where the plus sign comes in p different colors and the minus sign comes in q different colors. These permutations give a very explicit combinatorial interpretation of the q-Eulerian identities of Brenti 2 and also provide some generalizations of them. Second we will treat a variant of an old checker-jumping problem When playing checkers on the square grid given that the lower half-plane is full of checkers and the upper half-plane is empty how high up in the upper half-plane can we place a checker by playing the game This problem was solved long ago see Berlekamp Conway and Guy s entertaining book on combinatorial games 1 . H. Eriksson and Lindstrom generalized checker-jumping to higher dimensions 5 . In his . thesis Eriksen 4 changed the rules to allow also diagonal checker-jumping moves thereby obtaining a harder problem for which we will here present an upper bound on how high the checker can be placed. 1991 Mathematics Subject Classification. Primary 05A30 Secondary 05A99. Key words and phrases. Eulerian numbers color-signed permutations .
