INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A15

A REFINEMENT OF A PARTITION THEOREM OF SELLERS

Kuo-Jye Chen

Department of Mathematics, National Changhua University of Education, Changhua 500, Taiwan

                          kjc@math.ncue.edu.tw

Received:12/15/03, Revised: 9/29/04, Accepted: 10/19/04, Published: 10/25/04

Abstract

Abel’s identity

a_{1}b_{1}+a_{2}b_{2}+⋯+a_{m}b_{m} = (b_{1}+b_{2}+⋯+b_{m})a_{m}+(b_{1}+⋯+b_{m−1})(a_{m−1}−a_{m})+⋯+b_{1}(a_{1}−a_{2})

is used to give a refinement of a recent theorem of Sellers.

1. Introduction

Recently Sellers ([1], [2]) proved via partition analysis the following theorem.

Theorem 1. Let K = (k_{2}, k_{3}, k_{4}, ⋯) be an infinite vector of nonnegative integers with k_{2} ≥ 1. Define p(n; K) as the number of partitions of n of the form p_{1} + p_{2} + p_{3} + p_{4} + ⋯ with p_{1} ≥ p_{2} ≥ p_{3} ≥ p_{4} ⋯ ≥ 0 and p_{1} ≥ k_{2}p_{2} + k_{3}p_{3} + k_{4}p_{4} + · · ·. Then, for all n ≥ 0, p(n; K) equals the number of partitions of n whose parts must be 1′s or of the form (∑_{i=2}^{m} k_{i}) + (m − 1) for some integer m ≥ 2.

The main result of this note is a refinement of Sellers’s theorem. To state the theorem, we will first introduce some notation.

Definition 1. Let j be a nonnegative integer and let K = (k_{2}, k_{3}, k_{4}, ⋯) be a sequence of nonnegative integers with k_{2} ≥ 1.

Define

(1) K_{1} := ∅ and K_{m} := (k_{2}, k_{3}, ⋯, k_{m}) for m ≥ 2.

(2) S_{j}(n; K_{1}) := the set of all partitions of n with exactly the part j,

and for m ≥ 2 S_{j}(n; K_{m}) := the set of all partitions of n with n = p_{1} + p_{2} + ⋯ + p_{m},

p_{1} ≥ p_{2} ≥ ⋯ ≥ p_{m} ≥ 1, and p_{1} = j + k_{2}p_{2} + k_{3}p_{3} + ⋯ + k_{m}p_{m}.

(3) T_{j}(n; K_{1}) := the set of all partitions of n with 1 appearing exactly j times and with

largest part ≤ 1,

and for m ≥ 2

T_{j}(n; K_{m}) := the set of all partitions in which the only parts appeaing are 1, k_{2} + 1, k_{2} + k_{3} + 2, ⋯, k_{2} + k_{3} + ⋯ + k_{m} + m − 1, the largest part equals

k_{2} + k_{3} + ⋯ + k_{m} + m − 1, and 1 appears exactly j times.

(4) S(n; K_{m}) := ⋃_{j≥0} S_{j}(n; K_{m}), T (n; K_{m}) := ⋃_{j≥0} T_{j}(n; K_{m}), S(n; K) := ⋃_{m≥1} T (n; K_{m}), T (n; K) := ⋃_{m≥1} T (n; K_{m}).

(5) We will use the following notation for a partition p_{1}f_{1} + p_{2}f_{2} + ⋯ + p_{m}f_{m} of n:

n = p_{1} · (f_{1}) + p_{2} · (f_{2}) + ⋯ + p_{m} · (f_{m}),

where f_{i} denotes the multiplicity of the part p_{i} and p_{1} ≥ p_{2} ≥ ⋯ ≥ p_{m}.

With the notation in Definition 1, we can now state our main result:

Theorem 2. We have

|S_{j}(n; K_{m})| = |T_{j}(n; K_{m})|,

for integers j, n ≥ 0 and m ≥ 1.

Remark. Sellers’s Theorem 1 says that

∑_{j≥0} ∑_{m≥1} |S_{j}(n; K_{m})| = ∑_{j≥0} ∑_{m≥1} |T_{j}(n; K_{m})|,

and this follows immediately from Theorem 2.

In Section 2, Abel’s transform will be defined. In Section 3, Abel’s transform will be used to give a short proof of the main result. In Section 4, two examples will be given.

2. Abel’s Identity, Abel’s Transform, and the Conjugation of Partitions

Abel’s identity states that, for a_{i}, b_{i} ∈ ℝ, one has

a_{1}b_{1} + a_{2}b_{2} + ⋯ + a_{m}b_{m} = (b_{1} + b_{2} + ⋯ + b_{m})a_{m} + (b_{1} + b_{2} + ⋯ b_{m−1})(a_{m−1} − a_{m}) (1)
+ ⋯ + b_{1}(a_{1} − a_{2}),

which can be readily verified by induction. Let p_{1} · (f_{1}) + p_{2} · (f_{2}) + ⋯ + p_{m} · (f_{m}) be a partition of n. Define Abel’s transform α by

