Integer Compositions and Higher-Order Conjugation

Augustine O. Munagi School of Mathematics University of the Witwatersrand Wits 2050, Johannesburg South Africa

              augustine.munagi@wits.ac.za

Abstract

We consider the classical MacMahon conjugation of compositions or ordered partitions of positive integers. Using both algebraic and graphical methods we provide a natural extension of the standard conjugation of a composition to higher orders. The higher-order conjugates of a composition are obtained by varying the increments used in standard conjugation to turn strings of ones into larger summands and vice versa. It turns out that every nontrivial composition has an integral conjugation order beyond which it is not conjugable. We also discuss recursive conjugation and provide enumeration formulas and combinatorial identities between different classes of compositions.

1 Introduction

A composition of a positive integer n is an ordered partition of n or a sequence of positive integers that sum to n. The terms of the sequence are called parts and n is the weight of the composition. For example 4 has eight compositions namely

(4), (3, 1), (1, 3), (2, 2), (2, 1, 1), (1, 2, 1), (1, 1, 2), (1, 1, 1, 1).

It is well known that there are c(n) = 2^{n−1} compositions of n, and c(n, k) = \binom{n−1}{k−1} compositions of n with exactly k parts which are also called k-compositions (see for example [2, 9]).

The conjugate of a composition may be obtained by drawing its zig-zag graph. Here each part is represented by a row of dots such that the first dot on a row is aligned with the last dot on the previous row. For example, the zig-zag graph of (5, 3, 1, 2, 2) is shown in Figure 1.

\begin{aligned}• & • & • & • & • \\ & & & & • & • & • \\ & & & & & & • \\ & & & & & & • & • \\ & & & & & & & • & • \end{aligned}

Figure 1: Zig-zag graph of (5, 3, 1, 2, 2)

The conjugate is the composition corresponding to the columns of zig-zag graphs, from left to right. Thus the conjugate of (5, 3, 1, 2, 2), from the Figure 1, is (1, 1, 1, 1, 2, 1, 3, 2, 1). The conjugate of a composition C will be denoted by C′.

This is an expository paper aimed at providing a natural extension of the definition of the standard conjugation of a composition using algebraic and graphical methods. This will be followed by a brief discussion of how the resulting viewpoint refines or enlarges some familiar topics in the theory.

Percy Alexander MacMahon (1854–1929) introduced the zig-zag graph in [14]. Subsequently, in the classic text Combinatory Analysis, he contrasted the zig-zag graph with the partition Ferrers graph and remarked that the latter was rigidly fixed between two perpendicular axes [12, Sec. IV, p. 153]. However, he had previously defined conjugation using the Line Graph [12, 13] which provided an intuitive complementary relationship between a pair of mutually conjugate compositions. MacMahon also explained a diagram-free short-cut for writing the conjugates directly (now called the ‘DD’ method) [13].

In recent years conjugate compositions have played a pivotal role in the discovery of composition analogues of classical partition identities while affording natural insights into difficult proofs, see for example [8, 15, 16, 17]. The contemporary text [9] provides a wideranging coverage of the subject.

Agarwal [1] introduced n-color compositions which are extended compositions in which a part of size m may come in m different colors. Subsequently, Brian Hopkins [11] devised a MacMahon-type zig-zag graph for n-color compositions by replacing the original zig-zag graph dots with unit squares and then placing dots in some of the squares to indicate colors of part sizes. However, the graphical conjugation operation proposed by Hopkins failed to yield conjugates to many n-color compositions. Several other generalizations of compositions have appeared in the literature in the form of weighted compositions [6, 7], locally restricted compositions [3, 4] and compositions whose parts belong to a prescribed integer set [9, 10], and so forth. But none of these species of compositions emerged with specialized conjugation considerations.

Two further methods of obtaining the conjugate composition are outlined in Section 2 together with other essential preliminaries. In Section 3 we introduce the concept of higherorder conjugation of a composition and show the extended line graph representation. Section 4 deals with the highest possible order to which a composition is conjugable while Section 5 considers an additional conjugation-like operation and recursive conjugation. In Section 6 we discuss the derivation of higher-order conjugate compositions from zig-zag graphs. The enumeration of conjugable compositions of a given order is discussed in Section 7. Lastly, Section 8 considers a few combinatorial identities between different classes of compositions.

2 Preliminaries

We summarize two other methods of obtaining the conjugate of a composition employed by MacMahon [12, 13].

LG: Line Graph. In the line-graph of a composition C, denoted by LG(C), the weight n is depicted as a line divided into n equal segments and separated by n − 1 gaps. A composition C = (c_{1}, …, c_{k}) of n then corresponds to a choice of k − 1 from the n − 1 gaps, indicated with dots, such that each part c_{j} is represented by c_{j} equal contiguous segments, 1 ≤ j ≤ k. For example the line graph of the composition C = (3, 1, 1, 2, 4, 1) of 12 is

LG(C) : − − − · − · − · − − · − − − − · −.

The conjugate C′ is the composition whose line graph is obtained by placing dots in the gaps which previously had no dots, that is,

LG(C′) : − · − · − − − − · − − · − · − · −−.

Hence C′ = (1, 1, 4, 2, 1, 1, 2).

We observe that the LG method gives the number of parts of C′ directly as n − k + 1.

DD: Direct Detection of Conjugates. First, we write compositions symbolically by representing a maximal string of 1’s of length x by 1^{x}, where two adjacent big parts (i.e., parts > 1) are assumed to be separated by 1^{0}. For example (1, 1, 1, 5, 1, 1, 8, 2, 1, 5) = (1^{3}, 5, 1^{2}, 8, 1^{0}, 2, 1, 5).

The general composition in symbolic form C = (…, 1^{a_{u}}, b_{v}, 1^{a_{u+1}}, b_{v+1}, …), has the following four types (with b_{i} > 1 for all i):

(i) C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, b_{2}, …, b_{r}, 1^{a_{r+1}}), a_{1}, a_{r+1} > 0, a_{i} ≥ 0, i > 1;

(ii) C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, b_{2}, …, 1^{a_{r}}, b_{r}), a_{1} > 0, a_{i} ≥ 0, i > 1;

(iii) C = (b_{1}, 1^{a_{1}}, b_{2}, 1^{a_{2}}, …, b_{r}, 1^{a_{r}}), a_{i} ≥ 0, i ≠ r, a_{r} > 0;

(iv) C = (b_{1}, 1^{a_{1}}, b_{2}, 1^{a_{2}}, …, b_{r−1}, 1^{a_{r−1}}, b_{r}), a_{i} ≥ 0, 1 ≤ i < r.

The Direct Detection (DD) technique is an easily-mastered rule for writing down the conjugate of a composition in symbolic form by inspection [15, 16].

The respective conjugates of the four types of compositions are given according to the rule below.

(i’) C′ = (a_{1} + 1, 1^{b_{1}−2}, a_{2} + 2, 1^{b_{2}−2}, …, 1^{b_{r}−2}, a_{r+1} + 1);

(ii’) C′ = (a_{1} + 1, 1^{b_{1}−2}, a_{2} + 2, 1^{b_{2}−2}, …, a_{r} + 2, 1^{b_{r}−1});

