On the Unimodality of Convolutions of Sequences of Binomial Coefficients

Tricia Muldoon Brown Department of Mathematical Sciences Georgia Southern University 11935 Abercorn Street Savannah, GA 31419 USA

                  tmbrown@georgiasouthern.edu

Abstract We provide necessary and sufficient conditions on the unimodality of a convolution of two sequences of binomial coefficients preceded by a finite number of ones. These convolution sequences arise as rank sequences of posets of vertex-induced subtrees for a particular class of trees. The number of such trees whose poset of vertex-induced subgraphs containing the root is not rank unimodal is determined for a fixed number of vertices i.

1 Introduction

Unimodality of a sequence is an often-studied property where we say a sequence {s}_{i≥0} is unimodal if for some k ≥ 0, we have

s_{0} ≤ ⋯ ≤ s_{k−1} ≤ s_{k} ≥ s_{k+1} ≥ s_{k+2} ≥ · · · .

A classic example of a unimodal sequence is the sequence of binomial coefficients (\binom{n}{i})_{i≥0}. The question of unimodality of a sequence is a classic combinatorial problem. Stanley [10] provided a toolbox of techniques for proving unimodality and log-concavity which was updated by Brenti [3]. Further, several researchers have previously studied unimodality of other sequences involving binomial coefficients, including Tanny and Zuker [13] who establish the log-concavity and hence the unimodality of the sequence (\binom{n−r}{r})_{r≥0}. Belbachir, Bencherif, and Szalay [1] find similar results for the sequence (\binom{n+k}{βk})_{k≥0} for some natural number β ≥ 2. Their conjecture on unimodality along a ray of Pascal’s triangle is proven by Su and Wang [12]. Using the reflection principle, Sagan [7] shows the unimodality of a sequence of products of binomial coefficients (\binom{n}{ℓ−i}\binom{n}{i})_{0≤i≤ℓ} for any n and ℓ, as well as the sequence of differences of products (\binom{n}{ℓ−k}\binom{n}{k} − \binom{n}{ℓ−k−1}\binom{n}{k−1})_{k≥0}. In particular, here we are interested in the unimodality of the convolution of two sequences of binomial coefficients preceded by a finite number of ones. We define two sequences and their convolution as follows:

Definition 1. For integers m, n, p, q ≥ 0, let

(s_{i})_{i≥1} = (\underbrace{1, 1, …, 1}_{p}, \binom{m}{0}, \binom{m}{1}, …, \binom{m}{m}, 0, 0, …)

and

(t_{i})_{i≥1} = (\underbrace{1, 1, …, 1}_{q}, \binom{n}{0}, \binom{n}{1}, …, \binom{n}{n}, 0, 0, …) .

Then define the sequence (r_{i})_{i≥1} to be the convolution of (s_{i})_{i≥1} and (t_{i})_{i≥1}; that is, for i ≥ 1,

r_{i} = ∑_{j=1}^{i} s_{j} · t_{i−j+1}.

The main result provides necessary and sufficient conditions for (r_{i})_{i≥1} to be unimodal.

Theorem 2. For integers m ≥ n > 0 and p, q ≥ 0, the sequence (r_{i})_{i≥1} unimodal if and only if at least one of the following conditions hold:

i. m > q,

ii. n > p,

iii. m = n = 2, or

iv. n = 1.

As we shall see, the sequence (r_{i})_{i≥1} is motivated by graph theoretical objects, so in Section 2 we formally define a class of trees composed of two broom graphs and the associated poset of connected, vertex-induced subgraphs, determining the rank sequence and sequence of first differences. Section 3 provides some intermediate results on sequences of sums and differences of binomial coefficients, while Section 4 proves the main result and consequently an analogous result for a poset of connected, vertex-induced subgraphs of two broom graphs.

We conclude in Section 5 with a closed formula to count the number of such trees with a fixed number of vertices whose poset is not rank unimodular. We also note, throughout, m, n, p and q will be non-negative integers, r will always refer to the root vertex of the tree in question, and all subtrees will be connected.

2 Rank sequences and operations on rooted trees

Given a finite connected graph G, let C(G) denote the poset of all connected, vertex-induced subgraphs of G partially ordered by inclusion. This poset has been investigated by Leclerc [6] and Trotter and Moore [14], respectively, who give the dimension of this poset in the case of trees and graphs, respectively. These subgraph posets appeared more recently in a problem solved by Steelman [11] who gave conditions for when C(G) is a lattice. Further work has been done by Kézdy and Seif [5] on isomorphism conditions, and Vince and Wang [15] for an infinite set of non-Sperner subgraph posets. Dropping the condition that the subgraphs must be vertex-induced, Smith and Tomon [9] prove the poset of all connected subgraphs is Sperner. Here we wish to consider a class of vertex-induced, connected subgraph posets. Suppose T is a rooted tree. Let C(T, r) be the poset of connected, vertex-induced subtrees of G containing the root r partially ordered by inclusion. This poset and the more general poset were studied by Jacobson, Kézdy, and Seif [4] using the poset C(T, r) to show C(G) need not be Sperner.

Each poset C(T, r) has an associated sequence.

Definition 3. The rank sequence (r_{i})_{i≥0} of a poset P is given by the number of elements of rank i in the poset. These values r_{i} are also called Whitney numbers of the poset. A poset is rank unimodal if for some 0 ≤ k ≤ n, the rank sequence is unimodal.

In particular, the Whitney number r_{i} of C(T, r) is given by the number of connected, vertex-induced subtrees of T rooted at the root vertex with exactly i vertices.

Examples of rank unimodal posets are found in many commonly studied posets, such as the Boolean lattice and its q-analogues, as well as the partition lattice. The goal to characterize all trees whose poset of connected, vertex-induced subgraphs is unimodal was proposed by Jacobson, Kézdy, and Seif [4] . They provide the only example of a tree whose vertex-induced subposet C(T, r) is not unimodal when the number of vertices in the tree is less than or equal to 11, leading to questions on the prevalence of such non-unimodal posets. This example, see Figure 1, is the motivating example for this work.

We begin by defining a simple tree which is illustrated in Fig 2.

Definition 4. Given integers m > 0 and k ≥ 0, the broom graph, B_{m,k}, is a rooted, directed tree consisting of a path of length k directed into a vertex with m pendant vertices. The root is the origin of the path and all edges are directed away from the root.

It is not difficult to determine the rank sequence for the poset of connected, vertex-induced subtrees of a broom graph.

Figure 1: The rooted tree on 11 vertices whose poset C(T, r) has the non-unimodal rank sequence (1, 2, 3, 6, 10, 11, 10, 11, 10, 5, 1).

