Using Graph Theory to Derive Inequalities for the Bell Numbers

Alain Hertz Department of Mathematics and Industrial Engineering Polytechnique Montréal and GERAD Montréal, PQ H3T 1J4 Canada

                       alain.hertz@gerad.ca

Anaelle Hertz Department of Physics University of Toronto Toronto, ON M5S 1A7 Canada

                    ahertz@physics.utoronto.ca

Hadrien Mélot Computer Science Department—Algorithms Lab University of Mons 7000 Mons Belgium

                    hadrien.melot@umons.ac.be

Abstract

The Bell numbers count the number of different ways to partition a set of n elements, while the graphical Bell numbers count the number of non-equivalent partitions of the vertex set of a graph into stable sets. This relation between graph theory and integer sequences has motivated us to study properties on the average number of colors in the non-equivalent colorings of a graph to discover new nontrivial inequalities for the Bell numbers. Examples are given to illustrate our approach.

1 Introduction

The Bell numbers (B_{n})_{n≥0} count the number of different ways to partition a set that has exactly n elements. Starting with B_{0} = B_{1} = 1, the first few Bell numbers are 1, 1, 2, 5, 15, 52, 203 (sequence \underline{A141390} in the On-Line Encyclopedia of Integer Sequences). The integer B_{n} can be defined to be the sum

B_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\},

where \left\{{n \atop k}\right\} is the Stirling number of the second kind, with parameters n and k (i.e., the number of partitions of a set of n elements into k blocks). Dobiński’s formula [4] gives

B_{n} = \frac{1}{e} ∑_{k=0}^{∞} \frac{k^{n}}{k!} .

The 2-Bell numbers (T_{n})_{n≥0} count the total number of blocks in all partitions of a set of n + 1 elements. Starting with T_{0} = 1 and T_{1} = 3, the first few 2-Bell numbers are 1, 3, 10, 37, 151, 674 (sequence \underline{A005493}). More formally, the integer T_{n} is defined by

T_{n} = ∑_{k=0}^{n+1} k\left\{{n + 1 \atop k}\right\} = B_{n+2} − B_{n+1}.

Odlyzko and Richmond [12] have studied the average number A_{n} of blocks in a partition of a set of n elements, which can be defined as

A_{n} = \frac{T_{n−1}}{B_{n}} .

A concept very close to the Bell numbers is also defined in graph theory. More precisely, a coloring of a graph G is an assignment of colors to its vertices such that adjacent vertices have different colors. The chromatic number χ(G) is the minimum number of colors in a coloring of G. Two colorings are equivalent if they induce the same partition of the vertex set into color classes. For an integer k > 0, we define S(G, k) as the number of proper nonequivalent colorings of a graph G that use exactly k colors. Since S(G, k) = 0 for k < χ(G) or k > n, the total number B(G) of non-equivalent colorings of a graph G is defined to be

B(G) = ∑_{k=0}^{n} S(G, k) = ∑_{k=χ(G)}^{n} S(G, k).

In other words, B(G) is the number of partitions of the vertex set of G whose blocks are stable sets (i.e., sets of pairwise non-adjacent vertices). This invariant has been studied by several authors in the last few years [1, 6, 7, 9, 10, 11] under the name of (graphical) Bell number of G.

Let T (G) be the total number of stable sets in the set of non-equivalent colorings of a graph G. More precisely, we define

T (G) = ∑_{k=χ(G)}^{n} kS(G, k).

We are interested in computing the average number A(G) of colors in the non-equivalent colorings of G, that is,

A(G) = \frac{T (G)}{B(G)}.

Clearly, B(\overline{K}_{n}) = B_{n}, T (\overline{K}_{n}) = T_{n−1} = B_{n+1} − B_{n}, and A(\overline{K}_{n}) = \frac{B_{n+1}−B_{n}}{B_{n}} , where \overline{K}_{n} is the empty graph with n vertices. As another example, consider the cycle C_{5} on 5 vertices. As shown in Figure 1, there are five colorings of C_{5} with 3 colors, five with 4 colors, and one with 5 colors, which gives B(C_{5}) = 11, T (C_{5}) = 40 and A(G) = \frac{40}{11}.

Figure 1: The non-equivalent colorings of C_{5}.

This close link between Bell numbers and graph colorings indicates that it is possible to use graph theory to derive inequalities for the Bell numbers. This is the aim of this article. The next section gives values of A(G) for some families of graphs and basic properties involving A(G). In Section 3, we give several examples of inequalities for the Bell numbers that can be deduced from relations involving A(G).

Let u and v be two vertices in a graph G. We let G_{|uv} denote the graph obtained by identifying (merging) the vertices u and v and, if u and v are adjacent vertices, by removing the edge that links u and v. If parallel edges are created, we keep only one. Also, if u is adjacent to v, we let G − uv denote the graph obtained from G by removing the edge that links u with v, while if u is not adjacent to v, we let G + uv denote the graph obtained by linking u with v. In what follows, we let K_{n}, P_{n} and C_{n} be the complete graph of order n, the path of order n, and the cycle of order n, respectively. We denote the disjoint union of two graphs G_{1} and G_{2} by G_{1} ∪ G_{2}. We refer to Diestel [3] for basic notions of graph theory that are not defined here.

2 Some values and properties of A(G)

The deletion-contraction rule (also often called the fundamental reduction theorem [5]) is a well known method to compute B(G) [7, 11]. More precisely, let u and v be any pair of distinct vertices of G. We have

S(G, k) = S(G − uv, k) − S(G_{|uv}, k) for every pair u, v of adjacent vertices in G,  (1)
S(G, k) = S(G + uv, k) + S(G_{|uv}, k) for every pair u, v of non-adjacent vertices in G. (2)

It follows that

\begin{matrix}B(G) = B(G − uv) − B(G_{|uv}) \\ T (G) = T (G − uv) − T (G_{|uv}) \end{matrix} \} for every pair u, v of adjacent vertices in G,  (3)
\begin{matrix}B(G) = B(G + uv) + B(G_{|uv}) \\ T (G) = T (G + uv) + T (G_{|uv}) \end{matrix} \} for every pair u, v of non-adjacent vertices in G. (4)