(iii’) C′ = (1^{b_{1}−1}, a_{1} + 2, 1^{b_{2}−2}, a_{2} + 2, …, 1^{b_{r}−2}, a_{r} + 1);

(iv’) C′ = (1^{b_{1}−1}, a_{1} + 2, 1^{b_{2}−2}, a_{2} + 2, …, a_{r−1} + 2, 1^{b_{r}−1}).

The DD technique shows that C and C′ have the same number of symbolic parts.

For example, the conjugate of (5, 3, 1, 2, 2) = (5, 1^{0}, 3, 1, 2, 1^{0}, 2) is given by

(1^{4}, 2, 1, 3, 1^{0}, 2, 1).

In the sequel compositions of the form (1^{n}) or (n) will be called trivial. Thus a nontrivial composition contains 1 and a big part or at least two big parts.

The four types of compositions in (i) to (iv) will be referred to as 1c1, 1c2, 2c1 and 2c2, compositions, respectively. Thus a 1c1 composition has the first and last parts equal to 1, a 1c2 composition has a first part 1 and a last part > 1, and so forth. Their conjugates in (i’) to (iv’) are 2c2, 2c1, 1c2 and 1c1 compositions. We will mostly use 1c2 or 2c1 compositions for demonstrations because they possess the features of all four types. Note that a 1c2 or 2c1 composition is never trivial.

A nontrivial composition in symbolic form consists of an alternation of big parts and strings of 1’s. Initial and final strings of 1’s or big parts are boundary objects while others are interior or intermediate objects.

A composition C is deemed to be empty (or non-existent), denoted by C = ∅, if a defining inequality is violated. For example, if C is a 1c2 composition (see (ii) above), then C = ∅ if b_{i} < 2 for some i or a_{1} < 1 or a_{i} < 0, i = 2, 3, …, r.

3 Higher-order conjugation

Consider the general 1c2 composition

C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, b_{2}, …, 1^{a_{r}}, b_{r}), a_{1} > 0, a_{i} ≥ 0, i > 1, b_{i} > 1, ∀ i.

As already seen, the conjugate using the DD conjugation rule, is

C′ = (a_{1} + 1, 1^{b_{1}−2}, a_{2} + 2, 1^{b_{2}−2}, …, a_{r} + 2, 1^{b_{r}−1}).

This is the classical conjugation, and we say that it is of order 1. Notice that this process involves subtracting 1 from a boundary big part, and subtracting 2 = 2 × 1 from an intermediate big part to make 1’s (and correspondingly adding 1 to a boundary string of 1’s, and adding 2 to an intermediate string of 1’s, to make a big part).

For example, C = (1^{3}, 6, 4, 1^{2}, 5) = (1^{3}, 6, 1^{0}, 4, 1^{2}, 5) has the conjugate of order 1 given by

C′ = (3 + 1, 1^{6−2}, 0 + 2, 1^{4−2}, 2 + 2, 1^{5−1}) = (4, 1^{4}, 2, 1^{2}, 4, 1^{4}).

On the other hand, C has the order-2 conjugate

C′′ = (3 + 2, 1^{6−4}, 0 + 4, 1^{4−4}, 2 + 4, 1^{5−2}) = (5, 1^{2}, 4, 1^{0}, 6, 1^{3}).

In the second conjugation, we subtracted 2 from a boundary big part, and subtracted 4 = 2×2 from an intermediate big part, to make 1’s.

However, C′′′ = ∅ : interior big parts of size at least 6 are required. This may be extended to higher orders.

Definition 1 (Conjugate of Order t). Let t be a positive integer. A nontrivial composition C possesses a conjugate of order t if every boundary big part of C is greater than t and every interior big part is greater than or equal to 2t.

Let C be a composition that possesses a conjugate of order t. Then to obtain the conjugate of order t, we subtract t from each boundary big part and subtract 2t from every intermediate big part to make 1’s, and correspondingly add t to a boundary string of 1’s, and add 2t to an intermediate string of 1’s, to make a big part.

Thus a 1c2 composition C that possesses a conjugate of order t > 0 has the form

C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, …, 1^{a_{r}}, b_{r}),
a_{1} ≥ 1, a_{i} ≥ 0, i > 1, b_{i} ≥ 2t, 1 ≤ i ≤ r − 1, b_{r} > t.  (1)

The conjugate of order t is a composition E given by

E = (a_{1} + t, 1^{b_{1}−2t}, a_{2} + 2t, 1^{b_{2}−2t}, …, a_{r} + 2t, 1^{b_{r}−t}).  (2)

Notice that E is a 2c1 composition as expected. It is easily checked that the parts of E satisfy a_{1} + t > t, b_{i} − 2t ≥ 0 and b_{r} − t > 0. So the parts of E fulfill the same properties as the parts of C. Therefore E in turn possesses a conjugate of order t. It may be verified that the conjugate of E, of order t, is C.

Definition 2. Given a positive integer t, a composition is t-conjugable if it possesses a conjugate of order t. A t-conjugable composition C is also said to possess a t-conjugate, denoted successively, for t = 1, 2, 3, …, by C′, C′′, C′′′, …, C^{(t)}, C^{(t+1)}, . . ..

The trivial compositions (1^{n}) and (n) possess conjugates of arbitrary order. So they are conventionally m-conjugable for all positive integers m.

(1^{n})^{(m)} = (n) and (n)^{(m)} = (1^{n}), m > 0.

The following characterization is equivalent to the first part of Definition 1.

Theorem 3. A nontrivial t-conjugable composition (c_{1}, c_{2}, …, c_{k}) satisfies the properties:

(i) if x = c_{1} > 1 or x = c_{k} > 1, then x > t,

(ii) if i ≠ 1, k and c_{i} > 1, then c_{i} ≥ 2t.

Clearly C is t-conjugable if and only if C^{(t)} is t-conjugable. So t-conjugation is an involution on the set of t-conjugable compositions of n (a fact that is well-known for t = 1).

It is clear that a t-conjugable composition is s-conjugable for s = 1, 2, …, t.

3.1 The extended line graph

The line graph representation of C^{(t)} is obtained from that of C as a natural extension of the t = 1 case.

Let C be a t-conjugable composition of n with line graph LG(C). Then LG(C^{(t)}) is obtained from LG(C) with the following rule.

Place a dot in any gap that previously had no dot except the first t − 1 gaps immediately before or after a previous dot.

Thus the case t = 1 gives no exception for inserting dots into previously empty gaps to obtain LG(C′). But to obtain LG(C′′) every gap immediately before or after a previous dot in LG(C) must also be skipped, and so forth.

For example, consider the composition of n = 23 given by C = (1, 6, 9, 1, 1, 5). Then we have

LG(C) : − · − − − − − − · − − − − − − − − − · − · − · − − − − − .

Using the rule we obtain

LG(C′′) : − − − · − · − · − − − − · − · − · − · − · − · − − − − − − · − · − · −.

Thus C′′ = (3, 1^{2}, 4, 1^{5}, 6, 1^{3}).

Observe that the rule also restores LG(C) by using LG(C′′) to construct the line graph of the 2-conjugate of C′′ since LG((C′′)′′) = LG(C).