\begin{matrix}x_{0} \\ x_{1} \\ x_{p−1} \\ x_{p} \\ x_{p+1} \\ x_{p+2} \\ x_{p+m} \end{matrix}

Figure 2: The broom graph B_{m,p} Lemma 5. For m > 0 and p ≥ 0, the poset of connected, vertex-induced subtrees containing the root of a broom graph, C(B_{m,p}, r), is rank unimodal.

Proof. A broom without a handle, B_{m,0}, consists of a root vertex and m pendant vertices. The rank sequence of C(B_{m,0}, r) is given by the binomial coefficients, as the rooted subtrees with i vertices are chosen by selecting i − 1 edges from the set of m pendant edges, that is, for B_{m,0} we have r_{i} = \binom{m}{i−1}. More generally if the broom has a handle of length p and m pendant vertices, because all subtrees in B_{m,p} must be rooted, there is exactly one subtree with i vertices for 1 ≤ i ≤ p. All remaining subtrees in B_{m,p} with i > p vertices are subtrees of B_{m,0} with i − p vertices and a handle of p vertices. Thus the rank sequence is

(\underbrace{1, 1, …, 1}_{p}, \binom{m}{0}, \binom{m}{1}, …, \binom{m}{m}) .

As mentioned in Section 1, it is well-known that binomial coefficients are unimodal, see Stanley [10] for example, and hence C(B_{m,p}, r) is rank unimodal.

As the example provided by Jacobson, Kézdy, and Seif is two broom graphs, B_{3,2} and B_{2,3}, whose root vertices have been identified, the question we wish to consider is for a tree T composed of two broom graphs B_{m,p} and B_{n,q} whose root vertices have been identified, when is the subtree poset C(T, r) rank unimodal?

We will classify a set of rooted trees by the unimodality of their rank sequences, so first we formalize an operation on rooted trees.

Definition 6. We merge two rooted trees, T_{1} and T_{2}, respectively, with root vertices, v_{1} and v_{2}, respectively, by identifying the roots v_{1} = v_{2}. We denote the new tree as T_{1} · T_{2}.

This operation on a pair of trees leads to an analogous operation on the rank sequences of their posets of vertex-induced subtrees containing the root.

Lemma 7. If (t_{i})_{i≥1} is the rank sequence of C(T, r_{T}) for a rooted tree T and (s_{i})_{i≥1} is the rank sequence of C(S, r_{S}) for a rooted tree S, then the rank sequence (r_{i})_{i≥1} of C(T · S, r) is given by the convolution r_{i} = ∑_{j=0}^{i−1} t_{j+1}s_{i−j}.

Proof. Let T and S be two rooted trees. Choosing a rooted subtree consisting of i vertices from T · S is equivalent to choosing a rooted subtree of j + 1 vertices from T and a rooted subtree of i − j vertices from S for all 0 ≤ j ≤ i − 1.

Thus we see the sequence (r_{i})_{i≥i} defined in Section 1 is precisely the rank sequence of the poset C(B_{m,p} · B_{n,q}, r). The following proposition provides a more specific description of (r_{i})_{i≥1} in terms of binomial coefficients.

Proposition 8. For integers m, n > 0 and p, q ≥ 0, let (r_{i})_{i≥1} be the rank sequence of C(B_{m,p} · B_{n,q}, r), the poset of vertex-induced subtrees including the root of the merge of two broom graphs. If p ≤ q, then

r_{i} = \begin{cases}i, & for i = 1, 2, …, p; \\ p + ∑_{j=0}^{i−p−1} \binom{m}{j}, & for i = p + 1, p + 2, …, q; \\ ∑_{j=0}^{i−q−1} \binom{n}{j} + (q + p − i) + ∑_{j=0}^{i−p−1} \binom{m}{j}, & for i = q + 1, q + 2, …, q + p; \\ ∑_{j=0}^{p−1} \binom{n}{i−q−1−j} + \binom{m+n}{i−q−p−1} \\ + ∑_{j=0}^{q−1} \binom{m}{i−p−1−j}, & for i = q + p + 1, …, q + p + m + n + 1; \\ 0, & otherwise. \end{cases}

Proof. By Lemma 7, for 1 ≤ i ≤ p the rank sequence is the convolution of two sequences of ones, that is,

r_{i} = ∑_{j=0}^{i−1} 1 · 1 = i.

Now, for p < i ≤ q,

r_{i} = ∑_{j=0}^{p−1} 1 · 1 + ∑_{j=p}^{i−1} \binom{m}{j − p} · 1 = p + ∑_{j=0}^{i−p−1} \binom{m}{j}.

In the next case, when q < i ≤ q + p,

r_{i} = ∑_{j=0}^{i−q−1} 1 · \binom{n}{j} + ∑_{j=i−q}^{p−1} 1 · 1 + ∑_{j=p}^{i−1} \binom{m}{j − p} · 1,

= ∑_{j=0}^{i−q−1} \binom{n}{j} + (q + p − i) + ∑_{j=0}^{i−p−1} \binom{m}{j}.

Finally for q + p < i ≤ q + p + m + n, we have

r_{i} = ∑_{j=0}^{p−1} 1 · \binom{n}{i − q − 1 − j} + ∑_{j=p}^{i−q−1} \binom{m}{j − p}\binom{n}{i − q − 1 − j} + ∑_{j=i−q}^{i−1} \binom{m}{j − p} · 1

= ∑_{j=0}^{p−1} \binom{n}{i − q − 1 − j} + ∑_{j=0}^{i−q−p−1} \binom{m}{j}\binom{n}{i − q − p − 1 − j} + ∑_{j=0}^{q−1} \binom{m}{i − p − 1 − j}

= ∑_{j=0}^{p−1} \binom{n}{i − q − 1 − j} + \binom{m + n}{i − q − p − 1} + ∑_{j=0}^{q−1} \binom{m}{i − p − 1 − j}.

Note, in Proposition 8 we assumed that p ≤ q, but should it be the case that q ≤ p, a similar result may be obtained by replacing p with q and q with p throughout the statement of the result and the proof. For simplicity throughout the rest of the paper, when referring to Proposition 8 we will utilize whichever version is appropriate, whether p ≤ q or q ≤ p. Further results will only be explicitly proven for the case p ≤ q, but it will be understood that we may apply a switch of variables to prove the result in the case q ≤ p.

First differences of the rank sequence can be useful in determining unimodality, because if the sequence of first differences of a rank sequence changes sign at most one time, then the sequence is unimodal. We will compute the first difference of the sequence (r_{i})_{i≥0}, but first let us consider a few special cases.