Let v be a vertex in a graph G. We let G − v denote the graph obtained from G by removing v and all its incident edges. A vertex of a graph G is dominating if it is adjacent to all other vertices of G, and it is simplicial if its neighbors are pairwise adjacent.

Proposition 1. If G has a dominating vertex v, then A(G) = 1 + A(G − v).

Proof. Clearly, S(G, k) = S(G − v, k − 1) for all k, which implies

B(G) = ∑_{k=χ(G)}^{n} S(G, k)

= ∑_{k=χ(G)}^{n} S(G − v, k − 1) = ∑_{k=χ(G−v)}^{n−1} S(G − v, k) = B(G − v)

and

T (G) = ∑_{k=χ(G)}^{n} kS(G, k)

= ∑_{k=χ(G)}^{n} kS(G − v, k − 1) = ∑_{k=χ(G−v)}^{n−1}(k + 1)S(G − v, k) = T (G − v) + B(G − v).

Hence A(G) = \frac{T (G − v) + B(G − v)}{B(G − v)} = 1 + \frac{T (G − v)}{B(G − v)} = 1 + A(G − v).

Duncan [7] proved that if G is a tree, then S(G, k) = \left\{{n−1 \atop k}\right\} for k = 1, …, n. This leads to our second proposition.

Proposition 2. Let G be a tree of order n. Then B(G) = B_{n−1} and T (G) = B_{n}.

Proof. Since S(G, k) = \left\{{n−1 \atop k−1}\right\}, we immediately get

B(G) = ∑_{k=1}^{n} \left\{{n − 1 \atop k − 1}\right\} = ∑_{k=0}^{n−1} \left\{{n − 1 \atop k}\right\} = B_{n−1}

and

T (G) = ∑_{k=1}^{n} k\left\{{n − 1 \atop k − 1}\right\} = ∑_{k=0}^{n−1}(k + 1)\left\{{n − 1 \atop k}\right\}

= ∑_{k=0}^{n−1} k\left\{{n − 1 \atop k}\right\} + ∑_{k=0}^{n−1} \left\{{n − 1 \atop k}\right\} = (B_{n} − B_{n−1}) + B_{n−1} = B_{n}.

Proposition 3. Let T ∪ pK_{1} be the graph obtained from a tree T of order n ≥ 1 by adding

p isolated verices. Then B(T ∪ pK_{1}) = ∑_{i=0}^{p} \binom{p}{i}B_{n+i−1} and T (T ∪ pK_{1}) = ∑_{i=0}^{p} \binom{p}{i}B_{n+i}.

Proof. For p = 0, the result follows from Proposition 2. For larger values of p, we proceed by induction. Let T′ be the tree obtained from T by adding a new vertex and linking it to exactly one vertex in T. Equations (4) give the following:

B(T ∪ pK_{1}) = B(T′ ∪ (p − 1)K_{1}) + B(T ∪ (p − 1)K_{1})

= ∑_{i=0}^{p−1} \binom{p − 1}{i}B_{n+i} + ∑_{i=0}^{p−1} \binom{p − 1}{i}B_{n+i−1}

= ∑_{i=1}^{p} \binom{p − 1}{i − 1}B_{n+i−1} + ∑_{i=0}^{p−1} \binom{p − 1}{i}B_{n+i−1}

= B_{n+p−1} + ∑_{i=1}^{p−1} (\binom{p − 1}{i − 1} + \binom{p − 1}{i}) B_{n+i−1} + B_{n−1}

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

The proof for T (T ∪ pK_{1}) is similar.

Proposition 4. Let C_{n} be a cycle of order n ≥ 3. Then,

B(C_{n}) = ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j} and T (C_{n}) = ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1}.

Proof. Duncan [7] proved that B(C_{n}) = ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j}. It is therefore sufficient to prove that T (C_{n}) = ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1}.

If n = 3, then T (C_{3}) = 3 = B_{3} − B_{2}. If n > 3, Equations (3) together with the fact that P_{n} is a tree give T (C_{n}) = T (P_{n}) − T (C_{n−1}) = B_{n} − T (C_{n−1}), and the result follows by induction.

Proposition 5. Let C_{n} ∪ pK_{1} be the graph obtained from a cycle of order n ≥ 3 by adding p isolated verices. Then

B(C_{n}∪pK_{1}) = ∑_{j=1}^{n−1}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j} and T (C_{n}∪pK_{1}) = ∑_{j=1}^{n−1}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j+1}.

Proof. For p = 0, the result follows from Proposition 4. For larger values of p, we proceed by induction. If n = 3 then Equations (3) and Proposition 3 give

B(C_{3} ∪ pK_{1}) = B(P_{3} ∪ pK_{1}) − B(P_{2} ∪ pK_{1})

= ∑_{i=0}^{p} \binom{p}{i}B_{3+i−1} − ∑_{i=0}^{p} \binom{p}{i}B_{2+i−1}

= ∑_{j=1}^{2}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{3+i−j}.

Hence, the result is valid for n = 3. So assume n > 3 and that the statement holds for smaller values of n:

B(C_{n} ∪ pK_{1}) = B(P_{n} ∪ pK_{1}) − B(C_{n−1} ∪ pK_{1})

= ∑_{i=0}^{p} \binom{p}{i}B_{n+i−1} − ∑_{j=1}^{n−2}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j−1}

= ∑_{i=0}^{p} \binom{p}{i}B_{n+i−1} + ∑_{j=2}^{n−1}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j}

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

The proof for T (C_{n} ∪ pK_{1}) is similar.

Proposition 6. Let G be a graph with a simplicial vertex v. Then A(G) > A(G − v).

Proof. Let r be the number of neighbors of v in G. We have S(G, k) = (k − r)S(G − v, k) + S(G − v, k − 1). Assuming that G is of order n, we have

B(G) = ∑_{k=0}^{n} S(G, k) = ∑_{k=0}^{n−1} kS(G − v, k) − r ∑_{k=0}^{n−1} S(G − v, k) + ∑_{k=0}^{n−1} S(G − v, k)

= ∑_{k=0}^{n−1}(k − r + 1)S(G − v, k)

and

T (G) = ∑_{k=0}^{n} kS(G, k) = ∑_{k=0}^{n}(k^{2} − kr)S(G − v, k) + ∑_{k=0}^{n} kS(G − v, k − 1)

