TAILIEUCHUNG - 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

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.