Suppose q = p = 0. Then B_{m,0} · B_{n,0} = B_{m+n,0} is the tree with root r and exactly m + n pendant vertices. Therefore the rank sequence is precisely the sequence of binomial coefficients and thus is unimodal. Next, suppose q > p = 0. In this case, applying Proposition 8 to the rank sequence of C(B_{m,0} · B_{n,q}, r) gives the first differences

d_{i} = r_{i} − r_{i−1} = \begin{cases}\binom{m}{i−1}, & for i = 2, 3, …, q; \\ \binom{m+n}{i−q−1} − \binom{m+n}{i−q−2} + \binom{m}{i−1} − \binom{m}{i−q−1}, & for i = q + 1, …, q + m + n. \end{cases}

In Section 3, we will apply Proposition 12 to show the unimodality of (r_{i})_{i≥1} in this case.

More generally we have the following corollary which follows directly from Proposition 8 by subtraction.

Corollary 9. For integers m, n, p, q > 0, let d_{i} = r_{i} − r_{i−1} be the first difference of the rank sequence, (r_{i})_{i≥1} of C(B_{m,p} · B_{n,q}, r), the poset of connected, vertex-induced subtrees containing the root. Without loss of generality assume p ≤ q, then

d_{i} = \begin{cases}1, & for i = 2, 3, …, p; \\ \binom{m}{i−p−1}, & for i = p + 1, p + 2, …, q; \\ \binom{n}{i−q−1} − 1 + \binom{m}{i−p−1}, & for i = q + 1, q + 2, …, q + p; \\ \binom{n}{i−q−1} − \binom{n}{i−q−p−1} + \binom{m+n}{i−q−p−1} \\ − \binom{m+n}{i−q−p−2} + \binom{m}{i−p−1} − \binom{m}{i−q−p−1}, & for i = q + p + 1, …, q + p + m + n + 1; \\ 0, & otherwise. \end{cases}

Now, for i = 1, …, q, because the first differences are non-negative, it is easily seen that the rank sequence is non-decreasing. Further for i > p + q + 1 + ⌊\frac{m+n}{2}⌋, the rank sequence is decreasing. To see this and to simplify notation, we rewrite d_{i} for i > p + q using the substitution i = p + q + j + 1 to obtain the equation

d_{i} = d_{p+q+j+1} = \binom{n}{j + p} − \binom{n}{j} + \binom{m + n}{j} − \binom{m + n}{j − 1} + \binom{m}{j + q} − \binom{m}{j}. (1)

We observe, for j ≥ ⌊\frac{m+n}{2}⌋+1 the differences \binom{n}{j+p}−\binom{n}{j}, \binom{m+n}{j}−\binom{m+n}{j−1}, and \binom{m}{j+q}−\binom{n}{j} are all non-positive. In fact, unless j > m + n + 1 these differences cannot all be zero, because if \binom{m+n}{j} − \binom{m+n}{j−1} = 0, we know m + n is odd and j = ⌊\frac{m+n}{2}⌋ + 1. Because m + n is odd, m must be strictly greater than n so \binom{m}{⌊ \frac{m+n}{2} ⌋+1+q} − \binom{m}{⌊ \frac{m+n}{2} ⌋+1} ≠ 0. Thus the rank sequence is decreasing.

Therefore the question of the rank unimodality of (r_{i})_{i≥1} is reduced to the the question of the unimodality of the terms r_{q+1}, …, r_{p+q+1+⌊ \frac{m+n}{2} ⌋}. Let us first consider a set of posets that are not rank unimodal.

Proposition 10. Given m ≥ n > 0 and p, q > 0, if m ≥ n ≥ 3 or m > n = 2, the rank sequence (r_{i})_{i≥1} of the poset of vertex-induced subtrees containing the root, C(B_{m,p} · B_{n,q}, r), is not unimodal if q ≥ m and p ≥ n.

Proof. Assume q ≥ m and p ≥ n. In Equation 1, set j = 1. Then

d_{q+p+2} = \binom{n}{p + 1} − \binom{n}{1} + \binom{m + n}{1} − \binom{m + n}{0} + \binom{m}{q + 1} − \binom{m}{1}
= \binom{n}{p + 1} − n + n + m − 1 − m + \binom{m}{q + 1}
= \binom{n}{p + 1} + \binom{m}{q + 1} − 1 = −1.

Thus d_{q+p+2} < 0. However, if j = 2, then

d_{q+p+3} = \binom{n}{p + 2} − \binom{n}{2} + \binom{m + n}{2} − \binom{m + n}{1} + \binom{m}{q + 2} − \binom{m}{2}
= −\binom{n}{2} + \binom{m + n}{2} − (m + n) − \binom{m}{2}
= −\frac{n(n − 1)}{2} + \frac{(m + n)(m + n − 1)}{2} − \frac{2(m + n)}{2} − \frac{m(m − 1)}{2}
= \frac{1}{2} (−n^{2} + n + m^{2} + 2mn + n^{2} − m − n − 2m − 2n − m^{2} + m)
= \frac{1}{2}(2mn − 2m − 2n) = mn − m − n.

When m ≥ n ≥ 3, it follows that mn − m − n ≥ 3m − m − n = 2m − n ≥ m > 0, and when m > n = 2 we have mn − m − n = m − 2 > 0. Thus, we see that d_{q+p+3} > 0. Easily d_{2} = 1 > 0, so the sequence of first differences is positive, then negative, and then positive again. Therefore the sequence is not unimodal.

We wish to show these bounds on m, n, q, and p are tight, but first we need some results on the unimodality of sums and differences of binomial coefficients.

3 Unimodality of sequences of sums and differences of binomial coefficients

The sequence of first differences (d_{i})_{i≥2} of the sequence (r_{i})_{i≥1} given in Section 2 is composed of sums and differences of binomial coefficients, so in this section we investigate some similar sequences. In particular, the difference we are concerned with here is sequence \underline{A080232} in the OEIS [8], namely, the sequence (\binom{m}{j}−\binom{m}{j−1})_{j≥0}. This sequence has known combinatorial interpretations enumerating ballot sequences as well as a subset of lattice paths from (0, 0) to (j, m − j). We are interested in the unimodality of the first half of this sequence.

Lemma 11. Given m ≥ 0, the sequence s_{m,j} = \binom{m}{j} − \binom{m}{j−1} is unimodal with respect to j on the interval 0 ≤ j ≤ ⌊\frac{m}{2}⌋.

Proof. We proceed by induction on m. Easily, if m = 0, the sequence s_{0,0} = 1 is unimodal. Now for m > 0, suppose the sequence s_{m−1,0}, s_{m−1,1}, …, s_{m−1,⌊ \frac{m−1}{2} ⌋} is unimodal with a peak at s_{m−1,k}, that is