The Zig-zag graph representation of t-conjugable compositions is discussed in Section 6.

4 The conjugate height

To every nontrivial composition C is associated a unique positive integer m < ∞ such that C is m-conjugable and not (m + 1)-conjugable.

Definition 4. The conjugate height of a nontrivial composition C is the greatest positive integer m such that C is m-conjugable.

If the conjugate height of C is m we also write ht(C) = m.

By this definition every nontrivial composition C of n ≥ 3 satisfies

1 ≤ ht(C) ≤ n − 2, n > 2,  (3)

where equality holds on the right for the compositions (1, n − 1), (n − 1, 1). There is no nontrivial composition of n with height greater than n − 2.

If ht(C) = t > 1, then C is (t − 1)-conjugable. If ht(C) = t, then C^{(t+1)} = ∅.

Theorem 5. A nontrivial t-conjugable composition C = (c_{1}, c_{2}, …, c_{k}) has conjugate height t if and only if either of the following conditions hold:

(i) Every c_{i} > 1, 2 ≤ i ≤ k − 1 satisfies c_{i} ≥ 2t and t + 1 ∈ {c_{1}, c_{k}}.

(ii) c_{i} ∈ {2t, 2t + 1} for some i ≠ 1, k, and c_{1}, c_{k} ≥ t + 1.

Proof. We use the standard 1c2 composition C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, b_{2}, …, 1^{a_{r}}, b_{r}). Thus c_{k} = b_{r}, and any c_{i} > 1 corresponds to b_{i} for some i = 1, …, r − 1.

Assume ht(C) = t. Then C^{(t)} exists but not C^{(t+1)}. Consider

C^{(t)} = (a_{1} + t, 1^{b_{1}−2t}, …, a_{r} + 2t, 1^{b_{r}−t}) ≠ ∅,  (4)
C^{(t+1)} = (a_{1} + t + 1, 1^{b_{1}−2t−2}, …, a_{r} + 2t + 2, 1^{b_{r}−t−1}) = ∅.  (5)

Since C^{(t+1)} = ∅, Equations (4) and (5) imply that b_{r} may satisfy b_{r} −t > 0 and b_{r} −t−1 < 1, which imply 1 ≤ b_{r} − t ≤ 1 or b_{r} = t + 1 (where we have used Theorem 3). Alternatively, we might have b_{i} − 2t ≥ 0 and b_{i} − 2t − 2 < 0 for some i ∈ {1, …, r − 1}. This gives 0 ≤ b_{i} − 2t ≤ 1 or 2t ≤ b_{i} ≤ 2t + 1. So conditions (i) and (ii) hold.

Conversely (i) implies that b_{r} = t + 1. But from (5) C^{(t+1)} = ∅ since its last string of 1’s will be 1^{b_{r}−t−1} = 1^{0}. Condition (ii) implies that b_{i} ∈ {2t, 2t + 1}, i ≠ r. Then 1^{b_{i}−2t−2} = 1^{u}, u < 0; thus C^{(t+1)} = ∅. So ht(C) = t and the assertion is proved.

The set of compositions with height ≥ t is precisely the set of t-conjugable compositions: C^{(t)} ≠ ∅ ⟺ ht(C) ≥ t.

Let G_{t}(n) be the set of compositions of n with conjugate height t and let C_{t}(n) be the set of t-conjugable compositions of n with g_{t}(n) = |G_{t}(n)| and c_{t}(n) = |C_{t}(n)|. Then we have g_{1}(n) ≥ g_{2}(n) ≥ ⋯ ≥ g_{n−2}(n) ≥ g_{x}(n), x ≥ n − 1, even though G_{i}(n) ∩ G_{j}(n) = ∅, i ≠ j.

However, c_{1}(n) ≥ c_{2}(n) ≥ ⋯ ≥ c_{n−2}(n) ≥ c_{x}(n) with C_{1}(n) ⊇ C_{2}(n) ⊇ ⋯ ⊇ C_{n−2}(n) ⊇ C_{x}(n). Hence c_{1}(n) = c(n) = 2^{n−1}, and

C_{t}(n) = ⋃_{i≥t} G_{i}(n) and G_{t}(n) = C_{t}(n) \ C_{t+1}(n).  (6)

For example, g_{1}(6) = 22, g_{2}(6) = 4, g_{3}(6) = 2, g_{4}(6) = 2 and g_{x}(6) = 2, x ≥ 5, where the enumerated sets are shown below.

G_{1}(6): (2, 4), (4, 2), (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 2, 2), (2, 3, 1), (3, 1, 2), (3, 2, 1),

(1, 1, 2, 2), (1, 1, 3, 1), (1, 2, 1, 2), (1, 2, 2, 1), (1, 3, 1, 1), (2, 1, 1, 2), (2, 1, 2, 1),
(2, 2, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 2, 1), (1, 1, 2, 1, 1), (1, 2, 1, 1, 1), (2, 1, 1, 1, 1);

G_{2}(6): (3, 3), (1, 4, 1), (1, 1, 1, 3), (3, 1, 1, 1);

G_{3}(6): (1, 1, 4), (4, 1, 1);

G_{4}(6): (1, 5), (5, 1);

G_{x}(6): (6), (1, 1, 1, 1, 1, 1).

If C and E are compositions of n with ht(C) = ht(E) = t, then ht(C^{(t)}) ≠ ht(E^{(t)}) in general. For example consider the 2-conjugates of C = (1^{4}, 5, 1^{8}, 4, 1^{6}) and E = (1^{4}, 5, 1^{5}, 7, 1^{6}). Then C′′ = (6, 1, 12, 1^{0}, 8) satisfies ht(C′′) = 5 while E′′ = (6, 1, 9, 1^{3}, 8) gives ht(E′′) = 4.

When C^{(t)} ≠ ∅, it is clear that ht(C) ≤ ht(C^{(t)}); but when do we have ht(C) = ht(C^{(t)})? The following criterion is obtained by applying Theorem 5 to C^{(t)} with height m and the

fact that the big parts of C^{(t)} are determined by the strings of 1’s in C.

Corollary 6. Let C be a t-conjugable composition with height m (m ≥ t). Then C^{(t)} has height m if and only if

(i) every boundary string 1^{a} in C satisfies a = m − t + 1 and every interior string 1^{a} satisfies a ≥ 2(m − t), or

(ii) every boundary string 1^{a} in C satisfies a ≥ m − t + 1 and every interior string 1^{a} satisfies a ∈ {2(m − t), 2(m − t) + 1},

In particular, when m = t, we obtain the next result.

Corollary 7. Let C be a composition with height t. Then C^{(t)} has height t if and only if C contains an isolated 1 or a pair of consecutive big parts (i.e., C is not reciprocal (see definition in Section 5)).

Proposition 8. If C is a composition with height t ≥ s > 0, then ht((C^{(t)})^{(s)}) = s. In particular ht((C^{(t)})′) = 1.

Proof. Assume that ht(C) = t. Then for some interior part b ∈ {2t, 2t + 1}, the operations C → C^{(t)} → (C^{(t)})^{(s)} induce b → 1^{b−2t} → b−2t+2s which imply that b−2t+2s ∈ {2s, 2s+1}. Alternatively for a boundary big part b = t + 1 we have b → 1^{b−t} → b − t + s which imply that b − t + s = s + 1.