= ∑_{k=0}^{n−1}(k^{2} − kr)S(G − v, k) + ∑_{k=0}^{n−1}(k + 1)S(G − v, k)

= ∑_{k=0}^{n}(k^{2} − k(r − 1) + 1)S(G − v, k).

We therefore have B(G − v)T (G) − T (G − v)B(G)

= ∑_{k=0}^{n−1} S(G − v, k) ∑_{k′=0}^{n}(k^{′2}−k′(r−1)+1)S(G − v, k′) − ∑_{k=0}^{n−1} kS(G − v, k) ∑_{k′=0}^{n−1}(k′−r+1)S(G − v, k′)

= ∑_{k=0}^{n−1} (S(G − v, k))^{2} (k^{2} − k(r − 1) + 1 − k(k − r + 1))

+ ∑_{k=0}^{n−2} ∑_{k′=k+1}^{n−1} S(G − v, k)S(G − v, k′)(k^{′2}−k′(r−1)+1+k^{2}−k(r−1)+1−k(k′−r+1)−k′(k−r+1))

= ∑_{k=0}^{n−1} (S(G − v, k))^{2} + ∑_{k=0}^{n−2} ∑_{k′=k+1}^{n−1} S(G − v, k)S(G − v, k′) ((k − k′)^{2} + 2) > 0

which implies A(G)−A(G−v) = \frac{T (G)}{B(G)}−\frac{T (G − v)}{B(G − v)} = \frac{B(G − v)T (G) − T (G − v)B(G)}{B(G)B(G − v)} > 0.

Proposition 7. Let G, H and F_{1}, …, F_{r} be r + 2 graphs, and let α_{1}, …, α_{r} be r positive numbers such that

• B(G) = B(H) + ∑_{i=1}^{r} α_{i}B(F_{i})

• T (G) = T (H) + ∑_{i=1}^{r} α_{i}T (F_{i})

• A(F_{i}) < A(H) for i = 1, …, r.

Then A(G) < A(H).

Proof. Since A(F_{i}) < A(H), we have T (F_{i}) < \frac{T (H)B(F_{i})}{B(H)} for i = 1, …, r. Hence

A(G) = \frac{T (G)}{B(G)} = \frac{T (H) + ∑_{i=1}^{r} α_{i}T (F_{i})}{B(H) + ∑_{i=1}^{r} α_{i}B(F_{i})}

< \frac{T (H) + ∑_{i=1}^{r} α_{i} \frac{T (H)B(F_{i})}{B(H)}}{B(H) + ∑_{i=1}^{r} α_{i}B(F_{i})} = \frac{T (H) (B(H) + ∑_{i=1}^{r} α_{i}B(F_{i}))}{B(H) (B(H) + ∑_{i=1}^{r} α_{i}B(F_{i}))}

= \frac{T (H)}{B(H)} = A(H).

3 Inequalities for the Bell numbers

In this section, we show how to derive inequalities for the Bell numbers, using properties related to the average number A(G) of colors in non-equivalent colorings of G. We start by analyzing paths. As already mentioned, P_{n} ∪ pK_{1} is the graph obtained by adding p isolated vertices to a path on n vertices.

Theorem 8. A(P_{n} ∪ (p + 1)K_{1}) < A(P_{n+1} ∪ pK_{1}) for all n ≥ 1 and p ≥ 0.

Proof. It follows from Equations (4) that

B(P_{n} ∪ (p + 1)K_{1}) = B(P_{n+1} ∪ pK_{1}) + B(P_{n} ∪ pK_{1})

and

T (P_{n} ∪ (p + 1)K_{1}) = T (P_{n+1} ∪ pK_{1}) + T (P_{n} ∪ pK_{1}).

Also, we know from Proposition 6 that A(P_{n} ∪ pK_{1}) < A(P_{n+1} ∪ pK_{1}). Hence, it follows from Proposition 7 that A(P_{n} ∪ (p + 1)K_{1}) < A(P_{n+1} ∪ pK_{1}).

Proposition 3 immediately gives the following corollary.

Corollary 9. If n ≥ 1 and p ≥ 0 then

(∑_{i=0}^{p+1} \binom{p + 1}{i}B_{n+i}) (∑_{i=0}^{p} \binom{p}{i}B_{n+i}) < (∑_{i=0}^{p+1} \binom{p + 1}{i}B_{n+i−1}) (∑_{i=0}^{p} \binom{p}{i}B_{n+i+1}) .

Examples 10. For p = 0 and n ≥ 1, Corollary 9 provides the following inequality:

(B_{n} + B_{n+1})B_{n} < (B_{n−1} + B_{n})B_{n+1} ⟺ B_{n}^{2} < B_{n−1}B_{n+1}.

This inequality for the Bell numbers also follows from Proposition 6. Indeed, P_{n} is obtained from P_{n+1} by removing a vertex of degree 1, which implies

A(P_{n}) < A(P_{n+1}) ⟺ \frac{B_{n}}{B_{n−1}} < \frac{B_{n+1}}{B_{n}} ⟺ B_{n}^{2} < B_{n−1}B_{n+1}.

Note that Engel [8] has shown that the sequence (B_{n})_{n≥0} is log-convex, which implies B_{n}^{2} ≤ B_{n−1}B_{n+1} (with a non-strict inequality) for n ≥ 1. Recently, Alzer [2] proved that the sequence (B_{n})_{n≥0} is strictly log-convex by showing that

B_{n−1}B_{n+1} − B_{n}^{2} = \frac{1}{2e^{2}} ∑_{k=2}^{∞} ∑_{j=1}^{k−1} \frac{j^{n−1}(k − j)^{n−1}}{j!(k − j)!} (k − 2j)^{2}

for all n ≥ 2. Since B_{1}^{2} = 1 < 2 = B_{0}B_{2}, this also implies B_{n}^{2} < B_{n−1}B_{n+1} for all n ≥ 1.

As a second example, assume p = 1 and n ≥ 1. Corollary 9 provides the following inequality for the Bell numbers, which also follows from the strict log-convexity of the sequence (B_{n})_{n≥0}:

(B_{n} + B_{n+1} + B_{n+2})(B_{n} + B_{n+1}) < (B_{n−1} + B_{n} + B_{n+1})(B_{n+1} + B_{n+2})
⟺ B_{n}(B_{n} + B_{n+1}) < B_{n−1}(B_{n+1} + B_{n+2}).