s_{m−1,0} ≤ s_{m−1,1} ≤ ⋯ ≤ s_{m−1,k} ≥ s_{m−1,k+1} ≥ ⋯ ≥ s_{m−1,⌊ \frac{m−1}{2} ⌋}.

As the sequence s follows the recursion on the binomial coefficients, s_{m,j} = s_{m−1,j} +s_{m−1,j−1}, we see

s_{m−1,k−i} ≥ s_{m−1,k−i−2} ⟹ s_{m,k−i} ≥ s_{m,k−i−1}, for 0 ≤ i ≤ k
s_{m−1,k+i} ≥ s_{m−1,k+i+2} ⟹ s_{m,k+i+1} ≥ s_{m,k+i+2} for 0 ≤ i ≤ ⌊\frac{m − 1}{2}⌋ − k − 2.

To check the end condition, recall ⌊\frac{m−1}{2}⌋ = ⌊\frac{m}{2}⌋ − 1 and s_{m−1,⌊ \frac{m−1}{2} ⌋+1} = 0 if m − 1 is odd, so

s_{m−1,⌊ \frac{m−1}{2} ⌋−1} ≥ s_{m−1,⌊ \frac{m−1}{2} ⌋+1} = 0
s_{m−1,⌊ \frac{m−1}{2} ⌋} + s_{m−1,⌊ \frac{m−1}{2} ⌋−1} ≥ s_{m−1,⌊ \frac{m−1}{2} ⌋+1} + s_{m−1,⌊ \frac{m−1}{2} ⌋}
s_{m−1,⌊ \frac{m}{2} ⌋−1} + s_{m−1,⌊ \frac{m}{2} ⌋−2} ≥ s_{m−1,⌊ \frac{m}{2} ⌋} + s_{m−1,⌊ \frac{m}{2} ⌋−1}
s_{m,⌊ \frac{m}{2} ⌋−1} ≥ s_{m,⌊ \frac{m}{2} ⌋}.

If m − 1 is even, ⌊\frac{m−1}{2}⌋ = ⌊\frac{m}{2}⌋, so

s_{m−1,⌊ \frac{m−1}{2} ⌋−2} ≥ s_{m−1,⌊ \frac{m−1}{2} ⌋} ⟹ s_{m,⌊ \frac{m}{2} ⌋−1} ≥ s_{m,⌊ \frac{m}{2} ⌋}.

Thus the sequence increases from s_{m,0} to s_{m,k} and decreases from s_{m,k+1} to s_{m,⌊ \frac{m}{2} ⌋}. No matter the relationship between s_{m,k} and s_{m,k+1} the sequence is unimodal.

Note the proof techniques in Lemma 11 may be generalized to other sequences found in a row of a triangular array which satisfies the binomial recurrence. We state such a result.

Proposition 12. For integers m, n ≥ 0 and q ≥ 0, the sequence

c_{m,n,j} = \binom{m + n}{j} − \binom{m + n}{j − 1} + \binom{m}{j + q} − \binom{m}{j}

is unimodal with respect to j on the interval 0 ≤ j ≤ ⌊\frac{m+n}{2}⌋.

Proof. Start by fixing m = 0. Then c_{0,n,j} = \binom{n}{j} − \binom{n}{j−1} − \binom{0}{j} + \binom{0}{j+q}. Create a triangular array for n ≥ j ≥ 0. If q = 0, then c_{0,n,j} = s_{n,j}, the sequence found in Lemma 11, and is therefore unimodal. If q > 0, then

c_{0,n,j} = \begin{cases}s_{n,j}, & if j ≠ 0; \\ s_{n,0} − 1, & if j = 0. \end{cases}

is also unimodal.

Now for a fixed n, create a triangular array for c_{m,n,j} where m > 0 and j ≥ 0.

c_{0,n,0} ⋯ c_{0,n,n}
c_{1,n,0}  c_{1,n,1} ⋯ c_{1,n,n+1}
c_{2,n,0}  c_{2,n,1}  c_{2,n,2} ⋯ c_{2,n,n+2}
c_{3,n,0}  c_{3,n,1}  c_{3,n,2}  c_{3,n,3}  ⋯ c_{3,n,n+3}
⋯

The initial row of this array is unimodal as it appears in the array of c_{0,n,j}. Further, the binomial recurrence, c_{m,n,j} = c_{m−1,n,j} + c_{m−1,n,j−1} is satisfied, as the terms are sums and differences of binomial coefficients with respect to m and j. Repeating the proof techniques of Lemma 11, we see that every row in a triangular array having the binomial recurrence and an initial unimodular row is also unimodal, and we have proven the claim.

Recall the first difference of the rank sequence of C(B_{m,0} · B_{n,q}, r) given in Section 2. Because a unimodular sequence whose first term is non-negative may change signs at most once and because the sequence c_{m,n,j} is non-negative when j = 0, Proposition 12 and the substitution j = i−q−1, along with the discussion in Section 2, imply the following corollary.

Corollary 13. For m, n, q > 0, the rank sequences (r_{i})_{i≥1} of the posets C(B_{m,0} · B_{n,0}, r) and C(B_{m,0} · B_{n,q}, r) are rank unimodal.

This result will be used to prove the necessary and sufficient conditions on the integers m, n, p, q to determine rank unimodality of the poset C(B_{m,p} · B_{n,q}, r).

4 Proofs

Before proving Theorem 2, we need to prove some intermediate results.

Proposition 14. Given integers m ≥ n > 0, if \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} ≤ 0 for some 0 < j ≤ ⌊\frac{m+n}{2}⌋, then j ≥ n.

Proof. Suppose by assumption \binom{m}{j} ≥ \binom{m+n}{j} − \binom{m+n}{j−1}. This implies

\frac{m!}{j!(m − j)!} ≥ \frac{(m + n)!}{j!(m + n − j)!} (1 − \frac{j}{m + n + 1 − j} )
\frac{m!}{j!(m − j)!} ≥ \frac{(m + n)!}{j!(m + n − j)!} (\frac{m + n + 1 − 2j}{m + n + 1 − j} )
\frac{m + n + 1 − j}{m + n + 1 − 2j} ≥ \frac{(m + n)(m + n − 1) ⋯ (m + 1)}{(m + n − j)(m + n − 1 − j) ⋯ (m + 1 − j)}
1 + \frac{j}{m + n + 1 − 2j} ≥ (1 + \frac{j}{m + n − j} ) (1 + \frac{j}{m + n − 1 − j} ) ⋯ (1 + \frac{j}{m + 1 − j} )