5 Reciprocal compositions and recursive conjugation

Let C = (…, 1^{a_{u}}, b_{v}, 1^{a_{u+1}}, b_{v+1}, …) be a composition of n such that a_{i}, b_{i} ≥ 2 for all i. We define the reciprocal of C, denoted by r(C), to be the composition obtained by replacing each string 1^{a_{i}} with a_{i} and each big part b_{i} with 1^{b_{i}}, i.e.,

r(C) = (…, a_{u}, 1^{b_{v}}, a_{u+1}, 1^{b_{v+1}}, …), a_{i}, b_{i} > 1.

Note that r(C) = ∅ if a_{i} < 2 for some i. Thus the reciprocal operation is an involution on the set of compositions with no adjacent big parts in which every string of 1’s occurs with multiplicity ≥ 2. If r(C) ≠ ∅, we call C a reciprocal composition.

For example, r((1^{2}, 4, 1^{2}, 3, 1^{3})) = (2, 1^{4}, 2, 1^{3}, 3), and r((1^{2}, 4, 1)) = ∅.

Let C = (1^{a_{1}}, b_{1}, …, 1^{a_{s}}, b_{s}). Then observe from (1) that when t = 0 in C^{(t)} we obtain r(C):

(C^{(t)})_{|t=0} = C^{(0)} = (a_{1} + 0, 1^{b_{1}−2(0)}, a_{2} + 2(0), …, a_{s} + 2(0), 1^{b_{s}−0})
= (a_{1}, 1^{b_{1}}, a_{2}, …, a_{s}, 1^{b_{s}})
= r(C).

However, the resulting expression for r(C) may not be defined.

Thus it is intuitive to define C^{(0)} as r(C), so that when r(C) ≠ ∅ we have

r(r(C)) = r(C^{(0)}) = (C^{(0)})^{(0)} = C.

Lemma 9. If C is t-conjugable, then C^{(j)} is reciprocal, where j = 1, 2, …, t − 1:

C^{(t)} ≠ ∅ ⟹ r(C^{(j)}) ≠ ∅, 1 ≤ j < t.  (7)

This follows from the defining inequalities for C^{(t)} in (1): each string of 1’s in C^{(j)} has the form 1^{b_{i}−2j}, i < r, or 1^{b_{r}−j}, and either exponent is at least 2 because b_{i} ≥ 2t and b_{r} ≥ t + 1 with j < t.

Equation (7) implies

ht(C) > t ⟺ r(C^{(t)}) ≠ ∅.

Proposition 10. Let C be a composition. Then

ht(C) ≥ t and ht(r(C)) ≥ u ⟹ ht(C^{(t)}) ≥ t + u.

In particular ht(C) ≥ t and r(C) ≠ ∅ ⟺ ht(C^{(t)}) > t.

Proof. We have that r(C) ≠ ∅ and ht(C) ≥ t ⟺ every 1^{a} has a > 1 ⟺ every boundary big part b in C^{(t)} satisfies b > t + 1 and every interior big part b satisfies b > 2t + 1 ⟺ ht(C^{(t)}) > t.

Note that (C^{(t)})′ ≠ C^{(t+1)}. The correct relation is

(C^{(t)})′ = r(C^{(t−1)}), t > 0.

This may be extended as follows:

Theorem 11. We have

(C^{(t)})^{(u)} = r(C^{(t−u)}), 0 ≤ u ≤ t.  (8)

Note that u = 0 and u = t require C^{(t)} and C to be reciprocal respectively.

Proof. Compute directly:

C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, b_{2}, …, 1^{a_{s}}, b_{s}). C^{(t)} = (a_{1} + t, 1^{b_{1}−2t}, a_{2} + 2t, 1^{b_{2}−2t}, …, a_{s} + 2t, 1^{b_{s}−t}). (C^{(t)})^{(u)} = (1^{a_{1}+t−u}, b_{1} − 2t + 2u, 1^{a_{2}+2t−2u}, …, b_{s} − t + u) = r(C^{(t−u)}).

The following restatement provides a recursive procedure for computing C^{(t)}.

Corollary 12. We have

C^{(t)} = r(C^{(t−u)})^{(u)}, 0 ≤ u ≤ t.  (9)

Note that because of (7), Equation (8) or (9) holds whenever C^{(t)} exists. The process can be iterated. Let t = t_{1} +⋯+t_{s}, t_{i} > 0, ∀ i. Then writing r(C^{(t_{i})})^{t_{j}} instead of (r(C^{(t_{i})}))^{t_{j}} we have

C^{(t)} = r(r(⋯ (r(C^{(t_{1})})^{(t_{2})} ⋯)^{(t_{s−1})})^{(t_{s})}),

where the reciprocal operation is applied s − 1 times.

For example we obtain the 5-conjugate of C = (1^{3}, 15, 1, 7) using the decomposition 5 = 2 + 1 + 2:

C^{(5)} = r(r(C′′)′)′′
= r(r((5, 1^{11}, 5, 1^{5}))′)′′
= r((1^{5}, 11, 1^{5}, 5)′)′′
= r((6, 1^{9}, 7, 1^{4}))′′
= (1^{6}, 9, 1^{7}, 4)′′
= (8, 1^{5}, 11, 1^{2}).

If C^{(t+1)} ≠ ∅, then (9) implies (C^{(t+1)})^{(t)} = r(C′), ∀ t ≥ 0. But when r(C) ≠ ∅, we have

(C^{(t)})^{(t+1)} = r(C)′.  (10)

Indeed since r(C) ≠ ∅ the following computation is justified by Proposition 10 when C = (1^{a_{1}}, b_{1}, 1^{a_{2}}, …, 1^{a_{r}}, b_{r}) with ht(C^{(t)}) > t:

r(C)′ = ((a_{1}, 1^{b_{1}}, a_{2}, …, a_{r}, 1^{b_{r}}))′
= (1^{a_{1}−1}, b_{1} + 2, 1^{a_{2}−2}, …, 1^{a_{r}−2}, b_{r} + 1)
= ((a_{1} + t, 1^{b_{1}−2t}, a_{2} + 2t, …, a_{r} + 2t, 1^{b_{r}−t}))^{(t+1)}
= (C^{(t)})^{(t+1)}.

Thus using (10) the reciprocal of a t-conjugable reciprocal composition has the following expression.

r(C) = ((C^{(t)})^{(t+1)})′.

In particular the following relation holds for every reciprocal composition C.

r(C) = ((C′)′′)′.

However, r(C)′ = (C′)′′ ⟺ ht(C′) > 1. Hence the next result follows.

Proposition 13. A composition C is reciprocal if and only if ht(C′) ≥ 2. Hence the number of reciprocal compositions of n is equal to the number of 2-conjugable compositions of n (cf. see (18)).

6 Zig-zag graphs and higher-order conjugates

Given a t-conjugable composition C we show how C^{(t)} is obtained using zig-zag graphs. The zig-zag graph of C will be denoted by ZG(C).

