The Nonassociativity of the Double Minus Operation

Jia Huang, Madison Mickey, and Jianbai Xu^{1} Department of Mathematics and Statistics University of Nebraska at Kearney Kearney, NE 68849 USA

                    huangj2@unk.edu
                mickeym2@lopers.unk.edu
                  xuj2@lopers.unk.edu

Abstract

The sequence \underline{A000975} in the Encyclopedia of Integer Sequences can be defined by A_{1} = 1, A_{n+1} = 2A_{n} if n is odd, and A_{n+1} = 2A_{n}+1 if n is even. This sequence satisfies other recurrence relations, admits some closed formulas, and is known to enumerate several interesting families of objects. We provide a new interpretation of this sequence using a binary operation defined by a ⊖ b := −a − b. We show that the number of distinct results obtained by inserting parentheses in the expression x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} equals A_{n}, by investigating the leaf depth in binary trees. Our result can be viewed as a quantitative measurement for the nonassociativity of the binary operation ⊖.

1 Introduction

The sequence \underline{A000975} in The On-Line Encyclopedia of Integer Sequences (OEIS) [6] starts with 1, 2, 5, 10, 21, 42, 85, . . .. With its nth term denoted by A_{n}, this sequence has the following (equivalent) characterizations.

1 The second and third authors were supported by the Undergraduate Research Fellows program of the University of Nebraska at Kearney.

• A_{1} = 1, A_{n+1} = 2A_{n} if n is odd, and A_{n+1} = 2A_{n} + 1 if n is even.

• A_{1} = 1 and A_{n} = 2^{n} − 1 − A_{n−1} for n ≥ 2.

• A_{1} = 1, A_{2} = 2, and A_{n} = A_{n−2} + 2^{n−1} for n ≥ 3.

• A_{n} is the positive integer with an alternating binary representation of length n.

There are also some known closed formulas for this sequence:

A_{n} = ⌊\frac{2^{n+1}}{3} ⌋ = \frac{2^{n+2} − 3 − (−1)^{n}}{6} = \begin{cases}\frac{2^{n+1} − 1}{3}, & if n is odd; \\ \frac{2^{n+1} − 2}{3}, & if n is even. \end{cases}  (1)

According to Hinz [2], this sequence dates back to 1769, when Lichtenberg studied it in connection with the Chinese Rings puzzle (baguenaudier). This sequence has many interesting interpretations, some of which are listed below.

• A_{n} is the number of moves required to solve the n-ring Chinese Rings puzzle [2].

• A_{n} is the distance between 0^{n} and 1^{n} in an n-bit binary Gray code [3, Ch. 1].

• A_{n} is the number of ways to partition n + 2 people sitting at a circular table into three nonempty groups with no two members of the same group seated next to each other [4].

The sequence \underline{A000975} also has connections to some other sequences in OEIS [6], such as \underline{A000217}, \underline{A048702}, \underline{A155051}, \underline{A265158}, and so on. See Stockmeyer [8] for more details.

In this paper we present a new interpretation for the sequence \underline{A000975} using a binary operation which is not associative. This naturally connects to the ubiquitous Catalan numbers and objects counted by Catalan numbers, such as binary trees.

In fact, let ∗ be a binary operation defined on a set S and let x_{0}, x_{1}, …, x_{n} be indeterminates taking values from S. It is well known that the number of ways to insert parentheses in the expression x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n} is the Catalan number C_{n} := \frac{1}{n+1} \binom{2n}{n}, which enumerates many families of interesting objects [7].

A natural question is how many distinct results can be obtained by inserting parentheses in x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n} for a given binary operation ∗. To be more precise, observe that each parenthesization of x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n} gives a function from S^{n+1} → S, and if two parenthesizations give the same function then they are said to be ∗-equivalent. Hein and the first author [1] defined C_{∗,n} to be the number of ∗-equivalence classes of parenthesizations of x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n}. This provides a quantitative measurement for the nonassociativity of ∗, as we have inequalities 1 ≤ C_{∗,n} ≤ C_{n} where the first equality holds if and only if ∗ is associative, i.e., (a ∗ b) ∗ c = a ∗ (b ∗ c) for all a, b, c ∈ S.