For n ≥ 3 and r ≥ 0, we denote H_{n,r} the graph obtained by linking one extremity of P_{r} to one vertex of C_{n} (see Figure 2). For r = 0, H_{n,0} is equal to C_{n}. Also, H_{n,r} ∪ pK_{1} is the graph obtained from H_{n,r} by adding p isolated vertices. We now compare A(H_{3,n−3} ∪ pK_{1}) with A(P_{n+1} ∪ pK_{1}) to derive new inequalities involving the Bell numbers.

Figure 2: The graph H_{n,r}

Theorem 11. A(H_{3,n−3} ∪ pK_{1}) < A(P_{n+1} ∪ pK_{1}) for all n ≥ 4 and p ≥ 0.

Proof. Note first that Equations (3) give B(H_{3,n−3} ∪ pK_{1}) = B(P_{n} ∪ pK_{1}) − B(P_{n−1} ∪ pK_{1}) and T (H_{3,n−3} ∪ pK_{1}) = T (P_{n} ∪ pK_{1}) − T (P_{n−1} ∪ pK_{1}). Hence

A(P_{n+1} ∪ pK_{1}) − A(H_{3,n−3} ∪ pK_{1}) = \frac{T (P_{n+1} ∪ pK_{1})}{B(P_{n+1} ∪ pK_{1})} − \frac{T (H_{3,n−3} ∪ pK_{1})}{B(H_{3,n−3} ∪ pK_{1})}

= \frac{T (P_{n+1} ∪ pK_{1})}{B(P_{n+1} ∪ pK_{1})} − \frac{T (P_{n} ∪ pK_{1}) − T (P_{n−1} ∪ pK_{1})}{B(P_{n} ∪ pK_{1}) − B(P_{n−1} ∪ pK_{1})}

= \frac{T (P_{n+1} ∪ pK_{1}) (B(P_{n} ∪ pK_{1}) − B(P_{n−1} ∪ pK_{1})) − B(P_{n+1} ∪ pK_{1}) (T (P_{n} ∪ pK_{1}) − T (P_{n−1} ∪ pK_{1}))}{B(P_{n+1} ∪ pK_{1})B(H_{3,n−3} ∪ pK_{1})}.

Let f(n, p) be the numerator of the above fraction. It follows from Proposition 3 that

f(n, p) = ∑_{i=0}^{p} \binom{p}{i}B_{n+i+1} (∑_{ℓ=0}^{p} \binom{p}{ℓ}(B_{n+ℓ−1} − B_{n+ℓ−2}))−∑_{i=0}^{p} \binom{p}{i}B_{n+i} (∑_{ℓ=0}^{p} \binom{p}{ℓ}(B_{n+ℓ} − B_{n+ℓ−1})) .

It remains to prove that f(n, p) > 0 for all n ≥ 4 and p > 0. Since B_{n} = \frac{1}{e} ∑_{k=1}^{∞} \frac{k^{n}}{k!} , we have

B_{n} − B_{n−1} = \frac{1}{e} ∑_{k=1}^{∞} (\frac{k^{n}}{k!} − \frac{k^{n−1}}{k!} ) = \frac{1}{e} ∑_{k=2}^{∞} \frac{k^{n−1}}{k!} (k − 1).

Hence e^{2}f(n, p)

= ∑_{i=0}^{p} ∑_{ℓ=0}^{p} ∑_{j=1}^{∞} ∑_{k=2}^{∞} \binom{p}{i}\binom{p}{ℓ}\frac{j^{n+i+1}}{j!} \frac{k^{n+ℓ−2}}{k!} (k − 1) − ∑_{i=0}^{p} ∑_{ℓ=0}^{p} ∑_{j=1}^{∞} ∑_{k=2}^{∞} \binom{p}{i}\binom{p}{ℓ}\frac{j^{n+i}}{j!} \frac{k^{n+ℓ−1}}{k!} (k − 1)

= ∑_{i=0}^{p} ∑_{ℓ=0}^{p} ∑_{j=1}^{∞} ∑_{k=2}^{∞} \binom{p}{i}\binom{p}{ℓ}\frac{j^{n+i}}{j!} \frac{k^{n+ℓ−2}}{k!} (k − 1)(j − k)

= ∑_{i=0}^{p} ∑_{ℓ=0}^{p} ∑_{j>k≥1} \binom{p}{i}\binom{p}{ℓ} (\frac{j^{n+i}k^{n+ℓ−2}}{j!k!} (k − 1)(j − k) − \frac{j^{n+i−2}k^{n+ℓ}}{j!k!} (j − 1)(j − k))

= ∑_{i=0}^{p} ∑_{ℓ=0}^{p} ∑_{j>k≥1} \binom{p}{i}\binom{p}{ℓ}\frac{j^{n−2}k^{n−2}}{j!k!} (j − k) (j^{i+2}k^{ℓ}(k − 1) − j^{i}k^{ℓ+2}(j − 1))

= ∑_{j>k≥1} \frac{j^{n−2}k^{n−2}}{j!k!} (j − k) ((k − 1)j^{2} ∑_{i=0}^{p} \binom{p}{i}j^{i} ∑_{ℓ=0}^{p} \binom{p}{ℓ}k^{ℓ} − (j − 1)k^{2} ∑_{i=0}^{p} \binom{p}{i}j^{i} ∑_{ℓ=0}^{p} \binom{p}{ℓ}k^{ℓ})

= ∑_{j>k≥1} \frac{j^{n−2}k^{n−2}}{j!k!} (j − k)(j + 1)^{p}(k + 1)^{p} ((k − 1)j^{2} − (j − 1)k^{2}) .

Let g(j, k) = (k − 1)j^{2} − (j − 1)k^{2}. We have proved that

e^{2}f(n, p) = ∑_{j>k≥1} \frac{j^{n−2}k^{n−2}}{j!k!} (j − k)(j + 1)^{p}(k + 1)^{p}g(j, k).

Note that g(j, 1) = 1 − j, g(j, 2) = (j − 2)^{2}, and

g(j, k) = j^{2}k − j^{2} − jk^{2} + k^{2} = (j − k)(jk − j − k) = (j − k) (k(\frac{j}{2} − 1) + j(\frac{k}{2} − 1)) .

