Partitions of ℤ_{n} into Arithmetic Progressions

William Y.C. Chen^{1}, David G.L. Wang^{2}, and Iris F. Zhang^{3}

Center for Combinatorics, LPMC-TJKLC Nankai University, Tianjin 300071, P.R. China

1chen@nankai.edu.cn, ^{2}wgl@cfc.nankai.edu.cn, ^{3}zhangfan03@mail.nankai.edu.cn

Abstract

We introduce the notion of arithmetic progression blocks or AP-blocks of ℤ_{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 ℤ_{n} into AP-blocks for a given difference m. We show that subject to a technical condition, the number of partitions of ℤ_{n} 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.

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

AMS Classification: 05A05, 05A15

1 Introduction

Let ℤ_{n} be the cyclic group of order n whose elements are written as 1, 2, …, n. Intuitively, we assume that the elements 1, 2, …, n are placed clockwise on a cycle. Thus ℤ_{n} can be viewed as an n-cycle, more specifically, a directed cycle. In his study of the ménages problem, Kaplansky [7] has shown that the number of ways of choosing k elements from ℤ_{n} such that no two elements differ by one modulo n (see also Brauldi [1], Comtet [3], Riordan [14], Ryser [15] and Stanley [16, Lemma 2.3.4]) equals

\frac{n}{n − k} \binom{n − k}{k}.  (1.1)

Moreover, Kaplansky [8] considered the following generalization. Assume that n ≥ pk + 1. Then the number of k-subsets {x_{1}, x_{2}, …, x_{k}} of ℤ_{n} such that

x_{i} − x_{j} ∉ {1, 2, …, p}  (1.2)

for any pair (x_{i}, x_{j}) of distinct elements, is given by

\frac{n}{n − pk} \binom{n − pk}{k}.  (1.3)

Here we clarify the meaning of the notation (1.2). Given two elements x and y of ℤ_{n}, x − y may be considered as the distance from y to x on the directed cycle ℤ_{n}. Therefore, (1.2) says that the distance from any element x_{i} to any other element x_{j} on the directed cycle ℤ_{n} is at least p + 1.

From a different perspective, Konvalina [10] studied the number of k-subsets {x_{1}, x_{2}, …, x_{k}} such that no two elements x_{i} and x_{j} are “uni-separated”, namely x_{i} − x_{j} ≠ 2 for all x_{i} and x_{j}. Remarkably, Konvalina discovered that the answer is also given by the Kaplansky number (1.1) for n ≥ 2k + 1. Other generalizations and related questions have been investigated by Hwang [5], Hwang, Korner and Wei [6], Munarini and Salvi [12], Prodinger [13] and Kirschenhofer and Prodinger [9]. Recently, Mansour and Sun [11] obtained the following unification of the formulas of Kaplansky and Konvalina.

Theorem 1.1. Assume that m, p, k ≥ 1 and n ≥ mpk + 1. The number of k-subsets {x_{1}, x_{2}, …, x_{k}} of ℤ_{n} such that

x_{i} − x_{j} ∉ {m, 2m, …, pm}  (1.4)

for any pair (x_{i}, x_{j}), is given by the formula (1.3), and is independent of m.

In the spirit of the original approach of Kaplansky, Mansour and Sun first solved the enumeration problem of choosing k-subset from an n-set with elements lying on a line. They established a recurrence relation, and solved the equation by computing the residues of some Laurent series. The case for an n-cycle can be reduced to the case for a line. They raised the question of finding a combinatorial proof of their formula. Guo [4] found a proof by using number theoretic properties and Rothe’s identity:

∑_{k=0}^{n} \frac{xy}{(x + kz)(y + (n − k)z)}\binom{x + kz}{k}\binom{y + (n − k)z}{n − k} = \frac{x + y}{x + y + nz} \binom{x + y + nz}{n}.

This paper is motivated by the question of Mansour and Sun. We introduce the notion of arithmetic progression blocks or AP-blocks of ℤ_{n}. A sequence of the form

(x, x + m, x + 2m, …, x + (i − 1)m) (mod n)

is called an AP-block, or an m-AP-block, of length i and of difference m. Then we consider partitions of ℤ_{n} into m-AP-blocks B_{1}, B_{2}, …, B_{k} of the same difference m. The type of such a partition is referred to as the type of the multisets of the sizes of the blocks. Our main result shows that subject to a technical condition, the number of partitions of ℤ_{n} into m-AP-blocks of a given type is independent of m and is equal to the multinomial coefficient.

This paper is organized as follows. In Section 2, we give a review of the cycle dissections and make a connection between the Kaplansky numbers and the cyclic multinomial coefficients. We present the main result in Section 3, that is, subject to a technical condition, the number of partitions of ℤ_{n} into m-AP-blocks of a given type equals the multinomial coefficient and does not depend on m. We present a separation algorithm which leads to a bijection between m-AP-partitions and m′-AP-partitions of ℤ_{n}. The correspondence between m-AP-partitions and cycle dissections (m′ = 1) implies the main result Theorem 3.2. For the type 1^{n−(p+1)k}(p + 1)^{k} we are led to a combinatorial proof which answers the question of Mansour and Sun.

2 Cycle Dissections

In their combinatorial study of Waring’s formula on symmetric functions, Chen, Lih and Yeh [2] introduced the notion of cycle dissections. Recall that a dissection of an n-cycle is a partition of the cycle into blocks, which can be viewed by putting cutting bars on some edges of the cycle. Note that there at least one bar to cut a cycle into straight segments. A dissection of an n-cycle is said of type 1^{k_{1}}2^{k_{2}} ⋯ n^{k_{n}} if there are k_{i} blocks of i elements in it. For instance, Figure 1 gives a 20-cycle dissection of type 1^{8}2^{3}3^{2}.

1 2 3 456 7 8 9 10 11 12 13 14 15 16 1718 19 20  1 2 3 4 56 7 8 9 10 11 12 13 14 15 16 1718 19 20

Figure 1: A 20-cycle dissection of type 1^{8}2^{3}3^{2}.

The following lemma is due to Chen-Lih-Yeh [2, Lemma 3.1].

Lemma 2.1. For an n-cycle, the number of dissections of type 1^{k_{1}}2^{k_{2}} ⋯ n^{k_{n}} is given by the cyclic multinomial coefficients:

\frac{n}{k_{1} + ⋯ + k_{n}} \binom{k_{1} + ⋯ + k_{n}}{k_{1}, …, k_{n}}.  (2.1)

This lemma is easy to prove. Given a dissection, one may pick up any segment as a distinguished segment. This can be done in k_{1} + k_{2} + ⋯ + k_{n} ways. On the other hand, any of the n elements can serve as the first element of the distinguished segment.

Consider a cycle dissection of type 1^{n−(p+1)k}(p + 1)^{k}. The set of the first elements of each segment of length p + 1 corresponds a k-subset of ℤ_{n} satisfying (1.2). Thus the cyclic multinomial coefficient of type 1^{n−(p+1)k}(p + 1)^{k} reduces to (1.3) and particularly the cyclic multinomial coefficient of type 1^{n−2k}2^{k} reduces to the Kaplansky number (1.1).

3 Partitions of ℤ_{n} into Arithmetic Progressions

In this section, we present the main result of this paper, namely, a formula for the number of partitions of ℤ_{n} into m-AP-blocks of a given type. The proof is based on a separation algorithm to transform an m-AP-partition to an m′-AP-partition.

We begin with some concepts. First, ℤ_{n} is considered as a directed cycle. An arithmetic progression block, or an AP-block of ℤ_{n}, is defined to be a sequence of elements of ℤ_{n} of the following form

B = (x, x + m, x + 2m, …, x + (i − 1)m) (mod n),

where m is called the difference and i is called the length of B. An AP-block of difference m is called an m-AP-block. If B contains only one element, then it is called a singleton. The first element x is called the head of B. An m-AP-partition, or a partition of ℤ_{n} into m-AP-blocks, is a set of m-AP-blocks of ℤ_{n} whose underlying sets form a partition of ℤ_{n}. For example,

(7, 9, 11), (8), (10, 12), (1), (2, 4, 6), (3), (5)  (3.1)

is a 2-AP-partition of ℤ_{12} with four singletons and three non-singleton heads 7, 10 and 2.

It should be noted that different AP-blocks may correspond to the same underlying set. For example, (1, 3) and (3, 1) are regarded as different AP-blocks of ℤ_{4}, but they have the same underlying set {1, 3}. On the other hand, as will be seen in Proposition 3.1, it often happens that an AP-block is uniquely determined by its underlying set. For example, given the difference m = 3, the AP-block (12, 15, 2, 5, 8) of ℤ_{16} is uniquely determined by the underlying set {2, 5, 8, 12, 15} since there is only one way to order these five elements to form an arithmetic progression of difference 3 modulo 16.

For an m-AP-partition π, the type of π is defined by the type of the multisets of the sizes of the blocks. Usually, we use the notation 1^{k_{1}}2^{k_{2}} ⋯ n^{k_{n}} to denote a type for which there are k_{1} blocks of size one, k_{2} blocks of size two, etc. However, for the sake of presentation, we find it more convenient to ignore the zero exponents and express a type in the form i_{1}^{k_{1}}i_{2}^{k_{2}} ⋯ i_{r}^{k_{r}}, where 1 ≤ i_{1} < i_{2} < ⋯ < i_{r} and all k_{j} ≥ 1. For example, the AP-partition (3.1) is of type 1^{4}2^{1}3^{2}.

Throughout this paper, we restrict our attention to m-AP-partitions with at least one singleton block and also at least one non-singleton block, namely, i_{1} = 1 and r ≥ 2 in the above notation of types. Here is the aforementioned condition:

⌈\frac{k_{1}}{k_{2} + ⋯ + k_{r}} ⌉ ≥ (m − 1)(i_{r} − 1),  (3.2)

where the notation ⌈x⌉ for a real number x stands for the smallest integer that larger than or equal to x. Obviously, the condition (3.2) holds for m = 1. For m ≥ 2, (3.2) is equivalent to the relation

k_{1} ≥ (k_{2} + ⋯ + k_{r})[(m − 1)(i_{r} − 1) − 1] + 1.  (3.3)

We prefer the form (3.2) for a reason that will become clear in the combinatorial argument in the proof of Theorem 3.2. In fact on an n-cycle dissection, the ∑_{j=2}^{r} k_{j} non-singleton heads divide the k_{1} singletons into ∑_{j=2}^{r} k_{j} segments. By virtue of the pigeonhole principle, there exists a segment containing at least (m−1)(i_{r}−1) singletons.

For example in the AP-partition (3.1), the three non-singleton heads divide the four singletons into three segments and therefore there exists one segment containing at least 2 singletons. In this particular partition it is the path from 2 to 7 that contains two singletons 3 and 5, see the right cycle in Figure 2.

Proposition 3.1. Under the condition (3.2), an m-AP-block is not uniquely determined by its underlying set if and only if n = i_{r}m and it is of length i_{r}.

Proof. Let n = i_{r}m. Consider the AP-blocks,

B_{j} = (x + jm, x + (j + 1)m, …, x + (j + i_{r} − 1)m) (mod n), 0 ≤ j ≤ i_{r} − 1.

It is easy to see that these AP-blocks B_{j} (j = 0, 1, …, i_{r} −1) have the same underlying set

{x, x + m, …, x + (i_{r} − 1)m}.

Conversely, suppose that there is an m-AP-block B of length i_{s} which is not uniquely determined by its underlying set. We may assume that there exists another AP-block B′ having the same underlying set as B. Thus the difference between B and B′ lies only in the order of their elements as a sequence. It follows that n = i_{s}m for some 2 ≤ s ≤ r. If m = 1, then n = i_{s} which yields s = r = 1, a contradiction. So we may assume that m ≥ 2 and 2 ≤ s ≤ r − 1. Hence i_{s} ≤ i_{r−1} ≤ i_{r} − 1, and so

k_{1} + ∑_{j=2}^{r} k_{j}i_{j} = n = i_{s}m ≤ (i_{r} − 1)m.

In view of the condition (3.3), we deduce that

(i_{r} − 1)m − ∑_{j=2}^{r} k_{j}i_{j} ≥ k_{1} ≥ [(m − 1)(i_{r} − 1) − 1] ∑_{j=2}^{r} k_{j} + 1

which can be rewritten as

1 + ∑_{j=2}^{r−1} k_{j}i_{j} + (i_{r} − 1)m (∑_{j=2}^{r} k_{j} − 1) ≤ i_{r} ∑_{j=2}^{r−1} k_{j}.

Clearly,

∑_{j=2}^{r} k_{j} − 1 ≥ ∑_{j=2}^{r−1} k_{j},

so (i_{r} − 1)m < i_{r} and thus i_{r} < m/(m − 1) ≤ 2 which implies i_{r} = 1, a contradiction. Thus we conclude that s = r. This completes the proof.

For example, the AP-partition (3.1) is uniquely determined by its underlying partition:

{7, 9, 11}, {8}, {10, 12}, {1}, {2, 4, 6}, {3}, {5}.

We are now ready to present the main result of this paper.

Theorem 3.2. Given a type 1^{k_{1}}i_{2}^{k_{2}} ⋯ i_{r}^{k_{r}} satisfying the condition (3.2), the number of m-AP-partitions of ℤ_{n} does not depend on m, and is equal to the cyclic multinomial coefficient

\frac{n}{k_{1} + ⋯ + k_{r}} \binom{k_{1} + ⋯ + k_{r}}{k_{1}, …, k_{r}}.  (3.4)

In fact, Theorem 3.2 reduces to Theorem 1.1 when we specialize the type to 1^{n−(p+1)k}(p + 1)^{k}. In this case the condition (3.2) becomes n ≥ kmp + 1. The heads of the k AP-blocks of length p + 1 satisfy the condition (1.4). Conversely, any k-subset of ℤ_{n} satisfying (1.4) determines an m-AP-partition of the given type. The cyclic multinomial coefficient (3.4) agrees with the formula (1.3) of Theorem 1.1. For example, given the type 1^{4}2^{1}3^{2} and difference 2, the AP-partition (3.1) is determined by the selection of {7, 10, 2} as heads from ℤ_{12}.

Note that the cyclic multinomial coefficient (3.4) has occurred in Lemma 2.1. Indeed, Lemma 1 is the special case of Theorem 3.2 for m = 1. We proceed to describe an algorithm, called the separation algorithm, to transform m-AP-partitions to m′-AP-partitions of the same type T = i_{1}^{k_{1}}i_{2}^{k_{2}} ⋯ i_{r}^{k_{r}}, assuming the following condition holds:

⌈\frac{k_{1}}{k_{2} + ⋯ + k_{r}} ⌉ ≥ (max\{m, m′\} − 1)(i_{r} − 1).  (3.5)

The separation algorithm enables us to verify Theorem 3.2. We will state our algorithm for m-AP-partitions and m′-AP-partitions, instead of restricting m′ to one, because it is more convenient to present the proof by exchanging the role of m and m′.

Given a type T = 1^{k_{1}}i_{2}^{k_{2}} ⋯ i_{r}^{k_{r}}, let P_{m} be the set of m-AP-partitions of type T. To prove Theorem 3.2, it suffices to show that there is a bijection between P_{m} and P′_{m} under the condition (3.5).

Let π ∈ P_{m}. Denote by H(π) the set of heads in π. For each head h of π, we consider the nearest non-singleton head in the counterclockwise direction, denoted h^{∗}. Then we denote by g(h) the number of singletons lying on the path from h^{∗} to h under the convention that h is not counted by g(h). For example, for the AP-partition π′ on the right of Figure 2, we have H(π′) = {1, 2, 3, 5, 7, 8, 10}, g(1) = g(3) = g(8) = 0, g(2) = g(5) = g(10) = 1 and g(7) = 2. The values g(h) will be needed in the separation algorithm.

π  1 2 3 4 5 6 7 8 910 11 12 ⊛ ⊛  ⊚⊚ ⊚ ▲ starting point (7, 8, 9), (10), (11, 12), (1), (2, 3, 4), (5), (6)ψ φ  π′ 1 2 3 4 5 6 7 8 9 10 11 12 ⊛  ⊛  ⊚⊚ ⊚ ▲ starting point (7, 9, 11), (8), (10, 12), (1), (2, 4, 6), (3), (5)

Figure 2: The algorithms ψ and φ for T = 1^{4}2^{1}3^{2}, m = 1 and m′ = 2.

The Separation Algorithm. Let π be an m-AP-partition of type T. As the first step, we choose a head h_{1} of π, called the starting point, such that g(h_{1}) is the maximum. Then we impose a linear order on the elements of ℤ_{n} with respect to the choice of h_{1}:

h_{1} < h_{1} + 1 < h_{1} + 2 < ⋯ < h_{1} − 1 (mod n).  (3.6)

In accordance with the above order, we denote the heads of π by h_{1} < h_{2} < ⋯ < h_{t}, where t = ∑_{i=1}^{r} k_{i}. The m-AP-block of π with head h_{i} is denoted by B_{i}. Let l_{i} be the length of B_{i}, and so ∑_{i=1}^{t} l_{i} = n.

We now aim to construct m′-AP-blocks B′_{1}, B′_{2}, …, B′_{t} such that B′_{i} has the same number of elements as B_{i}. We begin with B′_{1} by setting h′_{1} = h_{1} and letting B′_{1} be the m′-AP-block of length l_{1}, namely,

B′_{1} = (h′_{1}, h′_{1} + m′, …, h′_{1} + (l_{1} − 1)m′) .

Among the remaining elements, namely, those that are not in B′_{1}, we choose the smallest element with respect to (3.6), denoted by h′_{2}, and let B′_{2} be the m′-AP-block of length l_{2} with head h′_{2}. Repeating the above procedure, as will be justified later, after t steps we obtain an m′-AP-partition, denoted ψ(π), of type T with blocks B′_{1}, B′_{2}, …, B′_{t}.

Figure 2 illustrates the separation algorithm from a 1-AP-partition π to a 2-AP-partition π′ of the same type T = 1^{4}2^{1}3^{2} and vice versa. The solid dots stand for singletons, whereas the other symbols represent different AP-blocks.

We remark that, as indicated by the example, the starting point can never be a singleton. In fact, if s is a singleton and h is a non-singleton head such that all the heads lying on the path from s to h are singletons, then we have the relation g(h) > g(s). Since g(h_{1}) is maximum, we see that the starting point is always a non-singleton head.

Clearly, it is necessary to demonstrate that the above algorithm ψ is valid, namely, we need to justify that underlying sets of the blocks B′_{1}, B′_{2}, …, B′_{t} are disjoint.

Proposition 3.3. The mapping ψ is well-defined, and for any π ∈ P_{m}, we have ψ(π) ∈ P_{m′}.

Proof. Let π ∈ P_{m} with AP-blocks B_{1}, B_{2}, …, B_{t}. Without loss of generality, we may assume that h_{1}, h_{2}, …, h_{t} are the heads of B_{1}, B_{2}, …, B_{t}, where h_{1} is the starting point for the mapping ψ and h′_{1}, h′_{2}, …, h′_{t} are the corresponding heads generated by ψ. Let l_{i} be the length of B_{i}. Suppose to the contrary that there exist two heads h_{i} and h_{j} (i < j) such that

h′_{i} + am′ ≡ h′_{j} + bm′ (mod n),

where 0 ≤ a ≤ l_{i} − 1 and 0 ≤ b ≤ l_{j} − 1.

If a ≥ b, then 0 ≤ a − b ≤ l_{i} − 1 and h′_{j} ≡ h′_{i} + (a − b)m′ (mod n). But the point h′_{i} + (a − b)m′ is in B′_{i}, contradicting the choice of h′_{j}. This yields a < b and thus 0 ≤ b − a ≤ l_{j} − 1.

We claim that the starting point h_{1} lies on the path from h′_{j} to h′_{i}. In fact, when the Algorithm ψ is at the j-th step to deal with the head h_{j}, all the points smaller than h′_{i} lie in one of the blocks B′_{1}, B′_{2}, …, B′_{i}. Then we see that h′_{j} > h′_{i}. Meanwhile, there are n − l_{1} − l_{2} − ⋯ − l_{j−1} > 0 points which are not contained in B′_{1}, B′_{2}, …, B′_{j−1}. But the head h′_{j} is chosen to be the smallest point not in B′_{1}, B′_{2}, …, B′_{j−1}, we find that h′_{j} lies on the path from h′_{i} to h_{1}.

In addition to h′_{i} and h′_{j}, we assume that there are N points on the path from h′_{j} to h′_{i}. Since h′_{i} ≡ h′_{j} + (b − a)m′ (mod n) and 1 ≤ b − a ≤ l_{j} − 1, we obtain N = (b − a)m′ − 1. On the other hand, at the j-th step, in addition to the point h′_{j}, there are at least l_{j} − 1 points not contained in B′_{1}, B′_{2}, …, B′_{j−1}. Similarly, the choice of h_{1} and the condition (3.5) yield that the largest (max{m, m′}−1)(i_{r} −1) heads with respect to the order (3.6) are all singletons by the pigeonhole principle. Therefore, there are at least (max{m, m′} − 1)(i_{r} − 1) points not contained in B′_{1}, B′_{2}, …, B′_{j−1}.

It follows that

N ≥ (max{m, m′} − 1)(i_{r} − 1) + (l_{j} − 1).  (3.7)

Since N = (b − a)m′ − 1 and 1 ≤ b − a ≤ l_{j} − 1, we deduce that

(m′ − 1)(i_{r} − 1) + (l_{j} − 1) ≤ (b − a)m′ − 1 ≤ (l_{j} − 1)m′ − 1,

leading to the contradiction l_{j} > i_{r}. This completes the proof.

Proposition 3.4. Given an m-AP-partition of ℤ_{n}, the separation algorithm ψ generates the same m′-AP-partition regardless of the choice of the starting point subject to the maximum property.

Proof. Let π be an m-AP-partition of ℤ_{n}. Suppose that u_{1}, u_{2}, …, u_{s} (s ≥ 2) are all the heads such that g(u_{1}) = g(u_{2}) = ⋯ = g(u_{s}) is the maximum on π. Let u_{1} be the starting point and u_{1} < u_{2} < ⋯ < u_{s} with respect to (3.6).

It suffices to show that when the Algorithm ψ processes u_{i} (1 ≤ i ≤ s), the m′- AP-blocks which have been generated consist of all the elements smaller than u_{i}. By induction we assume that this statement holds up to u_{j−1}.

Let v_{q}, v_{q−1}, …, v_{1}, u_{j} be all heads lying on the path Q from u_{j−1} to u_{j} such that u_{j−1} = v_{q} < v_{q−1} < ⋯ < v_{1} < u_{j}. Let B_{i} be the m-AP-block containing v_{i}. Let l_{i} be the length of B_{i} and

B′_{i} = (v′_{i}, v′_{i} + m′, …, v′_{i} + (l_{i} − 1)m′)

be the corresponding m′-AP-blocks generated by the Algorithm ψ. It suffices to show that the path Q consists of the elements of B′_{s}, B′_{s−1}, …, B′_{1}.

Suppose that v_{1}, v_{2}, …, v_{p} are all singletons, but v_{p+1} is not a singleton. Then p ≤ q − 1 since u_{j−1} is always a non-singleton head. The condition (3.5) yields that

p ≥ (max{m, m′} − 1)(i_{r} − 1).

We now wish to show that for any 1 ≤ i ≤ q, the block B_{i} lies entirely on the path Q. If i ≤ p, then B_{i} = (v_{i}) is a singleton block lying on Q. Otherwise, we have i ≥ p + 1 and

B_{i} = (v_{i}, v_{i} + m, …, v_{i} + (l_{i} − 1)m).

But the total number of points between any two consecutive elements of B_{i} is

(l_{i} − 1)(m − 1) ≤ (max{m, m′} − 1)(i_{r} − 1) ≤ p.

Intuitively, all these points can be fulfilled by the singletons v_{p}, v_{p−1}, …, v_{1}. Since u_{j} > v_{1}, the largest element v_{i} + (l_{i} − 1)m in the block B_{i} is smaller than u_{j}. Hence the block B_{i} (i = 1, 2, …, q) lies entirely on Q.

Therefore, the total number of elements in B_{q}, B_{q−1}, …, B_{1} equals the length u_{j} − u_{j−1} of the path Q. Since B′_{i} has the same number of elements as B_{i}, the total number of elements in B′_{q}, B′_{q−1}, …, B′_{1} also equals u_{j} − u_{j−1}.

Moreover, it can be shown that the block B′_{i} also lies entirely on the path Q for any 1 ≤ i ≤ q. If i ≤ p, the block B′_{i} = (v′_{i}) is a singleton given by the separation algorithm. Since the total number of elements in B′_{q}, B′_{q−1}, …, B′_{i+1} is smaller than u_{j} −u_{j−1} and v′_{i} is chosen to be the smallest element which is not in B′_{q}, B′_{q−1}, …, B′_{i+1}, we see the relation v′_{i} < u_{j}. Otherwise, we have i ≥ p + 1 and the total number of points between any two consecutive elements of B′_{i} equals

(l_{i} − 1)(m′ − 1) ≤ (max{m, m′} − 1)(i_{r} − 1) ≤ p.

Intuitively, all these points can be fulfilled by the singletons v′_{p}, v′_{p−1}, …, v′_{1}. Since u_{j} > v′_{1}, the largest element v′_{i} + (l_{i} − 1)m′ in the block B′_{i} is smaller than u_{j}. Consequently, the block B′_{i} lies entirely on Q.

In summary, the total number of elements in B′_{q}, B′_{q−1}, …, B′_{1} which lie on the path Q coincides with the length of Q. Hence the path Q consists of the elements of B′_{s}, B′_{s−1}, …, B′_{1}. This completes the proof.

Theorem 3.5. Let T be a type as given before. The separation algorithm induces a bijection between P_{m} and P_{m′} under the condition (3.5).

Proof. We may employ the separation algorithm by interchanging the roles of m and m′ to construct an m-AP-partition from an m′-AP-partition, and we denote this map by φ. We aim to show that φ is indeed the inverse map of ψ, namely, φ(ψ(π)) = π for any π ∈ P_{m}.

Let h_{1}, h_{2}, …, h_{t} be the heads of π for the map ψ, where h_{1} is the starting point. Assume that π has AP-blocks B_{1}, B_{2}, …, B_{t} with h_{i} being the head of B_{i}. Let l_{i} be the length of B_{i}. By the construction of ψ, the generated heads h′_{1} = h_{1}, h′_{2}, …, h′_{t} have the order h′_{1} < h′_{2} < ⋯ < h′_{t} in accordance with h_{1} < h_{2} < ⋯ < h_{t}. It follows that g(h′_{1}) is the maximum considering all heads of the AP-partition ψ(π).

We now apply the map φ on the m′-AP-partition ψ(π) and choose h′_{1} as the starting point. Let h′′_{1}, h′′_{2}, …, h′′_{t} be the heads generated by φ respectively. In light of the construction of φ, we have h′′_{1} = h′_{1} = h_{1} and h′′_{1} < h′′_{2} < ⋯ < h′′_{t}.

For any i, the separation algorithm has the property that the length of the m-AP-block in φ(ψ(π)) containing h′′_{i} is l_{i}, which is the length of the m-AP-block in π containing h_{i}.

Note that both φ(ψ(π)) and π are m-AP-partitions. They have the same starting point h′′_{1} = h_{1} and the same length sequence (l_{1}, l_{2}, …, l_{t}). Thus for any i = 2, 3, …, t, the head h′′_{i} is the smallest point which is not contained in the m-AP-blocks B_{1}, B_{2}, …, B_{i−1}, and so does h_{i}. Hence we conclude that h′′_{i} = h_{i} and φ(ψ(π)) = π. This completes the proof.

Acknowledgments. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, the Ministry of Science and Technology, and the National Science Foundation of China.

References

[1] R.A. Brualdi, Introductory Combinatorics, North-Holland, New York, 1977.

[2] W.Y.C. Chen, K.W. Lih and Y.N. Yeh, Cyclic tableaux and symmetric functions, Studies in Applied Math. 94 (1995) 327–339.

[3] L. Comtet, Advanced Combinatorics, D. Reidel Pub. Co., Dordrecht, Holland, 1974.

[4] V.J.W. Guo, A new proof of a theorem of Mansour and Sun, European J. Combin. (2007), to appear.

[5] F.K. Hwang, Cycle polynomials, Proc. Amer. Math. Soc., Vol. 83, No. 1 (1981) 215–219.

[6] F.K. Hwang, J. Korner, and V.K.-W. Wei, Selecting non-consecutive balls arranged in many lines, J. Combin. Theory Ser. A 37 (1984) 327–336.

[7] I. Kaplansky, Solution of the “Problème des ménages”, Bull. Amer. Math. Soc. 49 (1943) 784–785.

[8] I. Kaplansky, Selected Papers and Other Writings, Springer (1995) 25–26.

[9] P. Kirschenhofer and H. Prodinger, Two selection problems revisited, J. Combin. Theory Ser. A 42 (1986) 310–316.

[10] J. Konvalina, On the number of combinations without unit separation, J. Combin. Theory, Ser. A 31 (1981) 101–107.

[11] T. Mansour and Y. Sun, On the number of combinatorics without certain separations, European J. Combin. 29 5 (2008) 1200-1206.

[12] E. Munarini, N.Z. Salvi, Scattered subsets, Discrete Math. 267 (2003) 213–228.

[13] H. Prodinger, On the number combinations without a fixed distance, J. Combin. Theory Ser. A 35 (1983) 362–365.

[14] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, 1958.

[15] H.J. Ryser, Combinatorial Mathematics, Carus Monograph 14, Mathematical Association of America, Wiley, New York, 1963.

[16] R.P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge, New York, Cambridge University Press, 1997.