α : p_{1} · (f_{1}) + p_{2} · (f_{2}) + ⋯ + p_{m} · (f_{m}) → (f_{1} + f_{2} + ⋯ + f_{m}) · (p_{m})  (2)
+(f_{1} + f_{2} + ⋯ + f_{m−1}) · (p_{m−1} − p_{m})
+ ⋯ + f_{1} · (p_{1} − p_{2})

It follows from (1) that α^{2} is the identity map. Hence α is a bijection. Indeed, α is the conjugation of partitions. This bijection, together with other two, will provide a bijection between the two sets S_{j}(n; k_{m}) and T_{j}(n; k_{m}) in the next section.

3. Proof of Theorem 2

By use of Abel’s transform α, we are in a position to prove Theorem 2.

Proof of Theorem 2. Let n = p_{1} + p_{2} + ⋯ + p_{m} be a partition in S_{j}(n; k_{m}). Write n = j + p_{2} · (k_{2} + 1) + p_{3} · (k_{3} + 1) + ⋯ + p_{m} · (k_{m} + 1). Combining the sequence of bijections

n = j + p_{2} · (k_{2} + 1) + p_{3} · (k_{3} + 1) + ⋯ + p_{m} · (k_{m} + 1)
→ n − j = p_{2} · (k_{2} + 1) + p_{3} · (k_{3} + 1) + ⋯ + p_{m} · (k_{m} + 1)
→^{α} n − j = (k_{2} + k_{3} + ⋯ + k_{m} + (m − 1)) · p_{m} + (k_{2} + k_{3} + ⋯ + k_{m−1} + (m − 2)) ·
(p_{m−1} − p_{m}) + ⋯ + (k_{2} + 1) · (p_{2} − p_{3})
→ n = (k_{2} + k_{3} + ⋯ + k_{m} + (m − 1)) · p_{m} + (k_{2} + k_{3} + ⋯ + k_{m−1} + (m − 2)) ·
(p_{m−1} − p_{m}) + ⋯ + (k_{2} + 1) · (p_{2} − p_{3}) + 1 · (j),

we see that the last partition is in T_{j}(n; k_{m}). Hence |S_{j}(n; k_{m})| = |T_{j}(n; k_{m})|. □

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A15 4

4. Examples Example 1. The case K = (2, 1, 1, 1, ⋯) and n = 12. In this case, we have (k_{2} + 1, k_{2} + k_{3} + 2, k_{2} + k_{3} + k_{4} + 3, ⋯) = (3, 5, 7, 9, 11, ⋯),

S(12; K) = \{ \begin{matrix}12 \\ 11 + 1, 10 + 2, 9 + 3, 8 + 4 \\ 10 + 1 + 1, 9 + 2 + 1, 8 + 3 + 1, 8 + 2 + 2 \\ 9 + 1 · (3), 8 + 2 + 1 + 1, 7 + 2 + 2 + 1 \\ 8 + 1 · (4), 7 + 2 + 1 · (3) \\ 7 + 1 · (5) \end{matrix} \} ,

and

T (12; K) = \{ \begin{matrix}1 · (12) \\ 3 + 1 · (9), 3 + 3 + 1 · (6), 3 · (3) + 1 · (3), 3 · (4) \\ 5 + 1 · (7), 5 + 3 + 1 · (4), 5 + 3 + 3 + 1, 5 + 5 + 1 + 1 \\ 7 + 1 · (5), 7 + 5, 7 + 3 + 1 + 1 \\ 9 + 1 · (3), 9 + 3 \\ 11 + 1 \end{matrix} \} .

We have the following partition of S(12; K) and T (12; K) into corresponding subsets.