Hence, g(j, k) > 0 for j > k ≥ 3, and it remains to prove that

∑_{k=1}^{2} ∑_{j=k+1}^{∞} \frac{j^{n−2}k^{n−2}}{j!k!} (j − k)(j + 1)^{p}(k + 1)^{p}g(j, k) > 0.

We have

∑_{k=1}^{2} ∑_{j=k+1}^{∞} \frac{j^{n−2}k^{n−2}}{j!k!} (j − k)(j + 1)^{p}(k + 1)^{p}g(j, k)

= ∑_{j=3}^{∞} 2^{n−3} \frac{j^{n−2}}{j!} 3^{p}(j + 1)^{p}(j − 2)^{3} − ∑_{j=2}^{∞} \frac{j^{n−2}}{j!} 2^{p}(j + 1)^{p}(j − 1)^{2}

≥ 12^{p} (∑_{j=3}^{5} 2^{n−3} \frac{j^{n−2}}{j!} (j − 2)^{3} − ∑_{j=2}^{5} \frac{j^{n−2}}{j!} (j − 1)^{2}) + ∑_{j=6}^{∞} \frac{j^{n−2}}{j!} 2^{p}(j + 1)^{p} (2^{n−3}(j − 2)^{3} − (j − 1)^{2})

= 12^{p} (\frac{1}{6}2^{n−3}3^{n−2} + \frac{8}{24}2^{n−3}4^{n−2} + \frac{27}{120}2^{n−3}5^{n−2} − \frac{1}{2}2^{n−2} − \frac{4}{6}3^{n−2} − \frac{9}{24}4^{n−2} − \frac{16}{120}5^{n−2}) +

∑_{j=6}^{∞} \frac{j^{n−2}}{j!} 2^{p}(j + 1)^{p} (2^{n−3}(j − 2)^{3} − (j − 1)^{2}) .

It is easy to check that

\frac{1}{6}2^{n−3}3^{n−2} + \frac{8}{24}2^{n−3}4^{n−2} + \frac{27}{120}2^{n−3}5^{n−2} − \frac{1}{2}2^{n−2} − \frac{4}{6}3^{n−2} − \frac{9}{24}4^{n−2} − \frac{16}{120}5^{n−2} > 0

for all n ≥ 4, and 2^{n−3}(j − 2)^{3} − (j − 1)^{2} > 0 for all n ≥ 4 and j ≥ 4. Hence f(n, p) > 0.

As shown in the above proof, the above theorem is equivalent to the following inequalities for the Bell numbers. Corollary 12. If n ≥ 4 and p ≥ 0 then

∑_{i=0}^{p} \binom{p}{i}B_{n+i+1} (∑_{ℓ=0}^{p} \binom{p}{ℓ}(B_{n+ℓ−1} − B_{n+ℓ−2})) > ∑_{i=0}^{p} \binom{p}{i}B_{n+i} (∑_{ℓ=0}^{p} \binom{p}{ℓ}(B_{n+ℓ} − B_{n+ℓ−1})) .

Example 13. For p = 0 and n ≥ 4 we get the following inequality for the Bell numbers:

B_{n+1}(B_{n−1} − B_{n−2}) > B_{n}(B_{n} − B_{n−1}).

We now compare the average number of colors in colorings of C_{n} ∪ pK_{1} with the average number of colors in colorings of H_{3,n−3} ∪ pK_{1}. Lemma 14. If n ≥ 3, r ≥ 0 and p ≥ 0 then

B(H_{n,r} ∪ pK_{1}) = \begin{cases}∑_{i=0}^{\frac{n−3}{2}} \binom{\frac{n−3}{2}}{i}B(H_{3,2i+r} ∪ pK_{1}), & if n is odd; \\ ∑_{i=0}^{\frac{n−4}{2}} \binom{\frac{n−4}{2}}{i}B(H_{3,2i+r+1} ∪ pK_{1}) + B(P_{2+r} ∪ pK_{1}), & if n is even \end{cases}

and

T (H_{n,r} ∪ pK_{1}) = \begin{cases}∑_{i=0}^{\frac{n−3}{2}} \binom{\frac{n−3}{2}}{i}T (H_{3,2i+r} ∪ pK_{1}), & if n is odd; \\ ∑_{i=0}^{\frac{n−4}{2}} \binom{\frac{n−4}{2}}{i}T (H_{3,2i+r+1} ∪ pK_{1}) + T (P_{2+r} ∪ pK_{1}), & if n is even. \end{cases}

Proof. The result is clearly valid for n = 3. For n = 4, Equations (3) and (4) give

B(H_{4,r} ∪ pK_{1}) = B(P_{4+r} ∪ pK_{1}) − B(H_{3,r} ∪ pK_{1})

= (B(H_{3,r+1} ∪ pK_{1}) + B(P_{3+r} ∪ pK_{1})) − (B(P_{3+r} ∪ pK_{1}) − B(P_{2+r} ∪ pK_{1}))

= B(H_{3,r+1} ∪ pK_{1}) + B(P_{2+r} ∪ pK_{1}).

Similarly, T (H_{4,r}∪pK_{1})=T (H_{3,r+1}∪pK_{1})+T (P_{2+r}∪pK_{1}) which shows that the result is valid for n = 4. For larger values of n, we proceed by induction. Hence, it is sufficient to prove that B(H_{n,r} ∪pK_{1}) = B(H_{3,n−3+r} ∪pK_{1})+B(H_{n−2,r} ∪pK_{1}) and T (H_{n,r} ∪pK_{1})=T (H_{3,n−3+r} ∪ pK_{1})+T (H_{n−2,r} ∪ pK_{1}). Using Equations (3) and (4), we get

B(H_{n,r} ∪ pK_{1}) = B(P_{n+r} ∪ pK_{1}) − B(H_{n−1,r} ∪ pK_{1})

= (B(H_{3,n−3+r}∪pK_{1})+B(P_{n+r−1}∪pK_{1})) − (B(P_{n+r−1}∪pK_{1})−B(H_{n−2,r}∪pK_{1}))

= B(H_{3,n−3+r} ∪ pK_{1}) + B(H_{n−2,r} ∪ pK_{1}).

The proof for T (H_{n,r} ∪ pK_{1}) is similar.

We are now ready to compare A(C_{n} ∪ pK_{1}) with A(H_{3,n−3} ∪ pK_{1}).

