In 1940, Birkhoff posed an open problem of counting all finite lattices on n elements. Recently, Bhavale counted all non-isomorphic lattices on n elements, containing up to four reducible elements, and having nullity up to three. Further, Aware and Bhavale counted all non-isomorphic lattices on n elements, containing up to five comparable reducible elements, and having nullity up to three. In this paper, we count all non-isomorphic lattices on n elements, containing five reducible elements, and having nullity three.
In \(1940\), Birkhoff [7] raised the open problem, compute for small \(n\) all non-isomorphic posets/lattices on a set of \(n\) elements. There were attempts to solve this problem by many authors. In \(2002\), Brinkmann and Mckay [8] enumerated all non-isomorphic posets with \(15\) and \(16\) elements. The work of enumeration of all non-isomorphic (unlabeled) posets is still in progress for \(n\geq 17\). In the same year, Heitzig and Reinhold [11] counted all non-isomorphic (unlabeled) lattices on up to \(18\) elements. For further details about counting of lattices, reader may refer [9] and [12].
In \(2002\), Thakare et al. [14] counted all non-isomorphic lattices on \(n\) elements, containing exactly two reducible elements. Recently, Bhavale and Aware [4] counted all non-isomorphic lattices on \(n\) elements, containing exactly three reducible elements. Bhavale and Aware [3] also counted all non-isomorphic lattices on \(n\) elements, and having nullity up to two. Bhavale [2] counted all non-isomorphic lattices on \(n\) elements, containing up to four reducible elements, and having nullity up to three. Aware and Bhavale [1] counted all non-isomorphic lattices on \(n\) elements, containing up to five comparable reducible elements, and having nullity up to three (see [1] also). In this paper, we count all non-isomorphic lattices on \(n\) elements, containing exactly five reducible elements, and having nullity three.
Let \(\leq\) be a partial order relation on a non-empty set \(P\), and let \((P,\leq)\) be a poset. Elements \(x,y \in P\) are said to be \(comparable\), if either \(x \leq y\) or \(y\leq x\). A poset is called a chain if any two elements in it are comparable. Elements \(x,y \in P\) are said to be \(incomparable\), denoted by \(x||y\), if \(x,y\) are not comparable. An element \(c\in P\) is a lower bound (an upper bound) of \(a,b\in P\) if \(c\leq a,c\leq b(a\leq c,b\leq c)\). A meet of \(a,b \in P\), denoted by \(a \wedge b\), is defined as the greatest lower bound of \(a\) and \(b\). A join of \(a,b\in P\), denoted by \(a \vee b\), is defined as the least upper bound of \(a\) and \(b\). A poset \(L\) is a \(lattice\) if \(a \wedge b\) and \(a \vee b\), exist in \(L\), \(\forall a,b\in L\). Lattices \(L_1\) and \(L_2\) are isomorphic (in symbol, \(L_1\cong L_2\)), and the map \(\phi:L_1\to L_2\) is an isomorphism if and only if \(\phi\) is one-to-one and onto, and \(a \leq b\) in \(L_1\) if and only if \(\phi(a) \leq \phi(b)\) in \(L_2\). Algebraically, \(\phi : L_1 \to L_2\) is an isomorphism if and only if \(\phi\) is one-to-one and onto, and preserves both meet and join for any two elements.
An element \(b\) in \(P\) covers an element \(a\) in \(P\) if \(a<b\), and there is no element \(c\) in \(P\) such that \(a<c<b\). Denote this fact by \(a\prec b\), and say that pair \(<a, b>\) is a \(covering\) or an \(edge\). If \(a\prec b\) then \(a\) is called a lower cover of \(b\), and \(b\) is called an upper cover of \(a\). An element of a poset \(P\) is called doubly irreducible if it has at most one lower cover and at most one upper cover in \(P\). Let \(Irr(P)\) denote the set of all doubly irreducible elements in the poset \(P\). Let \(Irr^*(P)= \{x \in Irr(P):x\) has exactly one upper cover and exactly one lower cover in \(P\}\). The set of all coverings in \(P\) is denoted by \(E(P)\). The graph on a poset \(P\) with edges as covering relations is called the cover graph and is denoted by \(C(P)\). The number of coverings in a chain is called length of the chain.
The nullity of a graph \(G\) is given by \(m-n+c\), where \(m\) is the number of edges in \(G\), \(n\) is the number of vertices in \(G\), and \(c\) is the number of connected components of \(G\). Bhavale and Waphare [5] defined nullity of a poset \(P\), denoted by \(\eta(P)\), to be the nullity of its cover graph \(C(P)\). For \(a<b\), the interval \([a,b]=\{x\in P:a\leq x\leq b\}\), and \([a,b)=\{x\in P:a\leq x<b\}\); similarly, \((a,b)\) and (\(a,b]\) can also be defined. For integer \(n\geq 3\), crown is a partially ordered set \(\{x_1,y_1,x_2,y_2,x_3,y_3,\ldots,x_n,y_n\}\) in which \(x_i\leq y_i\), \(y_i\geq x_{i+1}\), for \(i=1,2,\ldots,n-1\), and \(x_1\leq y_n\) are the only comparability relations.
An element \(x\) in a lattice \(L\) is \(join\)–\(reducible\)(\(meet\)–\(reducible\)) in \(L\) if there exist \(y,z \in L\) both distinct from \(x\), such that \(y\vee z=x (y\wedge z=x)\). An element \(x\) in a lattice \(L\) is \(reducible\) if it is either join-reducible or meet-reducible. \(x\) is \(join\)–\(irreducible\)(\(meet\)–\(irreducible\)) if it is not join-reducible(meet-reducible); \(x\) is \(doubly\) \(irreducible\) if it is both join-irreducible and meet-irreducible. The set of all doubly irreducible elements in \(L\) is denoted by \(Irr(L)\), and its complement in \(L\) is denoted by \(Red(L)\). An ear of a loopless connected graph \(G\) is a subgraph of G which is a maximal path in which all internal vertices are of degree \(2\) in \(G\). Trivial ear is an ear containing no internal vertices. A non-trivial ear is an ear which is not an edge. A vertex of a graph is called pendant if its degree is one.
Definition 2.1. [15] A finite lattice of order \(n\) is called dismantlable if there exists a chain \(L_{1} \subset L_{2} \subset \ldots\subset L_{n}(=L)\) of sublattices of \(L\) such that \(|L_{i}| = i\), for all \(i\).
Theorem 2.2. [13] A finite lattice is dismantlable if and only if it contains no crown.
The concepts of ‘1-sum’ and ‘2-sum’ are introduced by Bhavale and Waphare [6]. Let \(P_1\) and \(P_2\) be disjoint posets. Let \(a \in P_1\). Define a partial order on \(P = P_1 \cup P_2\) with respect to \(a\) as follows. For \(x, y \in P\), we say that \(x \leq y\) in \(P\) if \(x, y \in P_1\) and \(x \leq y\) in \(P_1\) or \(x, y \in P_2\) and \(x \leq y\) in \(P_2\) or \(x \in P_1, y \in P_2\) and \(x \leq a\) in \(P_1\). It is easy to see that \(P\) is a poset containing \(P_1\) and \(P_2\) as subposets. The procedure for obtaining \(P\) in this way is called an up 1-sum of \(P_1\) with \(P_2\) with respect to \(a\), denoted by \(P_1 ]_a P_2\). A diagram of \(P\) is obtained by placing a diagram of \(P_1\) and a diagram of \(P_2\) side by side in such a way that the minimal elements of \(P_2\) are at higher positions than \(a\) and then by adding the coverings \(<a, x>\) for all \(x \in S\), the set of all minimal elements of \(P_2\). This clearly gives \(|E(P)| = |E(P_1)| + |E(P_2)| + |S|\).
Dually, one can define a down 1-sum of two posets. If \(P\) is a down 1-sum of \(P_1\) with \(P_2\) with respect to \(a\) in \(P_1\) then we write \(P = P_1 ]^a P_2\). We call the element \(a\) an adjunct element of the 1-sum. We say that \(P\) is a 1-sum of posets \(P_1\) and \(P_2\) with respect to an element \(a \in P_1\) if \(P\) is either an up 1-sum or a down 1-sum of \(P_1\) and \(P_2\) with respect to \(a\). A 1-sum \(P_1 ]_a P_2\) or \(P_1 ]^a P_2\) is called trivial 1-sum if \(P_2\) is a chain and \(a\) is respectively a maximal or a minimal element of \(P_1\); otherwise, we say that the 1-sum is non-trivial.
The concept of adjunct operation of lattices, is introduced by Thakare et al. [14]. Bhavale and Waphare [6] extended the concept of adjunct of lattices to 2-sum of posets.
A 2-sum of the posets \(P_1\) and \(P_2\) with respect to a pair \((a, b)\) with \(a < b\) but \(a \not\prec b\) in \(P_1\), is the poset \(P = P_1 \cup P_2\) with a partial order defined on \(P\), which is the union of the partial orders in \(P_1 ]_a P_2\) and \(P_1 ]^b P_2\). We denote the 2-sum of the posets \(P_1\) and \(P_2\) with respect to a pair \((a, b)\) by \(P_1 ]_a^b P_2\). The pair \((a, b)\) is called an adjunct pair of the 2-sum.
A lattice \(L\) is called an adjunct of lattices \(L_1,L_2,\ldots,L_k,\) if it is of the form \(L = L_1 ]^{b_1}_{a_1} L_2 \cdots ]^{b_{k-1}}_{a_{k-1}} L_k\). Following result is due to Thakare et al. [14].
Theorem 2.3. [14] A finite lattice is dismantlable if and only if it is an adjunct of chains.
Corollary 2.4. [4] A dismantlable lattice with \(n\) elements has nullity \(k\) if and only if it is an adjunct of \(k+1\) chains.
According to Bhavale and Waphare [5], if a dismantlable lattice contains \(r\) reducible elements and has nullity \(k \geq 1\) then \(2 \leq r \leq 2k\).
If \(M\) and \(N\) are two disjoint posets then the direct sum, denoted by \(M \oplus N\), is defined by taking the following order relation on \(M \cup N\) : \(x \leq y\) if and only if \(x, y \in M\) and \(x \leq y\) in \(M\), or \(x, y \in N\) and \(x \leq y\) in \(N\), or \(x \in M, y \in N\). In general, \(M \oplus N \neq N \oplus M\). Also, if \(M\) and \(N\) are lattices then \(|E(M \oplus N)|=|E(M)|+|E(N)|+1\).
Thakare et al. [14] defined a block as a finite lattice in which the largest element is join-reducible and the least element is meet-reducible. Let \(L\) be a finite lattice which is not a chain. Then \(L\) contains a unique maximal sublattice which is a block, called the maximal block. The lattice \(L\) has the form \(C_1\oplus\textbf{B}\) or \(\textbf{B}\oplus C_2\) or \(L=C_1\oplus\textbf{B}\oplus C_2\), where \(C_1,C_2\) are the chains and \(\textbf{B}\) is the maximal block. It follows that \(\eta(\textbf{B}) = \eta(L)\).
Bhavale and Waphare [5] introduced the concepts namely, retractible element, basic retract, basic block, and basic block associated to a poset.
Definition 2.5. [5] Let \(P\) be a poset. Let \(x \in Irr(P)\). Then \(x\) is called a retractible element of \(P\) if it satisfies either of the following conditions.
1. There are no \(y,z \in Red(P)\) such that \(y \prec x \prec z\).
2. There are \(y,z \in Red(P)\) such that \(y \prec x \prec z\) and there is no other directed path from \(y\) to \(z\) in \(P\).
Definition 2.6. [5] A poset \(P\) is a \(basic\) \(retract\) if no element of \(Irr^{*}(P)\) is retractible in the poset \(P\).
Definition 2.7. [5] Let \(P\) be a poset. Consider a (Hasse) diagram of \(P\). If \(Irr^*(P) = \emptyset\) then we say that \(P\) is a basic retract associated to itself; otherwise, go on removing elements of \(Irr^*(P)\) one by one as long as \(\eta(P)\) does not alter. Ultimately we get a subposet \(P'\) of \(P\) such that no element of \(Irr^*(P')\) is retractible in \(P'\). The resultant subposet \(P'\) of \(P\) is called a basic retract associated to \(P\).
Definition 2.8. [5] A poset \(P\) is a basic block if it is one element or \(Irr(P) = \emptyset\) or removal of any doubly irreducible element reduces nullity by one.
Definition 2.9. [5] \(B\) is a \(basic\) \(block\) \(associated\) \(to\) \(a\) \(poset\) \(P\) if \(B\) is obtained from the basic retract associated to \(P\) by successive removal of all the pendant vertices.
Theorem 2.10. [5] Let \(B\) be a basic retract associated to a poset \(P\). Then \(Red(B) = Red(P)\) and \(\eta(B) = \eta(P)\).
For the other definitions, notation, and terminology see [10] and [16].
Bhavale and Waphare [5] introduced the concept of RC-lattices as the class of lattices in which the reducible elements are all lying on a chain. Using Theorem 2.2, they have proved that RC-lattices are dismantlable. Interestingly, the lattices on up to three reducible elements are RC-lattices.
Let \({\mathscr L}(n; r, k)\) denote the class of all non-isomorphic RC-lattices on \(n\) elements such that each lattice in it has nullity \(k\) and contains \(r\) reducible elements. Note that there is only one lattice (i.e., a chain) having nullity zero. Therefore \({\mathscr L}(n; 0, 0)\) consists of the chain on \(n\) elements.
Theorem 3.1. [14] For an integer \(n \geq 4\), \[|{\mathscr L}(n; 2, 1)| = \left \{ \begin{array}{lll} \dfrac{m(m-1)(4m+1)}{6} & \text{if} & n = 2m + 1; \\ & & \\ \dfrac{m(m-1) (4m-5)}{6} & \text{if} & n = 2m. \end{array} \right.\]
Recently, Bhavale and Aware [3] counted all non-isomorphic lattices having nullity up to two. Further, Aware and Bhavale [1] counted all non-isomorphic lattices containing up to five comparable reducible elements, and having nullity up to three (see also [1] and [4]).
Bhavale [2] defined the class \({\mathcal L}'(n)\) as the subclass of \({\mathscr L}(n; 2, 1)\), containing the lattices in which \(1\) is the reducible element.
Lemma 3.2. [2] For \(n \geq 4\), \(|{\mathcal L}'(n)| = \displaystyle\sum_{i=0}^{n-4} \left\lfloor \frac{n-i-2}{2} \right\rfloor\).
In Section 4, we count the class of all non-isomorphic dismantlable lattices on \(n\) elements such that each lattice in it has nullity three, and at least two of the five reducible elements in each lattice in it are incomparable. For that purpose we need the following remark due to Bhavale [2].
Remark 3.3. [2] For any \(j \geq 3\), let \(S_j\) be the class of all non-isomorphic posets \(Y\) on \(j\) elements such that \(Y = C ]_x C'\), where \(C, C'\) are chains. Then \(Y \in S_j\) if and only if \(Y \oplus \{1\} \in {\mathcal L}' (j+1)\). Therefore \(|S_j| = |{\mathcal L}' (j+1)|\). If \(s_j = |S_j|\) for all \(j\), then \(s_j = |{\mathcal L}' (j+1)| = \displaystyle\sum_{i=0}^{j-3} \left\lfloor \frac{j-i-1}{2} \right\rfloor\).
It is known that the lattices of nullity up to two are RC-lattices (see [3]). But a lattice of nullity at least three may not be RC-lattice. We define the class of RI-lattices as the class of lattices such that each lattice in it contains at least two incomparable reducible elements. Hereafter, we will limit ourselves to dismantlable lattices only. By Theorem 2.2, it follows that the lattices of nullity up to three, containing at most \(7\) reducible elements are dismantlable, since cube (\(2^3\)) is the smallest lattice of nullity \(3\), containing \(8\) reducible elements, and which also contains the crown on \(6\) reducible elements.
Let \({\mathcal L}_r^k (n)\) denote the class of all non-isomorphic dismantlable RI-lattices on \(n\) elements such that each lattice in it contains \(r\) reducible elements and has nullity \(k\). Let \({\mathcal B}_r^k (m)\) denote the class of all non-isomorphic dismantlable maximal blocks on \(m\) elements such that each maximal block in it is an RI-lattice of nullity \(k\) and contains \(r\) reducible elements.
Theorem 4.1. [2] For \(n \geq 8\), \[\begin{aligned} |{\mathcal B}_4^3 (n)| = \left \{ \begin{array}{lll} \displaystyle\sum_{n = i+j+2,~ i>j} 4 s_i s_j & \text{if $n$ is odd}; \\ \displaystyle\sum_{n = i+j+2,~ i>j} 4 s_i s_j + s_{\frac{n-2}{2}} (2 s_{\frac{n-2}{2}}+1) & \text{if $n$ is even}, \end{array}\right. \end{aligned}\] where \(s_i = \displaystyle\sum_{k=0}^{i-3} \left\lfloor \frac{i-k-1}{2} \right\rfloor\).
The following result follows from Theorem 4.1.
Theorem 4.2. [2] For \(n \geq 8\), \(|{\mathcal L}_4^3 (n)| = \displaystyle\sum_{i=0}^{n} |{\mathcal B}_4^3 (n-i)|\).
Now in the following we prove that, there are eight non-isomorphic basic blocks containing five reducible elements and having nullity three such that at least two reducible elements are incomparable.
Proposition 4.3. If \(B\) is the basic block associated to a lattice \(L \in {\mathcal L}_5^3 (n)\) then \(B \in \{B_1, B_2, \ldots , B_8\}\) (see Figure I).
Proof. As \(B\) is the basic block associated to a lattice \(L \in {\mathcal L}_5^3 (n)\), not all \(5\) reducible elements of \(B\) are comparable. Let \(0, 1, a, b, c\) be the reducible elements of \(B\). Now at least two of them are incomparable. Without loss of generality, suppose \(a || b\). Then we have the following four cases.
1. If \(c || a\) and \(c || b\) then \(B\) contains a diamond, \(M_3 = \{0,a,b,c,1\}\) as a sublattice. Without loss of generality, suppose \(a\) is join reducible. Then there exist \(a', a'' \in Irr(B)\) such that \(a' || a''\) with \(a' \vee a'' = a\) and \(a' \wedge a'' = 0\). Consider a sublattice \(L'= M_3 \cup \{a''\}\) of \(B\). By Corollary 2.4, \(\eta(L' ]_0^a \{a'\}) = 3\), since \(\eta(M_3) = 2 = \eta(L')\). Again without loss of generality, suppose \(b\) is join reducible. Then there exist \(b', b'' \in Irr(B)\) such that \(b' || b''\) with \(b' \vee b'' = b\) and \(b' \wedge b'' = 0\). Consider a sublattice \(L''= M_3 \cup \{a'', b''\}\) of \(B\). Again by Corollary 2.4, \(\eta(L'' ]_0^a \{a'\} ]_0^b \{b'\}) = 4\), since \(\eta(L'')=\eta(M_3)\). This is not possible, since \(\eta(B)=3\).
2. Without loss of generality, suppose \(c || a\) and \(c\) is comparable to \(b\) with \(b < c\). Then \(B\) contains a pentagon, \(N_5 = \{0,a,b,c,1\}\) as a sublattice. Now we have the following three subcases.
a. Suppose \(a\) is a join reducible element only. Then there exist \(a', a'' \in Irr(B)\) such that \(a' || a''\) with \(a' \vee a'' = a\) and \(a' \wedge a'' = 0\). Consider a sublattice \(L'= N_5 \cup \{a''\}\) of \(B\). By Corollary 2.4, \(\eta(L' ]_0^a \{a'\}) = 2\), since \(\eta(N_5) = 1 = \eta(L')\).
If \(b\) and \(c\) are both join reducible elements then
by similar arguments there exist \(b',b'',c',c''\)
\(\in Irr(B)\) such that \(b'||b'', c'||c''\)
and \(\eta(L'' ]_0^a \{a'\} ]_0^b
\{b'\} ]_0^c \{c'\}) = 4\), where \(L''= L' \cup \{b'',
c''\}\) is a sublattice of \(B\). Note that \(\eta(L'')=\eta(L')\). Thus
\(B\) contains a sublattice having
nullity greater than that of \(B\).
This is not possible. Similar arguments can be applied if \(b\) and \(c\) are both meet reducible elements as
well as if \(b\) is a join reducible
element and \(c\) is a meet reducible
element. Further in both the cases, we get sublattices of \(B\) having nullity greater than that of
\(B\). Finally, if \(b\) is a meet reducible element and \(c\) is a join reducible element then we
left with only one possibility and in that case \(B\) is isomorphic to the basic block \(B_2\) (see Figure 1).
b. Suppose \(a\) is a meet reducible element only. By duality (and also by similar arguments as applied above), in this case, we find \(B\) is isomorphic to the basic block \(B_1\) (see Figure 1).
c. Suppose \(a\) ia meet reducible as well as join reducible element. Then by similar arguments as applied above, it can be shown that \(B\) contains a sublattice having nullity \(4\). So this is also not possible.
3. If \(c\) is comparable to both \(a\) and \(b\) with \(c < a\) and \(c < b\). Clearly \(a \wedge b = c\). Further, \(c\) can not be join reducible element, since otherwise \(B\) contains a sublattice having nullity greater than \(3\). Now we have the following three subcases.
a. \(a\) and \(b\) are both join reducible elements. Then \((c, a)\) and \((c, b)\) can not both be adjunct pairs in an adjunct representation of \(B\), since otherwise \(B\) contains a sublattice having nullity greater than \(3\). Therefore at the most one of \((c, a)\) and \((c, b)\) may be an adjunct pair in an adjunct representation of \(B\).
Suppose without loss of generality, \((c, a)\) is an adjunct pair in an adjunct representation of \(B\). But then there exists \(x \in Irr(B)\) such that \(x \wedge c = 0\) and \(x \vee c = b\), since \(b\) is a join reducible element. In this case \(B\) is isomorphic to the basic block \(B_4\) (see Figure 1).
If none of \((c, a)\) and \((c, b)\) is an adjunct pair in an adjunct representation of \(B\) then there exist \(x, y \in Irr(B)\) such that \(x \wedge c = 0, x \vee c = a\), \(y \wedge c = 0\) and \(y \vee c = b\), since \(a\) and \(b\) are join reducible elements. In this case \(B\) is isomorphic to the basic block \(B_8\) (see Figure 1).
b. \(a\) is join(meet) reducible and \(b\) is meet(join) reducible element then \(B\) is isomorphic to the basic block \(B_6\) (see Figure 1). c. \(a\) and \(b\) are both meet reducible elements. But this is not possible, since otherwise \(B\) contains a sublattice having nullity \(>3\).
4. If \(c\) is comparable to both \(a\) and \(b\) with \(a < c\) and \(b < c\). The proof is similar to the earlier case, and by duality, we get the basic blocks \(B_3, B_7\) and \(B_5\) up to isomorphism. ◻
For each \(i, \; 1 \leq i \leq 8\), let \({\mathbb B}_i = \{{\bf B} \in {\mathcal B}_5^3 (n) ~|~ B_i\) is the basic block associated to \({\bf B} \}\). Then \({\mathcal B}_5^3 (n) = {\mathbb B}_1 \dot\cup {\mathbb B}_2 \dot\cup \cdots \dot\cup {\mathbb B}_8\).
Proposition 5.1. For \(n \geq 9\), \(|{\mathbb B}_1| = \displaystyle\sum_{i=4}^{n-5} \left( |{\mathscr L}(i; 2, 1)| \times \displaystyle\sum_{k=0}^{n-i-5} \left\lfloor \frac{n-i-k-3}{2} \right\rfloor \right)\), where \[|{\mathscr L}(i; 2, 1)| = \left \{ \begin{array}{lll} \dfrac{m(m-1)(4m+1)}{6} & \text{if} & i = 2m + 1 ; \\[4mm] \dfrac{m(m-1) (4m-5)}{6} & \text{if} & i = 2m. \end{array} \right.\]
Proof. Let \({\bf B} \in {\mathbb B}_1\). As \(B_1\) (see Figure 1) is the basic block associated to \({\bf B} \}\), \({\bf B} \setminus \{0, 1\}\) is the disjoint union of a sublattice \(M \in {\mathscr L}_2^1 (i)\) and a subposet \(Y \in S_j\) of \({\bf B}\), where \(i \geq 4\) and \(j \geq 3\) with \(|{\bf B}| = n = i+j+2 \geq 9\). Also, observe that \({\bf B} = (\{0\} \oplus M \oplus \{1\}) ]_0^1 Y\) (or \({\bf B} = (\{0\} \oplus Y \oplus \{1\}) ]_0^1 M\)). Further, if \({\bf B'} = (\{0\} \oplus M' \oplus \{1\}) ]_0^1 Y' \in {\mathbb B}_1\) then \({\bf B} \cong {\bf B'}\) if and only if \(M \cong M'\) and \(Y \cong Y'\). Now for fixed \(i\), there are \(|{\mathscr L}(i; 2, 1)| \times |S_{n-i-2}|\) maximal blocks in \({\mathbb B}_1\) up to isomorphism. Further, \(4 \leq i = n-j-2 \leq n-5\) and there are \(\displaystyle\sum_{i=4}^{n-5} \left( |{\mathscr L}(i; 2, 1)| \times |S_{n-i-2}| \right)\) maximal blocks in \({\mathbb B}_1\) up to isomorphism. Therefore \(|{\mathbb B}_1| = \displaystyle\sum_{i=4}^{n-5} \left( |{\mathscr L}(i; 2, 1)| \times |S_{n-i-2}| \right)\). But by Remark 3.3, \(|S_j| = \displaystyle\sum_{k=0}^{j-3} \left\lfloor \frac{j-k-1}{2} \right\rfloor\). Hence the proof follows from Theorem 3.1. ◻
Corollary 5.2. For \(n \geq 9\), \(|{\mathbb B}_2| = \displaystyle\sum_{i=4}^{n-5} \left( |{\mathscr L}(i; 2, 1)| \times \displaystyle\sum_{k=0}^{n-i-5} \left\lfloor \frac{n-i-k-3}{2} \right\rfloor \right)\), where \[|{\mathscr L}(i; 2, 1)| = \left \{ \begin{array}{lll} \dfrac{m(m-1)(4m+1)}{6} & \text{if} & i = 2m + 1 ; \\[3mm] \dfrac{m(m-1) (4m-5)}{6} & \text{if} & i = 2m. \end{array} \right.\]
Proof. Clearly \(|{\mathbb B}_2| = |{\mathbb B}_1|\), since \({\bf B} \in {\mathbb B}_2\) if and only if the dual of \({\bf B}\), \({\bf B}^* \in {\mathbb B}_1\). Thus the proof follows from Proposition 5.1. ◻
For \(n \geq 6\), Thakare et al. [14] denoted the class of all non-isomorphic maximal blocks (containing \(n\) elements and having nullity two) of type \({\bf B}\), where \({\bf B} = C_{1}]^{b_{1}}_{a_{1}}C_{2}]^{b_{2}}_{a_{2}}C_{3}\) (where \(0=a_{1} < a_{2} < b_{1} = b_{2}=1\) on a maximal chain \(C_1\) and \(C_2, C_3\) are chains) by \({\cal{B}}_{1, 2}^{n}\), and obtained the following result.
Proposition 5.3. [14] For \(n \geq 6\), \(|{\cal{B}}_{1, 2}^{n}| = \displaystyle\sum_{r=1}^{\lfloor \frac{n-4}{2}\rfloor}\sum_{l=1}^{n-2r-3} (n-l-2r-2)\).
Proposition 5.4. For \(n \geq 8\), \[|{\mathbb B}_3| = \sum_{j=1}^{n-7}\sum_{i=1}^{n-j-6}\sum_{r=1}^{\lfloor \frac{n-i-j-4}{2}\rfloor}\sum_{l=1}^{n-i-j-2r-3} l(n-i-j-l-2r-2).\]
Proof. Let \({\bf B} \in {\mathbb B}_3\). Clearly \(B_3\) (see Figure 1) is the basic block associated to \({\bf B}\). As the nullity of \(B_3\) (and hence of \({\bf B}\)) is \(3\), by Corollary 2.4, \({\bf B} = C_{1}]_{0}^{c}C_2]_{a}^{c}C_3]_{b}^{1}C_4\), where \(C_1\) is a maximal chain containing \(a\) and \(c\), and \(C_2, C_3, C_4\) are chains with \(b \in C_2\). Note that \(a, b, c \in Red(B_3)\) and by Theorem 2.10, \(Red({\bf B}) = Red(B_3)\). Let \({\bf B}' = {\bf B} \cap [0, c]\) and \(C'_{1} = C_{1} \cap (c, 1]\) with \(|C'_1| = i \geq 1\) and \(|{\bf B}'| = k \geq 6\). Suppose \(|C_4| = j \geq 1\). Then \({\bf B} = ({\bf B}' \oplus C'_{1} )]_{b}^{1} C_{4}\) with \({\bf B}' \in {\cal{B}}_{1, 2}^{k}\) and \(|{\bf B}| = n = i + j + k \geq 8\). Further, if \({\bf D} = ({\bf D}' \oplus C')]_{b}^{1} C'' \in {\mathbb B}_3\), where \({\bf D}' \in {\cal{B}}_{1, 2}^{k}\) and \(C', C''\) are chains with \(|C'|=i\) and \(|C''|=j\), then \({\bf B} \cong {\bf D}\) if and only if \({\bf B'} \cong {\bf D'}\), \(C'_{1} \cong C'\) and \(C_{4} \cong C''\). By Proposition 5.3, \(|{\cal{B}}_{1, 2}^{k}| = \displaystyle\sum_{r=1}^{\lfloor \frac{k-4}{2}\rfloor}\sum_{l=1}^{k-2r-3} (k-l-2r-2)\), where \(l = |C_2|\), \(r = |C_3|\), and for fixed \(l\) and \(r\), \(k-l-2r-2\) is the number of possible positions of \(a\) in the block \({\bf B}' \in {\cal{B}}_{1, 2}^{k}\) (and hence in the block \({\bf B} \in {\mathbb B}_3\)).
Now for fixed \(i\) and \(j\), there are \(|{\cal{B}}_{1, 2}^{n-i-j}|\) maximal blocks in \({\mathbb B}_3\) up to isomorphism. Therefore for fixed \(j\), we have \(1 \leq i = n – j – k \leq n – j – 6\) and there are \(\displaystyle\sum_{i=1}^{n-j-6} |{\cal{B}}_{1, 2}^{n-i-j}|\) maximal blocks in \({\mathbb B}_3\) up to isomorphism. Further, \(1 \leq j = n – i – k \leq n – 1 – 6 = n – 7\) and there are \(\displaystyle \sum_{j=1}^{n-7} \sum_{i=1}^{n-j-6} |{\cal{B}}_{1, 2}^{n-i-j}|\) maximal blocks in \({\mathbb B}_3\) up to isomorphism.
Now \(b\) takes \(l\) number of positions in the block \({\bf B}' \in {\cal{B}}_{1,2}^{k}\) and hence in the block \({\bf B} \in {\mathbb B}_3\). Therefore there are \(\displaystyle \sum_{j=1}^{n-7} \sum_{i=1}^{n-j-6} (|{\cal{B}}_{1, 2}^{n-i-j}| \times l)\) maximal blocks in \({\mathbb B}_3\) up to isomorphism. Thus the proof follows from Proposition 5.3. ◻
Corollary 5.5. For \(n \geq 8\), \[|{\mathbb B}_4| = \sum_{j=1}^{n-7}\sum_{i=1}^{n-j-6}\sum_{r=1}^{\lfloor \frac{n-i-j-4}{2}\rfloor}\sum_{l=1}^{n-i-j-2r-3} l(n-i-j-l-2r-2).\]
Proof. Clearly \(|{\mathbb B}_4| = |{\mathbb B}_3|\), since \({\bf B} \in {\mathbb B}_4\) if and only if the dual of \({\bf B}\), \({\bf B}^* \in {\mathbb B}_3\). Thus the proof follows by Proposition 5.4. ◻
Corollary 5.6. For \(n \geq 8\), \[|{\mathbb B}_6| = \sum_{j=1}^{n-7}\sum_{i=1}^{n-j-6}\sum_{r=1}^{\lfloor \frac{n-i-j-4}{2}\rfloor}\sum_{l=1}^{n-i-j-2r-3} l(n-i-j-l-2r-2).\]
Proof. Let \({\bf B} \in {\mathbb B}_6\). Clearly \(B_6\) (see Figure 1) is the basic block associated to \({\bf B}\). As the nullity of \(B_6\) (and hence of \({\bf B}\)) is \(3\), by Corollary 2.4, \({\bf B} = C_{1}]_{c}^{1}C_2]_{b}^{1}C_3]_{0}^{a}C_4\), where \(C_1\) is a maximal chain containing \(b\) and \(c\), and \(C_2, C_3, C_4\) are chains with \(a \in C_2\). Note that \(a, b, c \in Red(B_6)\) and by Theorem 2.10, \(Red({\bf B}) = Red(B_6)\). Let \({\bf B}' = {\bf B} \cap [c, 1]\) and \(C'_{1} = C_{1} \cap [0, c)\) with \(|C'_1| = i \geq 1\) and \(|{\bf B}'| = k \geq 6\). Suppose \(|C_4| = j \geq 1\). Then \({\bf B} = (C'_{1} \oplus {\bf B}' )]_{0}^{a} C_{4}\) with \({\bf B}' \in {\cal{B}}_{1, 2}^{k}\) and \(|{\bf B}| = n = i + j + k \geq 8\).
Now by applying the similar arguments as applied in the proof of Proposition 5.4, we have \(|{\mathbb B}_6| = \displaystyle \sum_{j=1}^{n-7} \sum_{i=1}^{n-j-6} (|{\cal{B}}_{1, 2}^{n-i-j}| \times l)\). Hence the proof follows from Proposition 5.3. ◻
Corollary 5.7. For \(n \geq 8\), \[|{\mathbb B}_5| = \sum_{j=1}^{n-7}\sum_{i=1}^{n-j-6}\sum_{r=1}^{\lfloor \frac{n-i-j-4}{2}\rfloor}\sum_{l=1}^{n-i-j-2r-3} l(n-i-j-l-2r-2).\]
Proof. Clearly \(|{\mathbb B}_5| = |{\mathbb B}_6|\), since \({\bf B} \in {\mathbb B}_5\) if and only if the dual of \({\bf B}\), \({\bf B}^* \in {\mathbb B}_6\). Thus the proof follows by Corollary 5.6. ◻
Proposition 5.8. For \(n \geq 7\), \[|{\mathbb B}_{7}| = \displaystyle\sum_{l=1}^{n-7} \sum_{r=1}^{n-l-6} \sum_{q=1}^{\lfloor \frac{n-l-r-4}{2} \rfloor} \sum_{p=q+1}^{n-q-l-r-3} (p \times q) + \displaystyle\sum^{\lfloor \frac{n-6}{2}\rfloor}_{r=1}\sum_{l=r+1}^{n-r-5} \sum_{p=1}^{\lfloor \frac{n-l-r-3}{2} \rfloor} p^2 + \displaystyle\sum_{p=1}^{\lfloor \frac{n-5}{2} \rfloor} \sum_{l=1}^{\lfloor \frac{n-2p-3}{2} \rfloor} \frac{p(p+1)}{2}.\]
Proof. Let \({\bf B} \in {\mathbb B}_7\). Clearly \(B_7\) (see Figure 1) is the basic block associated to \({\bf B}\). As the nullity of \(B_7\) (and hence of \({\bf B}\)) is \(3\), by Corollary 2.4, \({\bf B} = C_{1}]_{0}^{c}C_2]_{a}^{1}C_3]_{b}^{1}C_4\), where \(C_1\) is a maximal chain containing \(a\) and \(c\), and \(C_2, C_3, C_4\) are chains with \(b \in C_2\). Note that \(a, b, c \in Red(B_7)\) and by Theorem 2.10, \(Red({\bf B}) = Red(B_7)\). Suppose \(C_1 : x_0 \prec x_1 \prec x_2 \prec \cdots \prec x_{p+t}\), \(C_2 : y_1 \prec y_2 \prec \cdots \prec y_{q}\), \(C_3 : z_1 \prec z_2 \prec \cdots \prec z_l\), and \(C_4 : w_1 \prec w_2 \prec \cdots \prec w_r\) are disjoint chains with \(x_0 = 0, x_{p+1} = c, a \in C_1 \cap [x_1, x_{p}]\) and \(x_{p+t} = 1\). Then \(p+q+l+r+t+1=n \geq 8\) with \(t \geq 2\). Note that, \(a\) has \(p\) choices and \(b\) has \(q\) choices in \(\bf B\). Further, as \(C_1\) is maximal, \(p \geq q\). Now we have the following two cases.
1. Suppose \(p > q\). Let \(S_1 = \{(p, q, l, r, t) ~|~ p \geq q + 1, t \geq 2, p, q, l, r, t \in {\mathbb N}, 1+p+q+l+r+t=n \geq 8\}\). Suppose \({\bf B}' \in {\mathbb B}_{7}\) and \((p', q', l', r', t') \in S_1\) corresponds to \(\bf B'\). Then \({\bf B} \cong {\bf B}'\) if and only if \((p, q, l, r, t) = (p', q', l', r', t')\), and \(h(a), h(b)\) are the same in both \(\bf B\) and \(\bf B'\), where \(h(a)\) is a height of \(a\).
Now for fixed \(p, q, l, r\), \(2 \leq t = n-p-q-l-r-1\), and there are \(p \times q\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Therefore for fixed \(q, l, r\), \(q+1 \leq p = n-q-l-r-t-1 \leq n-q-l-r-3\) since \(t \geq 2\), and there are \(\displaystyle\sum_{p=q+1}^{n-q-l-r-3} (p \times q)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Again for fixed \(l, r\), \(1 \leq q = n-p-l-r-t-1 \leq n-(q+1)-l-r-3\) since \(p \geq q + 1\) and \(t \geq 2\). That is, \(1 \leq q \leq \lfloor \frac{n-l-r-4}{2} \rfloor\). Therefore for fixed \(l, r\), there are \(\displaystyle\sum_{q=1}^{\lfloor \frac{n-l-r-4}{2} \rfloor} \left( \sum_{p=q+1}^{n-q-l-r-3} (p \times q) \right)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Further, for fixed \(l\), \(1 \leq r = n-p-q-l-t-1 \leq n-(q+1)-q-l-3 = n-2q-l-4 \leq n-l-6\) since \(p \geq q + 1\), \(t \geq 2\) and \(q \geq 1\). Therefore for fixed \(l\), there are \(\displaystyle\sum_{r=1}^{n-l-6} \left( \sum_{q=1}^{\lfloor \frac{n-l-r-4}{2} \rfloor} \sum_{p=q+1}^{n-q-l-r-3} (p \times q) \right)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Also \(1 \leq l = n-p-q-r-t-1 \leq n-7\) since \(p \geq q + 1\), \(t \geq 2\), \(q \geq 1\) and \(r \geq 1\). Thus in this case, there are \(\displaystyle\sum_{l=1}^{n-7} \left( \sum_{r=1}^{n-l-6} \sum_{q=1}^{\lfloor \frac{n-l-r-4}{2} \rfloor} \sum_{p=q+1}^{n-q-l-r-3} (p \times q) \right)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism.
2. Suppose \(p = q\). In this case, without loss, suppose \(l \geq r\). But then again we have to consider the following two subcases.
a. Suppose \(l > r\). Let \(S_2 = \{(p, l, r, t) ~|~ l \geq r + 1, t \geq 2, p, l, r, t \in {\mathbb N}, 1+2p+l+r+t=n \geq 8\}\). Suppose \({\bf B}' \in {\mathbb B}_{7}\) and \((p', l', r', t') \in S_2\) corresponds to \(\bf B'\). Then \({\bf B} \cong {\bf B}'\) if and only if \((p, l, r, t) = (p', l', r', t')\), and \(h(a), h(b)\) are the same in both \(\bf B\) and \(\bf B'\).
Now for fixed \(p, l, r\), \(2 \leq t = n-2p-l-r-1\), and there are \(p \times p = p^2\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Again for fixed \(l, r\), \(1 \leq p = \frac{n-l-r-t-1}{2} \leq \frac{n-l-r-3}{2}\) since \(t \geq 2\). That is, \(1 \leq p \leq \lfloor \frac{n-l-r-3}{2} \rfloor\). Therefore for fixed \(l, r\), there are \(\displaystyle\sum_{p=1}^{\lfloor \frac{n-l-r-3}{2} \rfloor} p^2\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Further, for fixed \(r\), \(r+1 \leq l = n-2p-r-t-1 \leq n-r-5\) since \(t \geq 2, p \geq 1\), and there are \(\displaystyle\sum_{l=r+1}^{n-r-5} \left( \sum_{p=1}^{\lfloor \frac{n-l-r-3}{2} \rfloor} p^2 \right)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Also \(1 \leq r = n-2p-l-t-1 \leq n-(r+1)-5\) since \(t \geq 2, p \geq 1\). That is, \(1 \leq r \leq \frac{n-6}{2}\). Thus in this subcase, \(1 \leq r \leq \lfloor \frac{n-6}{2} \rfloor\), and there are \(\displaystyle\sum^{\lfloor \frac{n-6}{2}\rfloor}_{r=1} \left( \sum_{l=r+1}^{n-r-5} \sum_{p=1}^{\lfloor \frac{n-l-r-3}{2} \rfloor} p^2 \right)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism.
b. Suppose \(l = r\). Let \(S_3 = \{(p, l, t) ~|~ t \geq 2, p, l, r, t \in {\mathbb N}, 1+2p+2l+t=n \geq 7\}\). Suppose \({\bf B}' \in {\mathbb B}_{7}\) and \((p', l', t') \in S_3\) corresponds to \(\bf B'\). Then \({\bf B} \cong {\bf B}'\) if and only if \((p, l, t) = (p', l', t')\), and \(h(a), h(b)\) are the same in both \(\bf B\) and \(\bf B'\) alongwith \(h(a) \leq h(b)\).
Now for fixed \(p, l\), \(2 \leq t = n-2p-2l-1\), and there are \(p + (p-1) + \cdots + 3 + 2 + 1 = \frac{p(p+1)}{2}\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Note that, if \(h(a) = i ~(1 \leq i \leq p)\) then there are \(p-i+1\) choices for \(b\) in a maximal block \(\bf B \in {\mathbb B}_{7}\). Again for fixed \(p\), \(1 \leq l = \frac{n-2p-t-1}{2} \leq \frac{n-2p-3}{2}\) since \(t \geq 2\). That is, \(1 \leq l \leq \lfloor \frac{n-2p-3}{2} \rfloor\). Therefore for fixed \(p\), there are \(\displaystyle\sum_{l=1}^{\lfloor \frac{n-2p-3}{2} \rfloor} \frac{p(p+1)}{2}\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. Also \(1 \leq p = \frac{n-2l-t-1}{2} \leq \frac{n-5}{2}\) since \(t \geq 2\) and \(l \geq 1\). That is, \(1 \leq p \leq \lfloor \frac{n-5}{2} \rfloor\). Thus in this subcase, there are \(\displaystyle\sum_{p=1}^{\lfloor \frac{n-5}{2} \rfloor} \left( \sum_{l=1}^{\lfloor \frac{n-2p-3}{2} \rfloor} \frac{p(p+1)}{2} \right)\) maximal blocks in \({\mathbb B}_{7}\) up to isomorphism. ◻
Corollary 5.9. For \(n \geq 7\), \[|{\mathbb B}_{8}| = \displaystyle\sum_{l=1}^{n-7} \sum_{r=1}^{n-l-6} \sum_{q=1}^{\lfloor \frac{n-l-r-4}{2} \rfloor} \sum_{p=q+1}^{n-q-l-r-3} (p \times q) + \displaystyle\sum^{\lfloor \frac{n-6}{2}\rfloor}_{r=1}\sum_{l=r+1}^{n-r-5} \sum_{p=1}^{\lfloor \frac{n-l-r-3}{2} \rfloor} p^2 + \displaystyle\sum_{p=1}^{\lfloor \frac{n-5}{2} \rfloor} \sum_{l=1}^{\lfloor \frac{n-2p-3}{2} \rfloor} \frac{p(p+1)}{2}.\]
Proof. Clearly \(|{\mathbb B}_{8}| = |{\mathbb B}_{7}|\), since \(\bf B \in {\mathbb B}_{8}\) if and only if the dual of \(\bf B\), \(\bf B^* \in {\mathbb B}_{7}\). Thus the proof follows from Proposition 5.8. ◻
Using Proposition 5.1, Corollary 5.2, Proposition 5.4, Corollary 5.5, Corollary 5.6, Corollary 5.7, Proposition 5.8 and Corollary 5.9, we obtain the following result.
Theorem 5.10. For \(n \geq 7\), \(|{\mathcal B}_5^3 (n)| = \displaystyle\sum_{i=1}^{8} |{\mathbb B} _i|\).
Proof. The proof follows from the fact that \(\{{\mathbb B}_i : 1 \leq i \leq 8\}\) forms a partition of the class \({\mathcal B}_5^3 (n)\). ◻
The following result follows from Theorem 5.10.
Theorem 5.11. For \(n \geq 7\), \(|{\mathcal L}_5^3 (n)| = \displaystyle\sum_{i=0}^{n} |{\mathcal B}_5^3 (n-i)|\).
Aware and Bhavale [1] counted all non-isomorphic lattices containing up to five comparable reducible elements, and having nullity up to three. Bhavale [2] obtained the number of all non-isomorphic lattices on \(n\) elements, having nullity three, and containing four reducible elements such that at least two of them are incomparable (see Theorem 4.2). In Theorem 5.11 we obtain the number of all non-isomorphic lattices on \(n\) elements, having nullity three, and containing five reducible elements such that at least two of them are incomparable. Thus, this counting achieve the counting of all non-isomorphic lattices on \(n\) elements, containing up to five reducible elements, and having nullity up to three.
We now raise the following three problems. Find up to isomorphism all RC-lattices containing \(r \geq 6\) reducible elements. Find up to isomorphism all dismantlable lattices containing \(r \geq 6\) reducible elements. Find up to isomorphism all lattices containing \(r \geq 4\) reducible elements.