We emphasize that the zig-zag graph is primarily structured for the classical 1-conjugation. So C^{(t)} may only be obtained indirectly through ZG(C) when t > 1.

Generally C^{(t)} is obtained from ZG(C) by reading off the composition corresponding to the columns of the zig-zag graph of a certain (transitional) composition X_{t}(C) satisfying C^{(t)} = X_{t}(C)′, where ZG(X_{t}(C)) is visually compatible with ZG(C).

It is expected that X_{1}(C) = C. In general we set X_{t}(C) = r(C^{(t−1)}) because C^{(t)} = r(C^{(t−1)})′ from (9). The visual connection between ZG(C) and ZG(r(C^{(t−1)})) is evident from the following procedure.

Algorithm to obtain ZG(r(C^{(t−1)})) from ZG(C).

(i) Draw ZG(C) depicting the dots as open circles;

(ii) Shade the first or last b − t + 1 circles if the first or last row contains b > 1 circles, and shade the middle b − 2(t − 1) circles in every other row containing b > 1 circles.

(iii) Straighten each ‘zig-zag’ string of unshaded circles and align them vertically so that each string of shaded circles is in a different row from an unshaded circle.

The figure obtained in step (iii) is ZG(r(C^{(t−1)})), that is, ZG((C^{(t)})′).

This procedure is reversible as one may verify by switching the roles of C and C^{(t)}; note that r((C^{t})^{t−1}) = r(r(C′)) = C′.

We illustrate the process with C = (1^{2}, 8, 1, 6, 5). Assume that t = 3, that is, we wish to obtain C′′′ using ZG(C). Then the first diagram in Figure 2 shows ZG(C) after the execution of step (ii) of the algorithm; the second diagram shows ZG(r(C′′)).

Now the conjugate C′′′ is given by the composition corresponding to the columns of ZG(r(C′′)), that is, C′′′ = (5, 1^{2}, 7, 6, 1^{2}).

Note that r(C′′) = r((1^{2}, 8, 1, 6, 5)′′) = r((4, 1^{4}, 5, 1^{2}, 4, 1^{3})) = (1^{4}, 4, 1^{5}, 2, 1^{4}, 3) = (C′′′)′.

\begin{aligned}∘ \\ ∘ \\ ∘ & ∘ & • & • & • & • & ∘ & ∘ \\ & & & & & & & ∘ \\ & & & & & & & ∘ & ∘ & • & • & ∘ & ∘ \\ & & & & & & & & & & & & ∘ & ∘ & • & • & • \end{aligned}  \begin{aligned}∘ \\ ∘ \\ ∘ \\ ∘ \\ • & • & • & • \\ & & & ∘ \\ & & & ∘ \\ & & & ∘ \\ & & & ∘ \\ & & & ∘ \\ & & & • & • \\ & & & & ∘ \\ & & & & ∘ \\ & & & & ∘ \\ & & & & ∘ \\ & & & & • & • & • \end{aligned}

Figure 2: Zig-zag graphs of C = (1^{2}, 8, 1, 6, 5) and r(C′′)

7 Enumeration

Let c_{t}(n, k) denote the number of t-conjugable k-compositions of n. Thus c_{t}(n) = ∑_{k} c_{t}(n, k).

Note that if t > 1 and n − t + 1 ≤ k ≤ n − 1, then c_{t}(n, k) = 0 since the longest composition after (1^{n}) is (1, …, 1, t + 1) or (t + 1, 1, …, 1) and any composition of the form (1, …, 1, x), 2 ≤ x ≤ t is not t-conjugable.

7.1 Formulas for the number of conjugable compositions

Following MacMahon [12, 13] we demonstrate how to use the line graph to obtain the formula for c_{t}(n, k) for various types of compositions.

Let c_{t}(n, k | P) := number of t-conjugable k-compositions of n that satisfy condition P. For example, consider the function c_{t}(n, k | parts > 1). Then an enumerated composition has the form

C = (b_{1}, b_{2}, …, b_{k−1}, b_{k}), b_{1}, b_{k} ≥ t + 1, b_{i} ≥ 2t, 2 ≤ i ≤ k − 1.

The line graph of C contains n − 2t − 2 ≥ 0 central lines as shown in (11).

\underbrace{− − − ⋯ − −−}_{t+1 lines} \underbrace{\overbrace{− − − − ⋯ − − − −}^{n−2t−1 gaps}}_{n−2t−2 lines} \underbrace{− − − ⋯ − −−}_{t+1 lines}  (11)

In order to specify C we create k − 2 adjacent strings of lines in-between the n − 2t − 1 central gaps such that the length of each string is at least 2t. To achieve this we apply the known formula w(n, k, v) = \binom{n−(v−1)(k−1)}{k} which is the number of subsets \{n_{1}, …, n_{k}\} ⊆ {1, …, n} satisfying |n_{i} − n_{j}| ≥ v, i ≠ j [5].

Hence the desired number of compositions is given by w(n − 2t − 1, k − 1, 2t), that is,

c_{t}(n, k | parts > 1) = \binom{n − 2t − 1 − (2t − 1)(k − 2)}{k − 1}.  (12)

A similar method may be applied to the function c_{t}(n, k | 2c2 and s ones), that is, the number of t-conjugable 2c2 compositions of n into k parts containing s interior 1’s, s ≥ 0. Thus c_{t}(n, k | 2c2 and 0 ones) = c_{t}(n, k | parts > 1).

Using (11) we find that c_{t}(n, k | 2c2 and s ones) = \binom{k−2}{s}w(n − s − 2t − 1, k − s − 1, 2t), that is,

c_{t}(n, k | 2c2 and s ones) = \binom{k − 2}{s}\binom{n − s − 2t − 1 − (2t − 1)(k − s − 2)}{k − s − 1},

where n ≥ 2t + 2 + s + 2t(k − 1 − s), k > 1.

Further variations of the shape of C and the formulas are clearly possible.

For a general formula we need the generating function for c_{t}(n, k).

Theorem 14. Let n ≥ k > 1 be integers. Then for all integers t > 0,

∑_{n=k}^{∞} c_{t}(n, k)x^{n} = \frac{(x − x^{2} + x^{t+1})^{2}(x − x^{2} + x^{2t})^{k−2}}{(1 − x)^{k}} .

In particular,

∑_{n=k}^{∞} c_{1}(n, k)x^{n} = \frac{x^{k}}{(1 − x)^{k}} = ∑_{n=k}^{∞} \binom{n − 1}{k − 1}x^{n}.

Proof. We use the following decomposition of an enumerated composition C, where k > 1. C =(a composition into one part ∈ {1, t + 1, t + 2, … })

×(a (k − 2)-composition using the parts 1, 2t, 2t + 1, …)

×(a composition into one part ∈ {1, t + 1, t + 2, … }).

Hence the generating function is given by

(x + x^{t+1} + x^{t+2} + ⋯)(x + x^{2t} + x^{2t+1} + ⋯)^{k−2}(x + x^{t+1} + x^{t+2} + ⋯),

That is,

∑_{n=k}^{∞} c_{t}(n, k)x^{n} = (x + \frac{x^{t+1}}{1 − x})^{2} (x + \frac{x^{2t}}{1 − x})^{k−2}