Theorem 15. A(C_{n} ∪ pK_{1}) < A(H_{3,n−3} ∪ pK_{1}) for all n ≥ 3 and p ≥ 0.

Proof. Lemma 14 (with r = 0) gives the following:

B(C_{n} ∪ pK_{1}) = \begin{cases}B(H_{3,n−3} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−5}{2}} B(H_{3,2i} ∪ pK_{1}), & if n is odd; \\ B(H_{3,n−3} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−6}{2}} B(H_{3,2i+1} ∪ pK_{1}) + B(P_{2} ∪ pK_{1}), & if n is even \end{cases}

and

T (C_{n} ∪ pK_{1}) = \begin{cases}T (H_{3,n−3} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−5}{2}} T (H_{3,2i} ∪ pK_{1}), & if n is odd; \\ T (H_{3,n−3} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−6}{2}} T (H_{3,2i+1} ∪ pK_{1}) + T (P_{2} ∪ pK_{1}), & if n is even. \end{cases}

We know from Proposition 6 that A(P_{2} ∪ pK_{1}) < A(C_{3} ∪ pK_{1}) = A(H_{3,0} ∪ pK_{1}). Since H_{3,n−3} ∪ pK_{1} is obtained from H_{3,i} ∪ pK_{1} (i < n − 3) by repeatedly adding vertices of degree 1, we have A(P_{2} ∪ pK_{1}) < A(H_{3,i} ∪ pK_{1}) < A(H_{3,n−3} ∪ pK_{1}) for i = 0, …, n − 5. Proposition 7 therefore implies A(C_{n} ∪ pK_{1}) < A(H_{3,n−3} ∪ pK_{1}).

Equations (3) give B(H_{3,n−3}∪pK_{1}) = B(P_{n}∪pK_{1})−B(P_{n−1}∪pK_{1}) and T (H_{3,n−3}∪pK_{1}) = T (P_{n} ∪ pK_{1}) − T (P_{n−1} ∪ pK_{1}). Hence, Propositions 3 and 5 immediately give the following corollary.

Corollary 16. If n ≥ 3 and p ≥ 0 then

(∑_{j=1}^{n−1}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j+1}) (∑_{i=0}^{p} \binom{p}{i}(B_{n+i−1} − B_{n+i−2}))

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

Example 17. For p = 0 and n ≥ 3, the above corollary provides the following inequalities for the Bell numbers:

(B_{n−1} − B_{n−2}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1} < (B_{n} − B_{n−1}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j}.

It is easy to check that this inequality is also valid for n = 2.

We now compare the average number of colors in colorings of paths with the average number of colors in colorings of cycles.

Theorem 18. A(C_{n} ∪ pK_{1}) > A(P_{n} ∪ pK_{1}) for all n ≥ 5 and p ≥ 0.

Proof. We know from Theorems 11 and 15 that A(P_{n}∪pK_{1}) > A(H_{3,n−4}∪pK_{1}) > A(C_{n−1}∪pK_{1}), which implies that

T (C_{n−1}∪pK_{1}) < \frac{T (P_{n} ∪ pK_{1})B(C_{n−1}∪pK_{1})}{B(P_{n}∪pK_{1})}.

Equations (3) show that B(C_{n} ∪ pK_{1}) = B(P_{n} ∪ pK_{1}) − B(C_{n−1} ∪ pK_{1}) and T (C_{n} ∪ pK_{1}) = T (P_{n} ∪ pK_{1}) − T (C_{n−1} ∪ pK_{1}). Hence:

A(C_{n} ∪ pK_{1}) = \frac{T (C_{n} ∪ pK_{1})}{B(C_{n} ∪ pK_{1})} = \frac{T (P_{n} ∪ pK_{1}) − T (C_{n−1} ∪ pK_{1})}{B(P_{n} ∪ pK_{1}) − B(C_{n−1} ∪ pK_{1})}

> \frac{T (P_{n} ∪ pK_{1}) − \frac{T (P_{n}∪pK_{1})B(C_{n−1}∪pK_{1})}{B(P_{n}∪pK_{1})}}{B(P_{n} ∪ pK_{1}) − B(C_{n−1} ∪ pK_{1})}

= \frac{T (P_{n} ∪ pK_{1}) (B(P_{n} ∪ pK_{1}) − B(C_{n−1} ∪ pK_{1}))}{B(P_{n} ∪ pK_{1}) (B(P_{n} ∪ pK_{1}) − B(C_{n−1} ∪ pK_{1}))} = \frac{T (P_{n} ∪ pK_{1})}{B(P_{n} ∪ pK_{1})} = A(P_{n} ∪ pK_{1}).

Propositions 3 and 5 immediately give the following corollary. Corollary 19. If n ≥ 5 and p ≥ 0 then

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

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

Example 20. For p = 0 and n ≥ 5 the above corollary provides the following inequality for the Bell numbers:

B_{n−1} ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1} > B_{n} ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j}.

Finally, we compare A(C_{n} ∪ pK_{1}) with A(C_{n−2} ∪ (p + 2)K_{1}). Lemma 21. If n ≥ 3 and p ≥ 0 then

B(C_{n} ∪ (p + 2)K_{1}) = B(H_{n,2} ∪ pK_{1}) + 2B(H_{n,1} ∪ pK_{1}) + B(H_{n,0} ∪ pK_{1})
T (C_{n} ∪ (p + 2)K_{1}) = T (H_{n,2} ∪ pK_{1}) + 2T (H_{n,1} ∪ pK_{1}) + T (H_{n,0} ∪ pK_{1}).

Proof. Equations (4) give

B(C_{n} ∪ (p + 2)K_{1}) = B(H_{n,1} ∪ (p + 1)K_{1}) + B(C_{n} ∪ (p + 1)K_{1})

= (B(H_{n,2} ∪ pK_{1}) + B(H_{n,1} ∪ pK_{1})) + (B(H_{n,1} ∪ pK_{1}) + B(H_{n,0} ∪ pK_{1}))

= B(H_{n,2} ∪ pK_{1}) + 2B(H_{n,1} ∪ pK_{1}) + B(H_{n,0} ∪ pK_{1}).