As each factor in the product is greater than one, we have

1 + \frac{j}{m + n + 1 − 2j} ≥ 1 + \frac{j}{m + 1 − j}
m + 1 − j ≥ m + n + 1 − 2j
j ≥ n.

Proposition 14 implies the following corollary we will need to prove our main result.

Corollary 15. Given integers m ≥ n > 0 and p, q ≥ 0, if

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} + \binom{m}{j + q} ≤ 0

for some 0 < j ≤ ⌊\frac{m+n}{2}⌋, then

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} + \binom{m}{j + q} − \binom{n}{j} + \binom{n}{j + q} ≤ 0.

The assumptions in Corollary 15 imply those of Proposition 14, so j ≥ n and thus the quantity −\binom{n}{j} + \binom{n}{j+q} ≤ 0.

Now we consider the case that the sequence \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} is greater than zero.

Proposition 16. Given integers m ≥ n > 0, if

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} > 0

for some 1 < j ≤ ⌊\frac{m+n}{2}⌋, then

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} − \binom{n}{j} ≥ 0.

Proof. First, if j > n, then \binom{n}{j} = 0 and the result holds, so assume 1 < j ≤ n; that is, assume \binom{n}{j} ≠ 0 and \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} > 0. We wish to show

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} − \binom{n}{j} ≥ 0.

But dividing by \binom{n}{j} and then adding 1 to both sides, the inequality can be rewritten as follows:

\frac{(m + n) ⋯ (n + 1)}{(m + n − j) ⋯ (n + 1 − j)} (\frac{m + n + 1 − 2j}{m + n + 1 − j} ) − \frac{m(m − 1) ⋯ (n + 1)}{(m − j)(m − 1 − j) ⋯ (n + 1 − j)} ≥ 1
\frac{(m + n)}{n} ⋯ \frac{(m + n + 1 − j)}{(n + 1 − j)} (\frac{m + n + 1 − 2j}{m + n + 1 − j} ) − \frac{m}{n} · \frac{(m − 1)}{(n − 1)} ⋯ \frac{(m + 1 − j)}{(n + 1 − j)} ≥ 1
\frac{(m + n)(m + n − 1) ⋯ (m + n + 2 − j)(m + n + 1 − 2j) − m(m − 1) ⋯ (m + 1 − j)}{n(n − 1) ⋯ (n + 1 − j)} ≥ 1

To show this inequality holds, we induct on j ≥ 2. Suppose j = 2. Then we have the expression

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

Because m + n ≥ 2n, we have

\frac{2(m + n)}{n} − \frac{n + 1}{n − 1} ≥ 4 − \frac{n + 1}{n − 1}.

Then \frac{n+1}{n−1} ≤ 3 for n ≥ 2, so we have the desired result

\frac{(m + n)(m + n − 3) − m(m − 1)}{n(n − 1)} ≥ 1.

Now by induction assume the inequality

\frac{(m + n) ⋯ (m + n + 2 − j)(m + n + 1 − 2j) − m ⋯ (m + 2 − j)(m + 1 − j)}{n(n − 1) ⋯ (n + 1 − j)} ≥ 1 (2)

holds for j ≥ 2. We wish to multiply by a term which preserves the inequality. First, let us assume the strict inequality n > j; that is, n ≥ j + 1. Then

m + n ≥ n + j + 1
m + n − 1 − 2j ≥ n − j.

Clearly m + n + 1 − j ≥ m + n + 1 − 2j, so the product

\frac{(m + n + 1 − j)}{(m + n + 1 − 2j)} · \frac{(m + n − 1 − 2j)}{(n − j)} ≥ 1.

Thus multiplying the left-hand side of inequality (2) by this term maintains the inequality on the right-hand side. Multiply the denominator by (n − j) to obtain

n(n − 1) ⋯ (n + 1 − j)(n − j),

as desired. Multiply the numerator by the remaining factor, \frac{(m+n+1−j)(m+n−1−2j)}{(m+n+1−2j)}, to obtain

(m + n) ⋯ (m + n + 1 − j)(m + n − 1 − 2j) − m ⋯ (m + 1 − j)\frac{(m+n+1−j)(m+n−1−2j)}{(m+n+1−2j)}.

The first summand is as desired for the inductive step, so consider the the second term. We have

0 ≤ n − 1 = 2n^{2} − n − 1 − 2n(n − 1) ≤ (n − 1)(2n + 1) − 2nj
≤ (n − 1)(m + n + 1) − 2nj
= (m + n + 1 − j)(m + n − 1 − 2j) − (m − j)(m + n + 1 − 2j).

Thus,

(m − j)(m + n + 1 − 2j) ≤ (m + n + 1 − j)(m + n − 1 − 2j)
m − j ≤ \frac{(m + n + 1 − j)(m + n − 1 − 2j)}{m + n + 1 − 2j},

which implies

−m(m − 1) ⋯ (m + 1 − j)\frac{(m+n+1−j)(m+n−1−2j)}{(m+n+1−2j)} ≤ −m(m − 1) ⋯ (m + 1 − j)(m − j).

Thus for the inductive step, that is j + 1, the following inequality holds:

\frac{(m + n) ⋯ (m + n + 1 − j)(m + n − 1 − 2j) − m ⋯ (m + 1 − j)(m − j)}{n(n − 1) ⋯ (n + 1 − j)(n − j)} ≥ 1.

We have one other case to consider. Suppose j = n. Then by assumption

\binom{m + n}{n} − \binom{m + n}{n − 1} − \binom{m}{n} > 0,

therefore

\binom{m + n}{n} − \binom{m + n}{n − 1} − \binom{m}{n} − \binom{n}{n} = \binom{m + n}{n} − \binom{m + n}{n − 1} − \binom{m}{n} − 1 ≥ 0.

We may extend Proposition 16 as follows:

Corollary 17. Given integers m ≥ n > 0 and p, q ≥ 0, if

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} + \binom{m}{j + q} > 0

for some 1 < j ≤ ⌊\frac{m+n}{2}⌋, then

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} + \binom{m}{j + q} − \binom{n}{j} + \binom{n}{j + p} ≥ 0.

Proof. If \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} + \binom{m}{j+q} > 0, there are two possibilities. In the first case, suppose \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} > 0. Apply Proposition 16 for the desired result:

\binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} + \binom{m}{j+q} − \binom{n}{j} + \binom{n}{j+p} ≥ \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} − \binom{n}{j} ≥ 0 .

