Partitions of Zn into Arithmetic Progressions

William Y.C. Chen, David G.L. Wang, and Iris F. Zhang

  Abstract:  We introduce the notion of arithmetic progression blocks or AP-blocks of Zn, 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 Zn into AP-blocks for a given difference m. We show that subject to a technical condition, the number of partitions of Zn into m-AP-blocks of a given type is independent of m. When we restrict our attention to blocks of sizes one or two, we are led to a combinatorial interpretation of a formula recently derived by Mansour and Sun as a generalization of the Kaplansky numbers. These numbers have also occurred as the coefficients in Waring's formula for symmetric functions.

  AMS Classification:  05A05, 05A15, 11B50

  Keywords:  Kaplansky number, cycle dissection, m-AP-partition, separation algorithm

  Download:   PDF