which simplifies to the stated result.

Now if \frac{(x − x^{2} + x^{2t})^{k−2}}{(1 − x)^{k}} = ∑_{n≥k} V (n, k)x^{n}, then it is a routine process to show that

V_{t}(n, k) = ∑_{r=0}^{n−k+2} ∑_{j=0}^{n−k+2}(−1)^{r+j}\binom{k − 2}{r}\binom{n − j + 1}{k − 1}\binom{k − 2 − r}{j − r(2t − 1)}.  (13)

Therefore the full generating function is given by

∑_{n=k}^{∞} c_{t}(n, k)x^{n} = (x − x^{2} + x^{t+1})^{2} ∑_{n=k}^{∞} V_{t}(n, k)x^{n}.

= (x^{2} − 2x^{3} + x^{4} + 2x^{t+2} − 2x^{t+3} + x^{2t+2}) ∑_{n=k}^{∞} V_{t}(n, k)x^{n}.

This gives the following formula. Theorem 15. We have

c_{t}(n, k) =V_{t}(n − 2, k) − 2V_{t}(n − 3, k) + V_{t}(n − 4, k)
+ 2V_{t}(n − t − 2, k) − 2V_{t}(n − t − 3, k) + V_{t}(n − 2t − 2, k),

where V_{t}(n, k) is defined in (13).

In particular since c_{1}(n, k) = V_{1}(n − 2, k) we equate this with a known formula to get the identity:

\binom{n − 1}{k − 1} = ∑_{r=0}^{n−k} ∑_{j=0}^{n−k}(−1)^{r+j}\binom{k − 2}{r}\binom{n − j − 1}{k − 1}\binom{k − 2 − r}{j − r}.

The generating function for c_{t}(n) = ∑_{k} c_{t}(n, k) is given by

∑_{n=1}^{∞} c_{t}(n)x^{n} = (x + x^{2} + ⋯) + ∑_{k=2}^{∞} \frac{(x − x^{2} + x^{t+1})^{2}(x − x^{2} + x^{2t})^{k−2}}{(1 − x)^{k}}

= \frac{x + x^{2} − x^{t+1}}{1 − x − x^{t}} .

Theorem 16. We have

∑_{n=1}^{∞} c_{t}(n)x^{n} = \frac{x(1 + x − x^{t})}{1 − x − x^{t}}.

In order to obtain an explicit formula for c_{t}(n) we first consider the function A(n, t) given by

\frac{x}{1 − x − x^{t}} = ∑_{n=1}^{∞} A(n, t)x^{n}.  (14)

When t = 1 and t = 2 one immediately recognizes the generating functions of two famous enumerators in combinatorial mathematics, namely, A(n, 1) = 2^{n−1}, the number of all subsets of {1, …, n−1} or the number of all compositions of n; and A(n, 2) = F_{n}, the nth Fibonacci number (F_{1} = F_{2} = 1, F_{n} = F_{n−1} + F_{n−2}, n > 2).

For the general coefficient one can show that

A(n, t) = ∑_{i=0}^{⌊ \frac{n−1}{t} ⌋} \binom{n − 1 − (t − 1)i}{i}, n > 0,  (15)

which is a generalized ‘Narayana’s cows’ sequence [18, \underline{A000930}].

Since ∑_{n≥1} c_{t}(n)x^{n} = (1 + x − x^{t}) ∑_{n≥1} A(n, t)x^{n}, we obtain

c_{t}(n) = A(n, t) + A(n − 1, t) − A(n − t, t).  (16)

The formula (16) may be simplified using (15) and the Pascal triangle recurrence.

Theorem 17. Given any positive integers n, t with 1 ≤ t ≤ n − 2 we have

c_{t}(n) = 2 ∑_{i=0}^{⌊ \frac{n−2}{t} ⌋} \binom{n − 2 − (t − 1)i}{i},  (17)

where c_{t}(1) = 1, c_{t}(n) = 2, t ≥ n − 1.

In particular we see that c_{1}(n) = 2 · 2^{n−2} = 2^{n−1}, and

c_{2}(n) = 2 ∑_{i=0}^{⌊ \frac{n−2}{2} ⌋} \binom{n − 2 − i}{i} = 2F_{n−1}, n > 1.  (18)

7.1.1 Recurrence relations

Theorem 16 translates into the following recurrence relation but we also give a direct combinatorial proof.

Theorem 18. Given positive integers n, t with n ≥ 2t + 2, then

c_{t}(n) = c_{t}(n − 1) + c_{t}(n − t),
c_{t}(1) = 1, c_{t}(n) = 2, 1 ≤ n ≤ t + 1; c_{t}(n) = 2(n − t), t + 2 ≤ n ≤ 2t + 1.

Proof. Let H_{t}(n) be the set enumerated by c_{t}(n). A composition C = (u_{1}, u_{2}, …,) in H_{t}(n), falls under one of the four categories:

1. u_{1} = 1,

2. u_{1} = t + 1,

3. t + 2 ≤ u_{1} ≤ 2t, t > 1, and

4. u_{1} ≥ 2t + 1:

Delete u_{1} = 1 from C in (1) or subtract 1 from u_{1} in (3) to obtain a member of H_{t}(n − 1). Subtract t from u_{1} in (2) or (4) to obtain a member of H_{t}(n − t).

Conversely, if (e_{1}, e_{2}, …) ∈ H_{t}(n−1) satisfies e_{1} = 1 or e_{1} ≥ 2t, then C = (1, e_{1}, e_{2}, …) ∈ H_{t}(n), otherwise C = (1 + e_{1}, e_{2}, …) ∈ H_{t}(n). If (e_{1}, e_{2}, …) ∈ H_{t}(n − t), then (t + e_{1}, e_{2}, …) ∈ H_{t}(n).

The compositions (1^{n}) and (n) are t-conjugable for any integer t > 0. So by convention we set c_{1}(1) = 1 = c_{t}(1) and c_{t}(n) = 2, 1 ≤ n ≤ t + 1. Then for t + 2 ≤ n ≤ 2t + 1 we see that c_{t}(n) = c_{t}(n − 1) + 2, where C is obtained by adding 1 to the big part in a composition enumerated by c_{t}(n − 1) or by inserting 1 into (1^{n−1}) or by using a member of {(1^{n−t−1}, t + 1), (t + 1, 1^{n−t−1})}. Then the recurrence c_{t}(n) = c_{t}(n − 1) + 2, with c_{t}(t + 1) = 2, has the solution c_{t}(n) = 2(n − t).

Another recurrence is given in terms of the number of compositions with last part 1. Denote the number of compositions in H_{t}(n) with last part x by c_{t}(n)_{x}. Then

c_{t}(n) = 2c_{t}(n)_{1}, c_{t}(t)_{1} = 1.

Indeed we have c_{t}(n) = c_{t}(n)_{1} + c_{t}(n)_{>1}. But since every composition enumerated by c_{t}(n)_{>1} has a conjugate with last part 1, we see that c_{t}(n)_{>1} = c_{t}(n)_{1}. Hence the assertion follows.

7.2 Number of compositions with a fixed conjugate height

Let g_{t}(n, k) denote the number of k-compositions of n with conjugate height exactly t so that g_{t}(n) = ∑_{k} g_{t}(n, k).