Lord [5] introduced the depth of nonassociativity of a binary operation and examined this depth for some elementary binary operations. The nonassociativity measurement C_{∗,n} is much finer than the depth of nonassociativity of ∗ since the latter can be written as inf{n + 1 : C_{∗,n} < C_{n}}. We have not found any other result on measuring nonassociativity of a binary operation in the literature.

For a family of binary operations defined by a ∗ b := ωa + b for a and b in the field ℂ of complex numbers, where ω := e^{2πi/k} is a primitive kth root of unity, Hein and the first author [1] determined the number C_{∗,n} and studied its connections to various objects counted by the Catalan numbers.

Now we define a binary operation by a⊖b := −a−b for all a, b in ℂ (or any other infinite field). We call this operation the double minus operation. It is not associative and we show that its nonassociativity measurement C_{⊖,n} equals A_{n}, the nth number in the sequence \underline{A000975}.

To prove this result, we first study the correspondence between parenthesizations and binary trees, and develop some lemmas on the depths of leaves in binary trees in Section 2. Here the depth of a leaf is the number of steps in the unique path from the root to this leaf.

We are interested in the leaf depths in binary trees because the results from parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} can be written in the form

±x_{0} ± x_{1} ± ⋯ ± x_{n}

where the sign of x_{i} is determined by the parity of the depth of the ith leaf in the corresponding binary tree. Combining this observation with the lemmas given in Section 2 we prove our main results in Section 3, which are summarized below.

We first establish a closed formula for the number C_{⊖,n,r} of distinct results obtained from parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} with exactly r plus signs. The result gives a truncated/modified version of the well-known Pascal triangle; see Table 1.

The number C_{⊖,n,r} refines the number C_{⊖,n} as C_{⊖,n} = ∑_{0≤r≤n+1} C_{⊖,n,r}. It also implies that C_{⊖,n} is determined by a “skipping sum” of binomial coefficients and we explicitly calculate it using cubic roots of unity. This proves the equality C_{⊖,n} = A_{n}. Our proof leads to a characterization of all distinct results from parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} using binary sequences, and hence gives another family of objects enumerated by the sequence \underline{A000975}. We also present a simpler proof for the equality C_{⊖,n} = A_{n}, which was pointed out to us by an anonymous referee, by showing the recurrence relation C_{⊖,n} = 2^{n} − 1 − C_{⊖,n−1} for n ≥ 2.

Finally, we provide some questions related to our results and proofs for future study in Section 4.

2 Leaf depths in binary trees

In this section we first recall some basic definitions and properties for binary trees and their connections to parenthesizations, and then develop some lemmas on the depths of leaves in binary trees.

A (full) binary tree is a rooted tree in which each node has either no child or two children ordered from left to right. A node without any child is called a leaf.

Let t be a binary tree. A subtree of t is a binary tree whose edges and nodes are contained in t. The left/right subtree of a node v in t is the maximal subtree of t rooted at the left/right child of v.

Let T_{n} be the set of all binary trees with n+1 leaves. For each t ∈ T_{n}, we label the leaves 0, 1, …, n from left to right, or more precisely, in the preorder of t. The depth of leaf i in t, denoted by d_{i}(t), is the length of the unique path from the root of t down to leaf i. The depth sequence of t is defined as d(t) = (d_{0}(t), d_{1}(t), …, d_{n}(t)).

Next, we introduce a binary operation ∧ for binary trees. If s ∈ T_{m} and t ∈ T_{n} then define s ∧ t to be the binary tree in T_{m+n+1} whose root has left subtree s and right subtree t.

