tailieunhanh - Báo cáo toán hoc:"Generating functions for the number of permutations with limited displacement."

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í toán học quốc tế đề tài: Generating functions for the number of permutations with limited displacement. | Generating functions for the number of permutations with limited displacement Torleiv Kl0ve Department of Informatics University of Bergen N-5020 Bergen Norway Submitted Jan 13 2009 Accepted Aug 6 2009 Published Aug 14 2009 Mathematics Subject Classifications 05A15 94B60 Abstract Let V d n be the number of permutations p of 1 2 . n that satisfy pi i d for all i. Generating functions for V d n for fixed d are given. 1 Introduction. The problem considered in this paper is the enumeration of permutations which satisfy pi i c d for all i. The motivation comes from coding theory. A permutation array is a set of permutations of n 1 2 . n . Recently Jiang et al. 1 2 showed an application of permutation arrays to flash memories where they used different distance metrics to investigate efficient rewriting schemes. In 4 we studied the multi-level flash memory model using the Chebyshev metric. More precisely we consider the distance dmax between permutations defined by dmax p q max pj qj . j The size of a sphere in the space of permutations with this distance is V d n Td n where Td n p G Sn pi i d for 1 i n . For fixed d it is well known that V d n satisfies a linear recurrence and that the generating function is a rational function see Lehmer 5 Stanley 6 . Lehmer s proof The research was supported by the Norwegian Research Council THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R104 1 was based on writing V d n as a permanent of a suitable matrix. He only considered d 3. Stanley s proof is general and uses the transfer-matrix method see 6 . In 3 we studied V d n for general d using permanent methods. In the present paper we introduce two related new transfer-matrix methods. The advantage is that the underlying matrix has a small size. 2 First transfer-matrix method. Let X X1 X2 . . . Xd d X1 X2 Xd 0 . It easy to see that X 2d . For 1 j d 1 and x G X we define xj X1 1 X2 1 . Xj-i 1 Xj 1 Xj 2 . Xd 0 . In particular x1 x2 X3 . Xd 0 and xd 1 x1 1 x2