The formulas for g_{t}(n, k) and g_{t}(n) are derived from those of c_{t}(n, k) and c_{t}(n) (cf. Equation (6)).

g_{t}(n, k) = c_{t}(n, k) − c_{t+1}(n, k), n ≥ t > 1,
g_{t}(n) = c_{t}(n) − c_{t+1}(n), n ≥ t > 1.  (19)

From Equations (19) and (17) we obtain Corollary 19. Given any positive integers n, t, then

g_{t}(n) = 2 ∑_{i=0}^{⌊ \frac{n−2}{t} ⌋} \binom{n − 2 − (t − 1)i}{i} − 2 ∑_{i=0}^{⌊ \frac{n−2}{t+1} ⌋} \binom{n − 2 − ti}{i}.

Note that g_{t}(n) > 0 only for n ≥ t + 2 in view of (3). The case t = 1 gives

g_{1}(n) = 2^{n−1} − 2F_{n−1}, n > 1.

The following result is a consequence of the generating function of c_{t}(n).

Corollary 20. We have

∑_{n=1}^{∞} g_{t}(n)x^{n} = \frac{2x^{t+2}(1 − x)}{(1 − x − x^{t})(1 − x − x^{t+1})}.

This generating function implies the following recurrence relation.

Corollary 21. Given integers n, t with t > 1, n ≥ 2t + 2, we have

g_{t}(n) = 2g_{t}(n − 1) − g_{t}(n − 2) + g_{t}(n − t) − g_{t}(n − t − 2) − g_{t}(n − 2t − 1),

g_{t}(n) = 0, for 1 ≤ n ≤ t + 1, g_{1}(4) = 4 and g_{t}(n) = 2, for t + 2 ≤ n ≤ 2t + 1.

An open problem is to find a direct combinatorial proof of Corollary 21.

Figure 3 shows some values of the enumeration functions c_{t}(n) and g_{t}(n) for small n. The second columns of the tables give the sequences c_{1}(n) = 2^{n−1} and g_{1}(n) = 2^{n−1} − 2F_{n−1}, n > 0, respectively.

We remark that the binomial coefficient sequences \binom{n}{k}, n ≥ k ≥ 0, in Sloane [18] are reproduced here in the form of the enumeration function c_{1}(n, k) (see Theorem 14).

The 2-conjugable compositions of n are enumerated by the double Fibonacci numbers 2F_{n} (\underline{A055389}). The sequences \frac{1}{2}c_{t}(n), t ≥ 1 occur in [18] as a family of sequences that satisfy the recurrence of Theorem 18: \underline{A000045}, \underline{A000079}, \underline{A000930}, \underline{A003269}, \underline{A003520}, \underline{A005708}, \underline{A005709}, \underline{A005710}, \underline{A005711}.

The functions c_{t}(n, 2), t = 1, 2, 3, n > t agree with \underline{A233583} for suitable sets of initial values, while c_{2}(n, 3), n > 7 coincides with \underline{A145018}. On the other hand, \frac{1}{2}g_{t}(n) is listed only for t = 1, namely \underline{A027934}.

Lastly we note that the following sequences are given in [18] as coefficients in the expansions of the rational function \frac{(1−x)}{1−x−x^{t}} , t > 3 (cf. Equation (14)): \underline{A017898}, \underline{A017899}, \underline{A017900}, \underline{A017901}, \underline{A017902}, \underline{A017903}, \underline{A017904}.

[figure: c_{t}(n); n; t; 1; 2; 3; 4; 5; 6; 7; 8; 1 1 1 1 1 1 1 1 1; 2 2 2 2 2 2 2 2 2; 3 4 2 2 2 2 2 2 2; 4 8 4 2 2 2 2 2 2; 5 16 6 4 2 2 2 2 2; 6 32 10 6 4 2 2 2 2; 7 64 16 8 6 4 2 2 2; 8 128 26 12 8 6 4 2 2; 9 256 42 18 10 8 6 4 2; 10 512 68 26 14 10 8 6 4; g_{t}(n); n; t; 1; 2; 3; 4; 5; 6; 7; 8; 1 0 0 0 0 0 0 0 0; 2 0 0 0 0 0 0 0 0; 3 2 0 0 0 0 0 0 0; 4 4 2 0 0 0 0 0 0; 5 10 2 2 0 0 0 0 0; 6 22 4 2 2 0 0 0 0; 7 48 8 2 2 2 0 0 0; 8 102 14 4 2 2 2 0 0; 9 214 24 8 2 2 2 2 0; 10 444 42 12 4 2 2 2 2]

Figure 3: The numbers c_{t}(n) and g_{t}(n) for 1 ≤ n ≤ 10 and 1 ≤ t ≤ 8

.

8 Combinatorial identities

Call a composition s-separated if every pair of consecutive big parts is separated by s ones, i.e., C has the form C = (…, b_{i}, 1^{s}, b_{i+1}, 1^{s}, b_{i+2}, 1^{s}, …), b_{j} > 1, ∀ j.

Then the following result is a consequence of conjugation.

Lemma 22. The number of t-conjugable 2c2 compositions of n that are s-separated is equal to the number of t-conjugable 1c1 compositions of n using only the parts 1 and 2t + s:

c_{t}(n | 2c2, s-separated) = c_{t}(n | 1c1, parts 1, 2t + s).

For a generating function proof we have

∑_{n=2}^{∞} c_{t}(n, k | 1c1, parts 1, 2t + s)x^{n} = (x)(x + x^{2t+s})^{k−2}(x), k ≥ 2;

∑_{n=r}^{∞} c_{t}(n | 2c2, s-separated, r parts > 1)x^{n}, r ≥ 2

= (x^{t+1} + x^{t+2} + ⋯)(x^{2t} + x^{2t+1} + ⋯)^{r−2}(x^{t+1} + x^{t+2} + ⋯)(x^{s})^{r−1}

= (\frac{x^{t+1}}{1 − x})^{2} (\frac{x^{2t}}{1 − x})^{r−2} x^{s(r−1)}.

The lemma then follows from the easily verified identity

∑_{k≥2} x^{2}(x + x^{2t+s})^{k−2} = \frac{x^{2}}{1 − x} + ∑_{r=2}^{∞} (\frac{x^{t+1}}{1 − x})^{2} (\frac{x^{2t}}{1 − x})^{r−2} x^{s(r−1)} = \frac{x^{2}}{1 − x − x^{2t+s}} ,

where (x^{2} + x^{3} + ⋯) = x^{2}/(1 − x) is the generating function for 1-part 2c2 compositions.

Since a positive integer may have different compositions of the form (2t, s) for different choices of t and s, the next assertion follows from Lemma 22.

Theorem 23. Let 2t + s = 2h + u for positive integers t, s, h, u. Then

c_{t}(n | 2c2, s-separated) = c_{h}(n | 2c2, u-separated), ∀ n > 1.

For example, since 5 = 2 · 1 + 3 = 2 · 2 + 1, we have c_{1}(n | 2c2, 3-separated) = c_{2}(n | 2c2, 1-separated) for all n > 1. Thus when n = 18, some (bijective) pairs of enumerated objects follow:

c_{1}(18 | 2c2, 3-separated) : (18), (4, 1^{3}, 11), (3, 1^{3}, 7, 1^{3}, 2), (2, 1^{3}, 3, 1^{3}, 2, 1^{3}, 2), …; c_{2}(18 | 2c2, 1-separated) : (18), (5, 1, 12), (4, 1, 9, 1, 3), (3, 1, 5, 1, 4, 1, 3), …. The case s = 0 in Lemma 22 leads to a 5-way combinatorial identity. We provide only

bijective proofs below.

Theorem 24. Let t be a positive integer. Then the following enumeration functions are equal.

(i) c_{t}(n | no 1’s);

(ii) c_{t}(n − 2 | parts 1, 2t);

(iii) c_{2t}(n | first part 1);

(iv) c_{t}(n − 1 | parts ≡ 1 (mod 2t));

(v) c_{t}(n + 2t − 2 | parts ≥ 2t).

The common value, from Equation (12), is given by

∑_{k} \binom{n − 2t − 1 − (2t − 1)(k − 2)}{k − 1}.

Proof. We will replace the lower-case letter c in each enumeration function with the uppercase C to denote the corresponding enumerated set.

(i) ⟺ (ii). There is an obvious bijection

α : C_{t}(n − 2 | parts 1, 2t) → C_{t}(n | 1c1, parts 1, 2t),  (20)

where α((c_{1}, …, c_{k})) = (1, c_{1}, …, c_{k}, 1). Thus (i) ⟺ (ii) is essentially a restatement of Lemma 22 with s = 0.

(ii) ⟺ (iii). By (20) and Lemma 22 it will suffice to establish the bijection

φ : C_{t}(n | 1c1, parts 1, 2t) → C_{2t}(n | 1st part 1).

Each U ∈ C_{t}(n | 1c1, parts 1, 2t) has the symbolic form

U = (1^{a_{1}}, 2t, 1^{a_{2}}, 2t, …, 1^{a_{r}}, 2t, 1^{a_{r+1}}), a_{1}, a_{r+1} ≥ 1, a_{i} ≥ 0, 1 < i < r + 1.

Now define φ as follows.

If r is even, then φ(U) = (1^{a_{1}}, 4t + a_{2}, 1^{a_{3}}, 4t + a_{4}, 1^{a_{5}}, …, 4t + a_{r}, 1^{a_{r+1}}), giving a 1c1 member of C_{2t}(n | 1st part 1).

If r is odd, then φ(U) = (1^{a_{1}}, 4t+a_{2}, 1^{a_{3}}, 4t+a_{4}, 1^{a_{5}}, …, 4t+a_{r−1}, 1^{a_{r}}, 2t+a_{r+1}), giving a 1c2 member of C_{2t}(n | 1st part 1). Clearly φ is one-to-one.

Conversely, since each interior big part b of any E ∈ C_{2t}(n | 1st part 1) satisfies b ≥ 4t, it splits into three symbolic parts (2t, 1^{a}, 2t), a ≥ 0. Correspondingly a boundary big part b of E satisfies b ≥ 2t + 1 and splits into (2t, 1^{a}), a > 0. So E can be transformed into a unique member of C_{t}(n | 1c1, parts 1, 2t). Hence the existence of φ^{−1} is guaranteed.

(ii) ⟺ (iv). An integer of the form 2tj + 1, j > 0 has a composition of the form (1, 2t, …, 2t). If we apply this transformation to each big part of C ∈ C_{t}(n − 1 | parts ≡ 1 (mod 2t)), and delete the first part (= 1), we obtain a unique member of C_{t}(n − 2 | parts 1, 2t).

(i) ⟺ (v). Since any (c_{1}, …, c_{k}) ∈ C_{t}(n | no 1’s) satisfies c_{1}, c_{k} > t and c_{i} ≥ 2t, 1 < i < k, it follows that (c_{1} + t − 1, c_{2}, …, c_{k−1}, c_{k} + t − 1) ∈ C_{t}(n + 2t − 2 | parts ≥ 2t).

9 Acknowledgment

The author is grateful to the editor and the referee for valuable comments which facilitated the revision of this paper. This work is based on research supported in part by the National Research Foundation of South Africa (Grant number 115024).

References

[1] A. K. Agarwal, n-color compositions, Indian J. Pure Appl. Math. 31 (2000), 1421–1427.

[2] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1998.

[3] E. A. Bender and E. R. Canfield, Locally restricted compositions I. Restricted adjacent differences, Electron. J. Combin. 12 (2005), Paper R57.

[4] E. A. Bender and E. R. Canfield, Locally restricted compositions II. General restrictions and infinite matrices, Electron. J. Combin. 16 (2009), Paper R108.

[5] C. Chuan-Chong and K. Khee-Meng, Principles and Techniques in Combinatorics, World Scientific, 1992.

[6] S. Eger, Restricted weighted integer compositions and extended binomial coefficients, J. Integer Seq. 16 (2013), Article 13.1.3.

[7] S. Eger, Some Elementary Congruences for the number of weighted integer compositions, J. Integer Seq. 18 (2015), Article 15.4.1.

[8] Y. Guo, Inverse-conjugate compositions with odd parts, Ars Combinatoria, 135 (2017), 93–102.

[9] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Discrete Mathematics and its Applications, CRC Press, 2010.

[10] S. Heubach and T. Mansour, Compositions of n with parts in a set, Congressus Numerantium 168 (2004), 127–143.

[11] B. Hopkins, Spotted tilings and n-color compositions, Integers 12B (2012), Paper A6.

[12] P. A. MacMahon, Combinatory Analysis, Volume 1, Cambridge University Press, 1915 [13] P. A. MacMahon, Memoir on the theory of the compositions of numbers, Philos. Trans.

Roy. Soc. London Ser. A, 184 (1893), 835–901.

[14] P. A. MacMahon, Second memoir on the theory of the compositions of numbers, Philos. Trans. Roy. Soc. London Ser. A, 207 (1908), 65–134.

[15] A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper A60.

[16] A. O. Munagi, Primary classes of compositions of numbers, Ann. Math. Inform. 41 (2013), 193–204.

[17] A. O. Munagi, Zig-zag graphs and partition identities of A. K. Agarwal, Ann. Comb. 19 (2015), 557–566.

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

2000 Mathematics Subject Classification: Primary: 05A17 Secondary: 11P81, 05A15, 05A19.

Keywords: composition, zig-zag graph, line graph, direct detection, conjugate, height, reciprocal.

(Concerned with sequences: \underline{A000045}, \underline{A000079}, \underline{A000930}, \underline{A003269}, \underline{A003520}, \underline{A005708}, \underline{A005709}, \underline{A005710}, \underline{A005711}, \underline{A017898}, \underline{A017899}, \underline{A017900}, \underline{A017901}, \underline{A017902}, \underline{A017903}, \underline{A017904}, \underline{A027934}, \underline{A055389}, \underline{A145018}, and \underline{A233583}.)

Received May 29 2018; revised versions received August 30 2018; August 31 2018. Published in Journal of Integer Sequences, November 25 2018.

Return to Journal of Integer Sequences home page.