Proposition 1. If s ∈ T_{m} and t ∈ T_{n} then the depth sequence of s ∧ t is

d(s ∧ t) = (d_{0}(s) + 1, …, d_{m}(s) + 1, d_{0}(t) + 1, …, d_{n}(t) + 1).

Proof. The result follows immediately from the construction of s ∧ t.

Example 2. Figure 1 illustrates binary trees s ∈ T_{3}, t ∈ T_{2}, and s ∧ t ∈ T_{6}. One sees that d(s) = (2, 3, 3, 1), d(t) = (2, 2, 1), and d(s ∧ t) = (3, 4, 4, 2, 3, 3, 2).

\begin{matrix}_{_{0 _{1 2}} 3} & _{0 1} 2 & _{_{_{0 _{1 2}} 3} _{_{4 5} 6}} \\ s & t & s ∧ t \end{matrix}

Figure 1: A binary operation on binary trees

Let ∗ be a binary operation on a set S and let x_{0}, x_{1}, …, x_{n} be S-valued indeterminates. There are different ways to insert parentheses in the expression x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n}. These parenthesizations of x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n} are enumerated by the Catalan number C_{n}. Moreover, the parenthesizations of x_{0} ∗ x_{1} ∗ ⋯ ∗ x_{n} are naturally in bijection with binary trees in T_{n}, since these binary trees are precisely the results from parenthesizing t_{0} ∧ t_{1} ∧ ⋯ ∧ t_{n}, where t_{0}, t_{1}, …, t_{n} all consist of a single node.

Example 3. We list all binary trees in T_{3} and their corresponding parenthesizations in Figure 2. These binary trees have depth sequences (3, 3, 2, 1), (2, 2, 2, 2), (2, 3, 3, 1), (1, 3, 3, 2), and (1, 2, 3, 3), respectively.

\begin{matrix}_{_{_{0 1} 2} 3} & _{_{0 1} _{2 3}} & _{_{0 _{1 2}} 3} & _{0 _{_{1 2} 3}} & _{0 _{1 _{2 3}}} \\ ↕ & ↕ & ↕ & ↕ & ↕ \\ ((x_{0}∗x_{1})∗x_{2})∗x_{3} & (x_{0}∗x_{1})∗(x_{2}∗x_{3}) & (x_{0}∗(x_{1}∗x_{2}))∗x_{3} & x_{0}∗((x_{1}∗x_{2})∗x_{3}) & x_{0}∗(x_{1}∗(x_{2}∗x_{3})) \end{matrix}

Figure 2: Correspondence between binary trees and parenthesizations

In the remainder of this section we give some lemmas on leaf depths in binary trees.

Lemma 4. For all n ≥ 0 and 0 ≤ r ≤ n + 1, there exists a binary tree t ∈ T_{n} with exactly r leaves of even depth only if n + r ≡ 1 (mod 3).

Proof. We induct on n. The case n = 0 is trivial. Assume n ≥ 1, 0 ≤ r ≤ n + 1, and there exists a binary tree t ∈ T_{n} with exactly r leaves of even depth. Let t_{1} and t_{2} be the left and right subtrees of the root of t. For i = 1, 2, let n_{i} + 1 be the number of leaves in t_{i} and let r_{i} be the number of leaves of even depth in t_{i}. Since t = t_{1} ∧ t_{2}, we have

n_{1} + 1 + n_{2} + 1 = n + 1 and r_{1} + r_{2} = n + 1 − r

where the second equation follows from Proposition 1. We also have

n_{1} + r_{1} ≡ 1 (mod 3) and n_{2} + r_{2} ≡ 1 (mod 3)

by the induction hypothesis. Therefore

n + r = 2(n_{1} + n_{2}) + 3 − (r_{1} + r_{2}) ≡ 2(n_{1} + n_{2} + r_{1} + r_{2}) ≡ 1 (mod 3).

This completes the proof.