The proof is similar for T (C_{n} ∪ (p + 2)K_{1}). Theorem 22. A(C_{n} ∪ pK_{1}) > A(C_{n−2} ∪ (p + 2)K_{1}) for all n ≥ 5 and p ≥ 0. Proof. We divide the proof into two cases, according to the parity of n. Case 1: n is odd. Lemma 14 (with r = 0) shows that

B(C_{n} ∪ pK_{1}) = ∑_{i=0}^{\frac{n−3}{2}} B(H_{3,2i} ∪ pK_{1}) and T (C_{n} ∪ pK_{1}) = ∑_{i=0}^{\frac{n−3}{2}} T (H_{3,2i} ∪ pK_{1})

and Lemmas 21 and 14 give B(C_{n−2} ∪ (p + 2)K_{1}) = B(H_{n−2,2} ∪ pK_{1}) + 2B(H_{n−2,1} ∪ pK_{1}) + B(H_{n−2,0} ∪ pK_{1})

= ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i+2} ∪ pK_{1}) + 2 ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i+1} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i} ∪ pK_{1})

= ∑_{i=1}^{\frac{n−3}{2}} \binom{\frac{n−5}{2}}{i − 1}B(H_{3,2i} ∪ pK_{1}) + 2 ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i+1} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i} ∪ pK_{1})

= ∑_{i=1}^{\frac{n−5}{2}} (\binom{\frac{n−5}{2}}{i − 1} + \binom{\frac{n−5}{2}}{i}) B(H_{3,2i} ∪ pK_{1}) + B(H_{3,n−3} ∪ pK_{1}) + B(H_{3,0} ∪ pK_{1})

+ 2 ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i+1} ∪ pK_{1})

= ∑_{i=0}^{\frac{n−3}{2}} \binom{\frac{n−3}{2}}{i}B(H_{3,2i} ∪ pK_{1}) + 2 ∑_{i=0}^{\frac{n−5}{2}} \binom{\frac{n−5}{2}}{i}B(H_{3,2i+1} ∪ pK_{1})

= B(C_{n} ∪ pK_{1}) + ∑_{i=1}^{n−4} α_{i}B(H_{3,i} ∪ pK_{1}),

where

α_{i} = \begin{cases}(\frac{n−3}{2} ; \frac{i}{2}) − 1, & if i is even; \\ 2(\frac{n−5}{2} ; \frac{i−1}{2}), & if i is odd. \end{cases}

Similarly, T (C_{n−2} ∪ (p + 2)K_{1}) = T (C_{n} ∪ pK_{1}) + ∑_{i=1}^{n−4} α_{i}T (H_{3,i} ∪ pK_{1}). Moreover, we know from Theorems 11 and 18 that

A(H_{3,n−4} ∪ pK_{1}) < A(P_{n} ∪ pK_{1}) < A(C_{n} ∪ pK_{1}).

Also, given i ∈ {1, …, n−5}, H_{3,n−4} ∪pK_{1} is obtained from H_{3,i} ∪pK_{1} by repeatedly adding vertices of degree 1, and it follows from Proposition 6 that

A(H_{3,i} ∪ pK_{1}) < A(H_{3,n−4} ∪ pK_{1}) < A(C_{n} ∪ pK_{1}).

Since all α_{i} are strictly positive, we can conclude from Proposition 7 that A(C_{n−2} ∪ (p + 2)K_{1}) < A(C_{n} ∪ (p + 2)K_{1}).

Case 2: n is even. The proof is similar to the previous case. More precisely, Lemma 14 shows that

B(C_{n} ∪ pK_{1}) = ∑_{i=0}^{\frac{n−4}{2}} B(H_{3,2i+1} ∪ pK_{1}) + B(P_{2} ∪ pK_{1})

and

T (C_{n} ∪ pK_{1}) = ∑_{i=0}^{\frac{n−4}{2}} T (H_{3,2i+1} ∪ pK_{1}) + T (P_{2} ∪ pK_{1})

and lemmas 21 and 14 give B(C_{n−2} ∪ (p + 2)K_{1}) = B(H_{n−2,2} ∪ pK_{1}) + 2B(H_{n−2,1} ∪ pK_{1}) + B(H_{n−2,0} ∪ pK_{1})

= (∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+3}∪pK_{1})+B(P_{4}∪pK_{1})) +2 (∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+2}∪pK_{1})+B(P_{3}∪pK_{1}))

+ (∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+1} ∪ pK_{1}) + B(P_{2} ∪ pK_{1}))

= ∑_{i=1}^{\frac{n−4}{2}} \binom{\frac{n−6}{2}}{i − 1}B(H_{3,2i+1} ∪ pK_{1}) + 2 ∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+2} ∪ pK_{1}) + ∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+1} ∪ pK_{1})

+ B(P_{4} ∪ pK_{1}) + 2B(P_{3} ∪ pK_{1}) + B(P_{2} ∪ pK_{1})

= ∑_{i=1}^{\frac{n−6}{2}} (\binom{\frac{n−6}{2}}{i − 1} + \binom{\frac{n−6}{2}}{i}) B(H_{3,2i+1} ∪ pK_{1}) + B(H_{3,n−3} ∪ pK_{1}) + B(H_{3,1} ∪ pK_{1})

+ 2 ∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+2} ∪ pK_{1}) + B(P_{4} ∪ pK_{1}) + 2B(P_{3} ∪ pK_{1}) + B(P_{2} ∪ pK_{1})

= ∑_{i=0}^{\frac{n−4}{2}} \binom{\frac{n−4}{2}}{i}B(H_{3,2i+1} ∪ pK_{1}) + 2 ∑_{i=0}^{\frac{n−6}{2}} \binom{\frac{n−6}{2}}{i}B(H_{3,2i+2} ∪ pK_{1})

+ B(P_{4} ∪ pK_{1}) + 2B(P_{3} ∪ pK_{1}) + B(P_{2} ∪ pK_{1})

= B(C_{n} ∪ pK_{1}) + ∑_{i=2}^{n−4} α_{i}B(H_{3,i} ∪ pK_{1}) + B(P_{4} ∪ pK_{1}) + 2B(P_{3} ∪ pK_{1})

where

α_{i} = \begin{cases}(\frac{n−4}{2} ; \frac{i−1}{2}) − 1, & if i is odd; \\ 2(\frac{n−6}{2} ; \frac{i−2}{2}), & if i is even. \end{cases}