Otherwise, suppose \binom{m+n}{j}−\binom{m+n}{j−1}−\binom{m}{j} ≤ 0. We apply Proposition 14 to see the quantity −\binom{n}{j} + \binom{n}{j+p} is either negative one or zero. Applied to the initial assumption, \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} + \binom{m}{j+q} > 0, we have

\binom{m + n}{j} − \binom{m + n}{j − 1} − \binom{m}{j} + \binom{m}{j + q} − \binom{n}{j} + \binom{n}{j + p} ≥ 0.

Now, we are ready to prove rank unimodality.

Proposition 18. For integers m, n, p, q > 0, the rank sequence (r_{i})_{i≥1} of the poset C(B_{m,p} · B_{n,q}, r) of connected, vertex-induced subtrees containing the root is unimodal if q < m or p < n.

Proof. As long as either q < m or p < n, the sequence of first differences (d_{i})_{i≥2} is nonnegative up to i = p+q. Using the change of variables in Eq. 1, we need to check that the signs of the first differences d_{q+p+j+1} are positive and then possibly negative for 0 ≤ j ≤ ⌊\frac{m+n}{2}⌋, as we know they are negative for j > ⌊\frac{m+n}{2}⌋. Without loss of generality, suppose m ≥ n. Note, because p, q > 0 and either m > q or m ≥ n > p, we have that m ≥ 2.

Further, for j > 1, Corollaries 15 and 17 show \binom{m+n}{j}−\binom{m+n}{j−1}−\binom{m}{j}+\binom{m}{j+q}−\binom{n}{j}+\binom{n}{j+p} is non-positive or non-negative, respectively, when \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} + \binom{m}{j+q} is non-positive or positive, respectively, so we see their signs are positive and negative or possible neutral on the same intervals. As the sequence \binom{m+n}{j} − \binom{m+n}{j−1} − \binom{m}{j} + \binom{m}{j+q} is unimodal on the interval in question by Proposition 12 and for j = 2 the difference d_{q+p+3} ≥ mn − m − n ≥ 0, the first difference of the rank sequences changes sign at most once. To complete the proof, we need to consider when j = 1. As long as either q < m or p < n, we note the first difference d_{q+p+2} ≥ 0 as seen in the proof of Proposition 10. Further we check that

d_{q+p+1} > \binom{m}{q} + \binom{n}{p} − 1 ≥ n − 1 ≥ 0

so the difference in rank sequence is positive for j = 0, 1, 2 as long as q < m or p < n and m, n ≥ 3 or m > n ≥ 2. Thus the sequence of first differences is positive and then negative and therefore the rank sequence is unimodal.

As we have already discussed the unimodality of the rank sequence (r_{i})_{i≥1} of the poset C(B_{m,p} · B_{n,q}, r) where p = q = 0 and q > p = 0, we still have two special cases to consider.

Lemma 19. The rank sequences (r_{i})_{i≥1} of the posets C(B_{m,p} · B_{1,q}, r) and C(B_{2,p} · B_{2,q}, r) are unimodal for any integers m, p, q > 0.

Proof. Consider the poset C(B_{m,p} · B_{n,q}, r) where we let n = 1. Because p > 0, we have p ≥ n, so suppose m > q > 0. In this case, the first difference d_{i} is non-negative up through i = p + q + 2. If i > p + q + 2, then

d_{i} = d_{p+q+j+1} = \binom{m}{j + q} − \binom{m}{j − 2}

for j > 1. If q < m − 1, the difference d_{q+p+3} ≥ 0 and hence Proposition 18 implies rank unimodularity of C(B_{m,p} · B_{1,q}, r). If q = m − 1, we have d_{q+p+j+1} ≤ 0 for all j > 1 and hence the difference changes sign exactly once at j = 2, implying the poset is also rank unimodular. Now check in the case q ≥ m. By Corollary 9, the first difference d_{i} is positive for i = 2 up to i = max{p, q}. Then, for max{p, q} < i ≤ q + p, the first difference

d_{i} = \binom{1}{i − q − 1} − 1 + \binom{m}{i − p − 1}

is non-negative if and only if i ≤ max{q +2, m+p+1}, so thus the sign of the first difference changes from positive to negative when i = max{q + 2, m + p + 1} + 1. For i > q + p, equation 1 gives the first difference

d_{i} = d_{p+q+j+1} = \binom{1}{j + p} − \binom{1}{j} + \binom{m}{j + q} − \binom{m}{j − 2}

which is always less than or equal to zero for j ≥ 0. Hence the sequence of differences is positive and then negative so the rank sequence of C(B_{m,p} · B_{1,q}, r) is unimodal.

Next, without loss of generality, assume p ≤ q and consider the poset C(B_{2,p} · B_{2,q}, r). The rank sequence of C(B_{2,p} · B_{2,q}, r) is the convolution of two sequences (t_{i})_{i≥1} and (s_{i})_{i≥1} consisting of exactly one two with the remaining terms being ones. First consider the convolution of the sequence of (p + 3) ones with the sequence of (q + 3) ones. At each rank, either we add one, remain neutral, or subtract one from the value of the previous rank, so the sequence of differences is

(d_{i})_{i≥2} = 1, 1, ⋯, 1, 0, 0, ⋯, 0, −1, −1, ⋯, −1,

where there are (p + 2) ones, (q − p) zeros, and (p + 2) negative ones. Replacing the (p + 2)^{nd} one in the first sequence with a two, that is setting t_{p+2} = 2, increases the term d_{p+2} in the sequence of differences by one and replacing the (q + 2)^{nd} term in the second sequence with a two, that is setting s_{q+2} = 2, increases the difference d_{q+2} by one. These terms are either ones or zeros so increasing by one (or possibly two if p = q) does not change the sign of the difference sequence from positive to negative. Further, the only other change to the difference sequence is in the last three terms of the sequence which become 0, −2, −3. These terms do not change the sign on the difference sequence from negative to positive, so the difference sequence changes sign exactly one and hence the rank sequence is unimodal.

Thus, Propositions 10 and 18 with Corollary 13 and Lemma 19 provide necessary and sufficient conditions on the integers m, n, p, q to determine the rank unimodality of the subtree poset C(B_{m,p} · C_{n,q}, r) and prove Theorem 2. In the final section, we enumerate the trees that correspond to a poset C(B_{m,k} · B_{n,p}, r) which is not rank unimodal.

5 Enumeration

As we shall see, there exists an explicit formula to count the number of trees B_{m,p} · B_{n,q} whose posets C(B_{m,p} · B_{n,q}, r) are not rank unimodal. But first, we will utilize a bijection between two sets.