\{ \begin{matrix}S(12; K_{1}) = \{12\}, \\ T (12; K_{1}) = \{1 · (12)\}, \end{matrix}
\{ \begin{matrix}S(12; K_{2}) = \{11 + 1, 10 + 2, 9 + 3, 8 + 4\}, \\ T (12; K_{2}) = \{3 + 1 · (9), 3 + 3 + 1 · (6), 3 · (3) + 1 · (3), 3 · (4)\}, \end{matrix}
\{ \begin{matrix}S(12; K_{3}) = \{10 + 1 + 1, 9 + 2 + 1, 8 + 3 + 1, 8 + 2 + 2\}, \\ T (12; K_{3}) = \{5 + 1 · (7), 5 + 3 + 1 · (4), 5 + 3 + 3 + 1, 5 + 5 + 1 + 1\}, \end{matrix}
\{ \begin{matrix}S(12; K_{4}) = \{9 + 1 · (3), 8 + 2 + 1 + 1, 7 + 2 + 2 + 1\}, \\ T (12; K_{4}) = \{7 + 1 · (5), 7 + 5, 7 + 3 + 1 + 1\}, \end{matrix}
\{ \begin{matrix}S(12; K_{5}) = \{8 + 1 · (4), 7 + 2 + 1 · (3)\}, \\ T (12; K_{5}) = \{9 + 1 · (3), 9 + 3\}, \end{matrix}
\{ \begin{matrix}S(12; K_{6}) = \{7 + 1 · (5)\}, \\ T (12; K_{6}) = \{11 + 1\}. \end{matrix}

We further partition these subsets. For example, in S(12; K_{3}) and T (12; K_{3}) we have

S_{7}(12; K_{3}) = {10 + 1 + 1}, T_{7}(12; K_{3}) = {5 + 1 · (7)},
S_{4}(12; K_{3}) = {9 + 2 + 1}, T_{4}(12; K_{3}) = {5 + 3 + 1 · (4)},
S_{1}(12; K_{3}) = {8 + 3 + 1}, T_{1}(12; K_{3}) = {5 + 3 + 3 + 1},
S_{2}(12; K_{3}) = {8 + 2 + 2}, T_{2}(12; K_{3}) = {5 + 5 + 1 + 1}.

and all other S_{j}(12; K_{3}) and T_{j}(12; K_{3}) are empty. We demonstrate, for example, |S_{1}(12; K_{3})| = |T_{1}(12; K_{3})|. Take 12 = 8+3+1, a partition in S_{1}(12; K_{3}). Since 8 = 1 + 3 · (2) + 1 · (1), we have

12 = 8 + 3 + 1 = 8 + 3 · (1) + 1 · (1) = 1 + 3 · (3) + 1 · (2) → 11 = 3 · (3) + 1 · (2)
→^{α} 11 = (3 + 2) · 1 + 3 · (3 − 1)

= 5 · (1) + 3 · (2)

→ 12 = 5 · (1) + 3 · (2) + 1 · (1)

= 5 + 3 + 3 + 1

The corresponding Ferrers graph is • • • • • • •

• • • 12 = 8 + 3 + 1 = 8 + 3 · (1) + 1 · (1) = 1 + 3 · (3) + 1 · (2)

• since 8 = 1 + 3 · (2) + 1 · (1)

↓

• • •

• • •

• • • 11 = 3 · (3) + 1 · (2) • •

↓ α

• • • • •

• • • 11 = 5 + 3 + 3

• • • ↓

• • • • •

• • • 12 = 5 + 3 + 3 + 1

• • • •

Example 2. The case K = (1, 1, 1, ⋯) and n = 11. In this case, we have

(k_{2} + 1, k_{2} + k_{3} + 2, k_{2} + k_{3} + k_{4} + 3, ⋯) = (2, 4, 6, 8, ⋯),
S_{3}(11, K_{3}) = {7 + 3 + 1, 7 + 2 + 2},

and

T_{3}(11, K_{3}) = {4 + 4 + 1 · (3), 4 + 2 + 2 + 1 · (3)}.

We demonstrate |S_{3}(11, K_{3})| = |T_{3}(11, K_{3})|.

Since 7 = 3 + 3 · (1) + 1 · (1), we have

11 = 7 + 3 + 1 = 7 + 3 · (1) + 1 · (1) = 3 + 3 · (2) + 1 · (2)
→ 8 = 3 · (2) + 1 · (2)
→^{α} 8 = (2 + 2) · 1 + 2 · (3 − 1)
= 4 · (1) + 2 · (2)
→ 11 = 4 · (1) + 2 · (2) + 1 · (3).

The corresponding Ferrers graph is • • • • • • •

• • • 11 = 7 + 3 + 1 = 7 + 3 · (1) + 1 · (1) = 3 + 3 · (2) + 1 · (2)

• since 7 = 3 + 3 · (1) + 1 · (1)

↓

• • •

• • • 8 = 3 · (2) + 1 · (2) • •

↓ α

• • • •

• • 8 = 4 · (1) + 2 · (2)

• • ↓

• • • •

• •

• • 11 = 4 · (1) + 2 · (2) + 1 · (3) • • •

Next, since 7 = 3 + 2 · (1) + 2 · (1), we have

11 = 7 + 2 + 2 = 7 + 2 · (1) + 2 · (1) = 3 + 2 · (2) + 2 · (2)
→ 8 = 2 · (2) + 2 · (2)
→^{α} 8 = (2 + 2) · (2) + 2 · (2 − 2)
= 4 · (2)
→ 11 = 4 · (2) + 1 · (3).

The corresponding Ferrers graph is • • • • • • •

• • 11 = 7 + 2 + 2 = 7 + 2 · (1) + 2 · (1) = 3 + 2 · (2) + 2 · (2)

• • since 7 = 3 + 2 · (1) + 2 · (1)

↓

• •

• • 8 = 2 · (2) + 2 · (2)

• •

• • ↓ α

• • • •

• • • • 8 = 4 · (2)

↓

• • • •

• • • •

• 11 = 4 · (2) + 1 · (3) • •

Therefore, |S_{3}(11, K_{3})| = |T_{3}(11, K_{3})|.

References

[1] J. A. Sellers, Extending a recent result of Santos on partitions into odd parts, INTEGERS: Electronic Journal of Combinatorial Number Theory 3 (2003), #A04.

[2] J. A. Sellers, Corrigendum to Article A4, Volume 3 (2003), INTEGERS 4 (2004), #A08.