Frequency permutation arrays

Motivated by recent interest in permutation arrays, we introduce and investigate the more general concept of frequency permutation arrays (FPAs). An FPA of length n = m lambda and distanced is a set T of multipermutations on a multiset of m symbols, each repeated with frequency lambda, such that the Hamming distance between any distinct x,y is an element of T is at least d. Such arrays have potential applications in powerline communication. In this article, we establish basic properties of FPAs, and provide direct constructions for FPAs using a range of combinatorial objects, including polynomials over finite fields, combinatorial designs, and codes. We also provide recursive constructions, and give bounds for the maximum size of such arrays. (C) 2006 Wiley Periodicals, Inc.