Lemma 5. For all n ≥ 1 and t ∈ T_{n}, we have d_{j}(t) = d_{j+1}(t) for some j ∈ {0, 1, …, n − 1}.

Proof. Consider the leftmost leaf j with the largest depth among all leaves of t. The sibling of j, i.e., the other child of the parent of j, must be a leaf (otherwise the depth of j is not the largest) and to the right of j (otherwise j is not the leftmost leaf with the largest depth). It follows that the sibling of j is the leaf j + 1 and d_{j}(t) = d_{j+1}(t).

Let n ≥ 0. We say a binary sequence (d_{0}, d_{1}, …, d_{n}) ∈ {0, 1}^{n+1} is non-alternating if n ≥ 1 implies d_{j} = d_{j+1} for some j ∈ {0, 1, …, n − 1}, and say it is admissible if it is non-alternating and satisfies

n + |{i : 0 ≤ i ≤ n, d_{i} = 0}| ≡ 1 (mod 3).

Write (a_{0}, a_{1}, …, a_{n}) ≡ (b_{0}, b_{1}, …, b_{n}) (mod m) if a_{i} ≡ b_{i} (mod m) for all i ∈ {0, 1, …, n}.

Lemma 6. Let n ≥ 0 and suppose (d_{0}, d_{1}, …, d_{n}) ∈ {0, 1}^{n+1} is admissible. Then there exists a binary tree t ∈ T_{n} such that d(t) ≡ (d_{0}, d_{1}, …, d_{n}) (mod 2).

Proof. We induct on n. The result holds for n = 0 since the only admissible sequence in {0, 1}^{1} is (0), which is the depth sequence of the unique binary tree in T_{0}.

For n ≥ 1, suppose (d_{0}, d_{1}, …, d_{n}) ∈ {0, 1}^{n+1} is admissible, i.e., it is non-alternating and satisfies n + r ≡ 1 (mod 3), where r := |{i : 0 ≤ i ≤ n, d_{i} = 0}|. This sequence must contain a run of all zeros or all ones of length at least two. Replacing an adjacent pair of zeros (or ones, resp.) in this run with a one (or zero, resp.) gives a new sequence (d′_{0}, …, d′_{n−1}) ∈ {0, 1}^{n}, which satisfies

n − 1 + |{i : 0 ≤ i ≤ n, d′_{i} = 0}| ≡ n − 1 + r + 1 ≡ 1 (mod 3).

We show that it is always possible to make the new sequence (d′_{0}, …, d′_{n−1}) non-alternating.

In fact, we may assume (d_{0}, …, d_{n}) contains a run of zeros of length at least two, without loss of generality. If this run of zeros is preceded (or followed, resp.) by a one, then we can replace the first (or last, resp.) two zeros in this run with a one and get a non-alternating sequence (d′_{0}, …, d′_{n−1}). If it is not preceded nor followed by a one, then we must have d_{0} = d_{1} = ⋯ = d_{n} = 0. The condition n + r ≡ 1 (mod 3) implies n ≡ 0 (mod 3) and thus n ≥ 3. Then replacing the first two zeros in (d_{0}, …, d_{n}) with a one gives a non-alternating sequence (d′_{0}, …, d′_{n−1}). Some examples are given below.

1\underline{00}1100 → 1\underline{1}1100 1010\underline{00}1 → 1010\underline{1}1 0000 → \underline{1}00

Now we know that (d′_{0}, …, d′_{n−1}) is admissible. By the induction hypothesis, there exists a binary tree t′ ∈ T_{n−1} such that d(t′) ≡ (d′_{0}, …, d′_{n−1}) (mod 2). The construction of the sequence (d′_{0}, …, d′_{n−1}) implies that d′_{i} is obtained by switching a pair of adjacent zeros (or ones, resp.) in (d_{0}, …, d_{n}) to a one (or zero, resp.) for some i ∈ {0, 1, …, n − 1}. Then appending two children to the ith leaf of t′ gives a binary tree t ∈ T_{n} satisfying d(t) ≡ (d_{0}, …, d_{n}) (mod 2).

