Partitions of Z(n) into arithmetic progressions

作者：Chen William Y C; Wang David G L; Zhang Iris F

来源：European Journal of Combinatorics, 2009, 30(4): 764-773.

DOI：10.1016/j.ejc.2008.09.027

We introduce the notion of arithmetic progression blocks or m-AP-blocks of Z(n), which can be represented as sequences of the form (x, x + m, x + 2m, ..., x + (i - 1)m) (mod n). Then we consider the problem of partitioning Z(n) into m-AP-blocks. We show that subject to a technical condition, the number of partitions of Z(n) into m-AP-blocks of a given type is independent of m, and is equal to the cyclic multinomial coefficient which has occurred in Waring's formula for symmetric functions. The type of such a partition of Z(n) is defined by the type of the underlying set partition. We give a combinatorial proof of this formula and the construction is called the separation algorithm. When we restrict our attention to blocks of sizes 1 and p + 1, we are led to a combinatorial interpretation of a formula recently derived by Mansour and Sun as a generalization of the Kaplansky numbers. By using a variant of the cycle lemma, we extend the bijection to deal with an improvement of the technical condition recently given by Guo and Zeng.

• 出版日期2009-5
• 单位南开大学