Proposition 20. For an integer i ≥ 1, the set of (2 × i) binary matrices with no zero rows or columns, up to row and column permutation is in bijection with the set of integer pairs (m, n) such that m ≥ n ≥ 3 or m > n = 2 and m + n ≤ i + 4.

Proof. We provide a bijective map from the set B_{i} of integer pairs (m, n) such that m ≥ n ≥ 3 or m > n = 2 and m + n ≤ i + 4 into the set A_{i} of (2 × i) binary matrices with no zero rows or columns, up to row and column permutation. Given an integer i ≥ 1 and a pair (m, n) from the set B_{i}, suppose m ≥ n > 2. Set (a, b) = (m − 2, n − 2). Then the image of (m, n) is the 2 × i matrix with b zeros in the first row and a zeros in the second row as follows:

[\begin{matrix}1 & ⋯ & 1 & 0 & ⋯ & 0 & 1 & ⋯ & 1 \\ 0 & \underbrace{⋯}_{a} & 0 & 1 & \underbrace{⋯}_{b} & 1 & 1 & \underbrace{⋯}_{i−a−b} & 1 \end{matrix}] .

When n = 2, set (a, b) = (m − 3, 0) and map (m, 2) to the matrix

[\begin{matrix}1 & ⋯ & 1 & 1 & ⋯ & 1 \\ 0 & \underbrace{⋯}_{a} & 0 & 1 & \underbrace{⋯}_{i−a} & 1 \end{matrix}] .

This map is injective; for each unique integer pair (m, n) the pair (a, b) is also unique and hence describes a unique matrix up to row and column permutation. Further, given a (2 × i) matrix from the set B_{i}, the map may be reversed by using row and column permutations to standardize the matrix so the first row is a sequence of ones followed by a sequence of zeros followed by a sequence of ones, and the second row is a sequence of zeros followed by a sequence of ones. Then the pairs (a, b) are easily determined and can be shifted to pairs (m, n) in B_{i}.

Set a_{i} = |A_{i}|. The sequence (a_{i})_{i≥0} is a known sequence appearing (with a shift) as sequence \underline{A024206} in the OEIS [8]. One formula is

a_{i} = ⌊\frac{i(i + 4)}{4}⌋ .

Now, for a given number of vertices in the tree, we will enumerate the trees whose subtree poset C(B_{m,p} · B_{n,q}, r) is not rank unimodal.

Theorem 21. Let T = B_{m,p} ·B_{n,q} be a tree which is the merge of two broom graphs for some integers m, n > 0 and p, q ≥ 0. Let b_{i} be the number of trees T with i vertices such that the poset C(T, r) is not rank unimodal. We have b_{1} = b_{2} = ⋯ = b_{9} = 0, and for k ≥ 0

b_{2k+10} = 2 (∑_{i=0}^{k} ⌊\frac{i(i + 4)}{4}⌋) − ⌊\frac{k^{2}}{4} ⌋

b_{2k+11} = 2 (∑_{i=0}^{k} ⌊\frac{i(i + 4)}{4}⌋) + ⌊\frac{(k + 1)(k + 5)}{4}⌋ − ⌊\frac{k^{2}}{4} ⌋

Proof. Every tree with i vertices that is the merge of two brooms may described by an ordered quadruplet (m, n, p, q) of non-negative integers where m gives the number of pendant vertices on the first broom, n gives the number of pendant vertices on the second broom, p describes the length of the handle of the first broom, and q describes the length of the handle of the second broom. The sum is m + n + p + q = i − 1. Without loss of generality we will always assume m ≥ n.

If the rank sequence of the poset C(B_{m,p} · B_{n,q}) is not unimodal, by Theorem 2, we know m ≥ 3, n ≥ 2, q ≥ m and p ≥ n. First fix the first two terms of the quadruplet (m, n). Under these restrictions, for each pair m + n ≤ \frac{i−1}{2}, the number of trees leading to a non-unimodal poset is completely determined, that is, we have the following set of quadruplets describing such trees:

{(m, n, m, i − 2m − n − 1), (m, n, m + 1, i − 2m − n − 2), …, (m, n, i − m − 2n − 1, n)}.

As long as m ≠ n each of these trees is unique as a rooted tree up to isomorphism. If m = n, we have the following unique trees:

\{(m, n, m, i − 2m − n − 1), (m, n, m + 1, i − 2m − n − 2), …, (m, n, ⌊\frac{i−m−n−1}{2}⌋, ⌈\frac{i−m−n−1}{2}⌉)\}.

We work recursively. If i is odd, for every tree (m, n, p, q) on i − 1 vertices there is a corresponding tree on i vertices using the straight-forward injection

(m, n, p, q) ⟶ (m, n, p, q + 1).

Further for each pair (m, n) such that m+n ≤ \frac{i−1}{2} there is one additional tree to be counted, that is, the tree with n as the final coordinate, (m, n, i − m − 2n − 1, n) if m ≠ n, and the tree (m, m, \frac{i−2m−1}{2}, \frac{i−2m−1}{2}) if m = n. None of these trees are accounted for in the surjection as their last coordinates are smaller than those given in the map. Thus to count the number of trees when i is odd, we may count the number of trees on i − 1 vertices plus the number of pairs (m, n) such that m + n ≤ \frac{i−1}{2}. Setting i = 2k + 11, recall from Proposition 20 the number of such pairs are given by the sequence (a_{k+1}). Therefore for k ≥ 0,

b_{2k+11} = b_{2k+10} + a_{k+1}.

Now suppose i is even. We still have the injection from the set of trees on i − 1 vertices to the set of trees on i vertices, however we must be careful when counting additional trees. If m = n there is no additional tree as the tree (m, m, ⌊\frac{i−2m−1}{2}⌋+1, ⌈\frac{i−2m−1}{2}⌉−1) is isomorphic to the tree (m, m, ⌊\frac{i−2m−1}{2}⌋ , ⌈\frac{i−2m−1}{2}⌋).

Therefore for i even we add the number of trees on i−1 vertices plus the number of pairs (m, n) where m ≠ n. Setting i = 2k + 10, the number of pairs (m, n) where m + n ≤ \frac{i−1}{2} is given by a_{k}, and the number of such pairs where m = n is ⌊\frac{k}{2}⌋. Now, we have

b_{2k} = b_{2k−1} + a_{k} − ⌊\frac{k}{2}⌋ .

Now, we repeatedly apply the recursion along with the initial conditions b_{10} = 0 and b_{11} = 1 found in by Jacobson, Kézdy, and Seif [4]. So for any k ≥ 0 we have

b_{2k+11} = b_{2k+10} + a_{k+1}

= b_{2k+9} + a_{k} + a_{k+1} − ⌊\frac{k}{2}⌋