3 Main results

In this section we prove that the number C_{⊖,n} of equivalence classes of parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} equals A_{n}, the nth term of the sequence \underline{A000975}.

Since C_{⊖,n} also enumerates distinct results from parenthesizing x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n}, it is refined by the number C_{⊖,n,r} of distinct results from parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} with exactly r plus signs. We have

C_{⊖,n} = ∑_{0≤r≤n+1} C_{⊖,n,r}.  (2)

We can establish a closed formula for the number C_{⊖,n,r}, thanks to the following observation.

Proposition 7. A parenthesization of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} equals

(−1)^{d_{0}(t)}x_{0} + (−1)^{d_{1}(t)}x_{1} + ⋯ + (−1)^{d_{n}(t)}x_{n}

where t ∈ T_{n} is the binary tree corresponding to this parenthesization.

Proof. If a parenthesization of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} corresponds to a binary tree t ∈ T_{n}, then expanding this parenthesization using the definition a⊖b := −a−b, one sees that x_{i} receives d_{i}(t) many negative signs for all i. The result follows.

By Proposition 7, C_{⊖,n,r} enumerates binary trees in T_{n} with exactly r leaves of even depth. Using this observation, we compute the number C_{⊖,n,r} for 0 ≤ n ≤ 12 and 0 ≤ r ≤ n + 1 and record the result in Table 1, whose rows and columns are indexed by n and r, respectively.

r  0 1 2 3 4 5 6  7  8 9 10 11 12 13
C_{⊖,0,r}  1
C_{⊖,1,r} 1
C_{⊖,2,r}  2
C_{⊖,3,r} 4 1
C_{⊖,4,r} 1  9
C_{⊖,5,r}  15  6
C_{⊖,6,r}  7  34  1
C_{⊖,7,r} 1  56  28
C_{⊖,8,r}  36  125  9
C_{⊖,9,r}  10  210  120  1
C_{⊖,10,r} 1  165  461  55
C_{⊖,11,r}  66  792  495  12
C_{⊖,12,r}  13  715  1715  286  1
Table 1: C_{⊖,n,r} for 0 ≤ n ≤ 12 and 0 ≤ r ≤ n + 1

In this table, an empty spot means zero, a black entry equals \binom{n+1}{r}, and a red entry equals \binom{n+1}{r} − 1. Table 1 can be viewed as a truncated/modified version of the well-known Pascal triangle and suggests a closed formula for C_{⊖,n,r}.

Theorem 8. For n ≥ 1 and 0 ≤ r ≤ n + 1 we have

C_{⊖,n,r} = \begin{cases}\binom{n + 1}{r}, & if n + r ≡ 1 (mod 3) and n ≠ 2r − 2; \\ \binom{n + 1}{r} − 1, & if n + r ≡ 1 (mod 3) and n = 2r − 2; \\ 0, & if n + r ≢ 1 (mod 3). \end{cases}

Proof. Lemma 4 gives C_{⊖,n,r} = 0 if n + r ≢ 1 (mod 3). Assume n + r ≡ 1 (mod 3) below.

By definition, C_{⊖,n,r} ≤ \binom{n+1}{r}. Lemma 5 and 6 imply that \binom{n+1}{r} − C_{⊖,n,r} equals the number of sequences d := (d_{0}, d_{1}, …, d_{n}) ∈ {0, 1}^{n+1} such that {i : 0 ≤ i ≤ n, d_{i} = 0}| = r and d_{j} ≠ d_{j+1} for all j ∈ {0, 1, …, n − 1}. Such a sequence d must be alternating and we distinguish the following cases. Case 1. If d = (1, 0, 1, 0, …, 0, 1) then n = 2r and n + r = 3r ≢ 1 (mod 3). Case 2. If d = (1, 0, 1, 0, …, 1, 0) or d = (0, 1, 0, 1, …, 0, 1) then we have n = 2r − 1 and n + r ≡ 3r − 1 ≢ 1 (mod 3). Case 3. If d = (0, 1, 0, 1, …, 1, 0) then n = 2r − 2 and n + r ≡ 3r − 2 ≡ 1 (mod 3).