Similarly,

T (C_{n−2} ∪ (p + 2)K_{1}) = T (C_{n} ∪ pK_{1}) + ∑_{i=2}^{n−4} α_{i}T (H_{3,i} ∪ pK_{1}) + T (P_{4} ∪ pK_{1}) + 2T (P_{3} ∪ pK_{1}).

As already mentioned, we know that

A(H_{3,i} ∪ pK_{1}) < A(H_{3,n−4} ∪ pK_{1}) < A(P_{n} ∪ pK_{1}) < A(C_{n} ∪ pK_{1})

for i = 2, …, n − 4. Also, P_{n} ∪ pK_{1} is obtained from P_{3} ∪ pK_{1} by repeatedly adding vertices of degree 1, and it follows from Proposition 6 that

A(P_{3} ∪ pK_{1}) < A(P_{4} ∪ pK_{1}) < A(P_{n} ∪ pK_{1}) < A(C_{n} ∪ pK_{1}).

Since all α_{i} are strictly positive, we conclude from Proposition 7 that A(C_{n−2} ∪ (p + 2)K_{1}) < A(C_{n} ∪ (p + 2)K_{1}).

Proposition 5 immediately gives the following corollary.

Corollary 23. If n ≥ 5 and p ≥ 0 then

(∑_{j=1}^{n−3}(−1)^{j+1} ∑_{i=0}^{p+2} \binom{p + 2}{i}B_{n+i−j−1}) (∑_{j=1}^{n−1}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j})

< (∑_{j=1}^{n−3}(−1)^{j+1} ∑_{i=0}^{p+2} \binom{p + 2}{i}B_{n+i−j−2}) (∑_{j=1}^{n−1}(−1)^{j+1} ∑_{i=0}^{p} \binom{p}{i}B_{n+i−j+1}) .

Example 24. For p = 0 and n ≥ 5, the above corollary provides the following inequalities for the Bell numbers:

∑_{j=1}^{n−3}(−1)^{j+1}(B_{n−j−1} + 2B_{n−j} + B_{n−j+1}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j}

< ∑_{j=1}^{n−3}(−1)^{j+1}(B_{n−j−2} + 2B_{n−j−1} + B_{n−j}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1}

⟺ (∑_{j=2}^{n−2}(−1)^{j}B_{n−j} + 2 ∑_{j=1}^{n−3}(−1)^{j+1}B_{n−j} + ∑_{j=0}^{n−4}(−1)^{j}B_{n−j}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j}

< (∑_{j=2}^{n−2}(−1)^{j}B_{n−j−1} + 2 ∑_{j=1}^{n−3}(−1)^{j+1}B_{n−j−1} + ∑_{j=0}^{n−4}(−1)^{j}B_{n−j−1}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1}

⟺ (B_{n} + B_{n−1} + 7(−1)^{n}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j} < (B_{n−1} + B_{n−2} + 3(−1)^{n}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1}.

It is easy to check that this inequality is also valid for n = 4.

4 Conclusion

We have shown how the average number of colors in the non-equivalent colorings of a graph G helps to derive inequalities for the Bell numbers. Among the inequalities, we have shown that

• B_{n}^{2} < B_{n−1}B_{n+1} for all n ≥ 1,

• B_{n}(B_{n} + B_{n+1}) < B_{n−1}(B_{n+1} + B_{n+2}) for all n ≥ 1,

• B_{n}(B_{n} − B_{n−1}) < B_{n+1}(B_{n−1} − B_{n−2}) for all n ≥ 4,

• (B_{n−1} − B_{n−2}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1} < (B_{n} − B_{n−1}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j} for all n ≥ 2,

• B_{n} ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j} < B_{n−1} ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1} for all n ≥ 5,

• (B_{n} + B_{n−1} + 7(−1)^{n}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j} < (B_{n−1} + B_{n−2} + 3(−1)^{n}) ∑_{j=1}^{n−1}(−1)^{j+1}B_{n−j+1}

for all n ≥ 4.

We have no doubt that other inequalities for the Bell numbers can be generated by comparing the average numbers of colors in the non-equivalent colorings of other types of graphs.

References

[1] R. Absil, E. Camby, A. Hertz, and H. Mélot, A sharp lower bound on the number of non-equivalent colorings of graphs of order n and maximum degree n−3, Discrete Appl. Math. 234 (2018), 3–11.

[2] H. Alzer, On Engel’s inequality for Bell numbers, J. Integer Sequences 22 (2019), Article 19.7.1.

[3] R. Diestel, Graph Theory, Springer-Verlag, 2000.

[4] G. Dobiński, Summierung der Reihe ∑ n^{m}/n! für m = 1, 2, 3, 4, 5, …, Arch. Math. Phys. 61 (1877), 333–336.

[5] F. M. Dong, K. M. Koh, and K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific, 2005.

[6] B. Duncan, Bell and Stirling numbers for disjoint unions of graphs, Congressus Numerantium 106 (2010), 215–217.

[7] B. Duncan and R. B. Peele, Bell and Stirling numbers for graphs J. Integer Sequences 12 (2009), Article 09.7.1.

[8] K. Engel, On the average rank of an element in a filter of the partition lattice, J. Comb. Theory Ser. A 65 (1994), 67–78.

[9] D. Galvin and D. T. Thanh, Stirling numbers of forests and cycles, Electron. J. Comb. 20 (2013), Paper P73.

[10] A. Hertz and H. Mélot, Counting the number of non-equivalent vertex colorings of a graph, Discrete Appl. Math. 203 (2016), 62–71.

[11] Z. Kereskényi-Balogh and G. Nyul, Stirling numbers of the second kind and Bell numbers for graphs, Australasian J. Comb. 58 (2014), 264–274.

[12] A. M. Odlyzko and L. B. Richmond, On the number of distinct block sizes in partitions of a set, J. Comb. Theory Ser. A 38 (1985), 170–181.

2020 Mathematics Subject Classification: Primary 11B73; Secondary 05C15. Keywords: Bell number, Stirling number, graph coloring.

(Concerned with sequences \underline{A005493} and \underline{A141390}.)

Received March 9 2021; revised versions received October 13 2021; December 6 2021. Published in Journal of Integer Sequences, December 21 2021.

Return to Journal of Integer Sequences home page.