= b_{2k+8} + 2a_{k} + a_{k+1} − ⌊\frac{k}{2}⌋

= b_{2k+7} + a_{k−1} + 2a_{k} + a_{k+1} − ⌊\frac{k}{2}⌋ − ⌊\frac{k − 1}{2}⌋

⋮

= 2(a_{1} + a_{2} + ⋯ a_{k}) + a_{k+1} − ⌊\frac{k}{2}⌋ − ⋯ − ⌊\frac{1}{2}⌋

= 2 (∑_{i=1}^{k} ⌊\frac{i(i + 4)}{4}⌋) + ⌊\frac{(k + 1)(k + 5)}{4}⌋ − ⌊\frac{k^{2}}{4} ⌋ .

Note the identity ∑_{i=1}^{k} ⌊\frac{i}{2}⌋ = ⌊\frac{k^{2}}{4} ⌋ may be found in the entry for sequence \underline{A002620} of the OEIS [8].

This result on the odd indexed terms then implies for k ≥ 0,

b_{2k+10} = 2 (∑_{i=1}^{k} ⌊\frac{i(i + 4)}{4}⌋) − ⌊\frac{k^{2}}{4} ⌋ .

Trees leading to a vertex-induced poset that is not unimodal are quite frequent. Let t_{i} be the total number of non-isomorphic trees B_{m,p} · B_{n,q} with i vertices, m, n ≥ 0 and p, q > 0. The sequence (t_{i})_{i≥1} is found in The Online Encyclopedia of Integer Sequences [8] as sequence \underline{A005993}. To see how this sequence enumerates non-isomorphic trees, we look to a comment by C. Zizka who describes the term t_{i} as the number of different patterns on the 2-color 4-partitions of i (with an offset of 4). Recall that trees B_{m,p} · B_{n,q} with i vertices may described as ordered 4-tuples where the coordinates sum to i − 1. All trees may be described by a choice of m, n ≥ 0 and p, q > 0. We partition i + 1 into four non-zero parts, a, b, c, and d, and use these values to determine all possible trees, shifting two of the partition values by −1 to allow for m, n = 0 and to create a sum equal to i − 1. There are several cases. If a = b = c = d, there is only one way to place the partition values in a distinct 4-tuple, creating a single tree and corresponding to the one pattern on this partition. If a = b = c ≠ d, we may choose d − 1 = m or d = p, setting all other values in the 4-tuple to a or a−1, therefore creating two different trees and two patterns. All other possibilities create a tree isomorphic to one of the two trees already generated. If a = b and c = d, we may set

\begin{matrix}i & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ b_{i} & 0 & 1 & 2 & 5 & 7 & 12 & 16 & 24 & 30 & 41 & 50 & 65 & 77 \\ t_{i} & 60 & 85 & 110 & 146 & 182 & 231 & 280 & 344 & 408 & 570 & 670 & 770 & 891 \end{matrix}

Table 1: Initial values for sequences (b_{i}) and (t_{i}), respectively, which enumerate the number of non-unimodal, total number respectively, of sequences (r_{i})_{i≥0} where m, n, ≥ 0 and p, q > 0.

a − 1 = m = n and c = p = q, c − 1 = m = n and a = p = q, a − 1 = m, a = p, c − 1 = n, and c = q, or a − 1 = m, a = q, c − 1 = n, and c = p for a total of four choices. This argument continues similarly for the other two forms, namely if a = b and c and d are both distinct from a and from each other, there are six trees created, and if a, b, c, and d are all distinct from each other there are 12 non-isomorphic trees. These are exactly the patterns of 2-color 4-partitions described in the encyclopedia entry.

The sequence (b_{i})_{i≥1} has also been entered into the OEIS in the entry \underline{A320657}. Table 1 gives the first values of the sequence (b_{i}) starting with i = 10, that is the number of trees of a given size whose poset C(B_{m,p} · B_{n,q}, r) has a rank sequence which is not unimodal, determined by Theorem 21, as well as the total number of non-isomorphic trees B_{m,p} · B_{n,q} with i vertices where m, n > 0 and p, q ≥ 0.

References

[1] H. Belbachir, F. Bencherif, and L. Szalay, Unimodality of certain sequences connected with binomial coefficients, J. Integer Sequences 10 (2007), Article 07.2.3.

[2] J. Bertrand, Solution d’un probléme, Comptes Rendus de l’Académie des Sciences, Paris 105 (1887), 369.

[3] F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, in Jerusalem Combinatorics ’93, Contemp. Math. 178 (1994), American Mathematical Society, pp. 71–89.

[4] M. Jacobson, A. E. Kézdy, and S. Seif, The poset on connected induced subgraphs of a graph need not be Sperner, Order 12 (1995), 315–318.

[5] A. E. Kézdy and S. Seif, When is a poset isomorphic to the poset of connected induced subgraphs of a graph?, Southwest J. Pure Appl. Math. 1 (1996), 42–50.

[6] B. Leclerc, Arbres et dimension des ordres, Discrete Math. 14 (1976), 69–76.

[7] B. Sagan, Unimodality and the reflection principle, Ars Combin. 48 (1998), 65–72.

[8] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2019.

[9] S. G. Z. Smith and I. Tomon, The poset on connected graphs is Sperner, J. Combin. Theory Ser. A 150 (2017), 162–181.

[10] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989), 500–535.

[11] J. H. Steelman, The lattice of connected subgraphs of a graph, solution to problem E3281, Amer. Math. Monthly 97 (1990), 924–925. Proposed by S. Klavz̆ar and M. Petkovs̆ek, Amer. Math. Monthly 95 (1988), 655.

[12] X.-T. Su and Y. Wang, On unimodality problems in Pascal’s triangle, Electron. J. Combin. 15 (1) (2008), Paper 113.

[13] S. M. Tanny and M. Zuker, On a unimodal sequence of binomial coefficients, Discrete Math. 9 (1974), 79–89.

[14] W. T. Trotter, Jr. and J. I. Moore, Jr., Some theorems on graphs and posets, Discrete Math. 15 (1974), 79–84.

[15] A. Vince and H. Wang, Infinitely many trees have non-Sperner subtree poset, Order 24 (2007), 133–138.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 05C05.

Keywords: binomial coefficient, rank sequence, tree, unimodal.

(Concerned with sequences \underline{A002620}, \underline{A005993}, \underline{A024206}, \underline{A080232}, and \underline{A320657}.)

Received October 23 2018; revised versions received November 8 2018; April 23 2019. Published in Journal of Integer Sequences, May 6 2019.

Return to Journal of Integer Sequences home page.