Thus

\binom{n + 1}{r} − C_{⊖,n,r} = \begin{cases}0, & n ≠ 2r − 2; \\ 1, & n = 2r − 2. \end{cases}

This establishes the desired formula for C_{⊖,n,r}.

Now we are ready to give the main result on the number C_{⊖,n}.

Theorem 9. For all n ≥ 1 we have C_{⊖,n} = A_{n}.

Proof. Let ω = e^{2πi/3} be a primitive cubic root of unity in ℂ. Substituting x = 1, ω, ω^{2} in the binomial expansion of (1 + x)^{n} we obtain

2^{n} + ω^{−k}(1 + ω)^{n} + ω^{k}(1 + ω^{2})^{n} = ∑_{i} \binom{n}{i}(1 + ω^{i−k} + ω^{2i+k}).

We have

1 + ω^{i−k} + ω^{2i+k} = \begin{cases}1 + 1 + 1 = 3, & if i ≡ k (mod 3), \\ 1 + ω + ω^{2} = 0, & otherwise. \end{cases}

Hence

∑_{i≡k (mod 3)} \binom{n}{i} = \frac{2^{n} + ω^{−k}(1 + ω)^{n} + ω^{k}(1 + ω^{2})^{n}}{3} .  (3)

For n ≥ 1, let

C′_{⊖,n} := \begin{cases}C_{⊖,n}, & if n is odd; \\ C_{⊖,n} + 1, & if n is even. \end{cases}

It follows from Equation (2), Theorem 8, and Equation (3) that

C′_{⊖,n} = ∑_{r≡1−n (mod 3)} \binom{n + 1}{r}

= \frac{2^{n+1} + ω^{n−1}(1 + ω)^{n+1} + ω^{1−n}(1 + ω^{2})^{n+1}}{3}

= \frac{2^{n+1} + ω^{n−1}(−ω^{2})^{n+1} + ω^{1−n}(−ω)^{n+1}}{3}

= \frac{2^{n+1} + (−1)^{n+1}ω + (−1)^{n+1}ω^{2}}{3} = \frac{2^{n+1} + (−1)^{n}}{3} .

This implies that C_{⊖,n} satisfies the same closed formulas (1) as A_{n}.

We are grateful to the anonymous referee for pointing out the following simpler proof of Theorem 9.

Another Proof. We have C_{⊖,1} = A_{1} = 1. For n ≥ 2, applying Theorem 8 we obtain

C_{⊖,n} + C_{⊖,n−1} + 1 = ∑_{r≡1−n (mod 3)} \binom{n + 1}{r} + ∑_{r≡2−n (mod 3)} \binom{n}{r}

= ∑_{r≡1−n (mod 3)} (\binom{n}{r − 1} + \binom{n}{r}) + ∑_{r≡2−n (mod 3)} \binom{n}{r}

= ∑_{0≤r≤n} \binom{n}{r} = 2^{n}.

Thus C_{⊖,n} satisfies the same recurrence relation as A_{n} = 2^{n} − 1 − A_{n−1} for n ≥ 2.

Finally, we characterize all distinct results from parenthesizing x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n}.

Proposition 10. The results from parenthesizing x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} are precisely

(−1)^{d_{0}}x_{0} + (−1)^{d_{1}}x_{1} + ⋯ + (−1)^{d_{n}}x_{n}

for all admissible sequences (d_{0}, d_{1}, …, d_{n}) ∈ \{0, 1\}^{n+1}. Consequently, sequence \underline{A000975} enumerates admissible binary sequences.

Proof. Any result from parenthesizing x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} can be written as

(−1)^{d_{0}(t)}x_{0} + (−1)^{d_{1}(t)}x_{1} + ⋯ + (−1)^{d_{n}(t)}x_{n}

where t ∈ T_{n} corresponds to this parenthesization. Let (d_{0}, …, d_{n}) ∈ {0, 1}^{n+1} such that (d_{0}, …, d_{n}) ≡ (d_{0}(t), …, d_{n}(t)) (mod 2). Then (d_{0}, …, d_{n}) must be admissible by Lemma 4 and 5.

Conversely, if (d_{0}, …, d_{n}) ∈ {0, 1}^{n+1} is admissible then there exists t ∈ T_{n} such that d(t) ≡ (d_{0}, …, d_{n}) (mod 2) by Lemma 6. Thus the parenthesization of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} corresponding t equals (−1)^{d_{0}}x_{0} + (−1)^{d_{1}}x_{1} + ⋯ + (−1)^{d_{n}}x_{n}.

4 Questions

In this section we present some problems for future study.

First, similarly to many other enumeration problems, it would be nice to have explicit bijections between distinct results from parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n}, which are naturally encoded by admissible sequences in {0, 1}^{n+1}, and other objects enumerated by sequence \underline{A000975}, such as those mentioned in Section 1. Such bijections may help find a direct proof for the closed formulas of C_{⊖,n} without using the refined number C_{⊖,n,r}.

Next, C_{⊖,n} satisfies the recurrent relations for A_{n} mentioned in Section 1 since C_{⊖,n} = A_{n}. The second proof of Theorem 9 establishes one of these recurrence relations directly for C_{⊖,n}. How about the other recurrent relations?

It also seems to natural to explore the generating function

C_{⊖}(x, y) := ∑_{n≥0} ∑_{0≤r≤n+1} C_{⊖,n,r}x^{n}y^{r}.

Its specializations C_{⊖}(x, 1) is known to be

C_{⊖}(x, 1) = ∑_{n≥0} C_{⊖,n}x^{n} = \frac{1}{(1 + x)(1 − x)(1 − 2x)}

which gives the generating function for the sequence \underline{A000975} (although A_{0} = 0 differs from C_{⊖,0} = 1).

Lastly, the results from parenthesizations of x_{0} ⊖ x_{1} ⊖ ⋯ ⊖ x_{n} are determined by the depths of leaves in the corresponding binary trees. What is the average leaf depth in all binary trees with n + 1 leaves?

5 Acknowledgments

We are grateful to the anonymous referee for providing many valuable suggestions, which helped us improve the organization of this paper and simplified some proofs.

References

[1] N. Hein and J. Huang, Modular Catalan numbers, Euro. J. Comb. 61 (2017), 197–218.

[2] A. M. Hinz, The Lichtenberg sequence, Fibonacci Quart. 55 (2017), 2–12.

[3] A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi—Myths and Maths, Springer, 2013.

[4] D. E. Knuth and O. P. Lossers, Problem 11151: partitions of a circular set, Amer. Math. Monthly 114 (2007), 265–266.

[5] N. J. Lord, Non-associative operations, Math. Mag. 60 (1987), 174–177.

[6] N. J. Sloane, ed., The On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2017.

[7] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[8] P. K. Stockmeyer, An exploration of sequence A000975, Fibonacci Quart. 55 (2017), 174–185.

2010 Mathematics Subject Classification: Primary 05A15. Keywords: binary tree, leaf depth, binary sequence, nonassociativity, parenthesization.

(Concerned with sequences \underline{A000217}, \underline{A000975}, \underline{A048702}, \underline{A155051}, and \underline{A265158}.)

Received May 27 2017; revised versions received August 31 2017; October 13 2017. Published in Journal of Integer Sequences, October 29 2017.

Return to Journal of Integer Sequences home page.