Recognition and Enumeration of the Quasi-Full Rooted Trees

Salah Uddin Mohammad, Md. Shah Noor, and Md. Rashed Talukder

Department of Mathematics Shahjalal University of Science and Technology Sylhet-3114 Bangladesh

                salahuddin-mat@sust.edu
                  msnoor-mat@sust.edu
                r.talukder-mat@sust.edu

Abstract

We introduce the notion of quasi-full rooted trees. We provide a poset matrix based approach for the recognition of quasi-full rooted trees. We obtain an exact enumeration of the unlabeled quasi-full t-ary rooted trees with n elements (nodes), where 2 ≤ t < n. Here, we give the enumeration of the unlabeled quasi-full rooted trees according to the arity and the number of elements of the trees. This method induces a polynomial-time algorithm that determines the values of the parameters involved in the enumeration formula. We also computationally implement the enumeration algorithm and include the number of n-element unlabeled quasi-full t-ary rooted trees for all 2 ≤ t < n ≤ 31.

1 Introduction

We introduce a new class of rooted trees, which we call the quasi-full rooted trees. A rooted tree with arity t is called quasi-full if the root of every subtree with r elements (nodes or vertices) has exactly min(r − 1, t) children. The class of quasi-full rooted trees contains the class of full rooted trees as a subclass. Similar to full rooted trees, there are balanced quasifull rooted trees. We call these quasi-complete. There are also quasi-full rooted trees with all of their leaves at the same level, which we call quasi-perfect. Rooted trees, as a special type of graph (more specifically, Hasse diagrams of posets), have significant importance. Various combinatorial properties of these mathematical structures have shown their relevance in structural analysis, enabling the understanding of patterns, relationships, and connectivity in many scenarios, ranging from gene models in molecular biology to data mining in computer science. Therefore, numerous authors have focused on the recognition and enumeration of several types of rooted trees and forests; see [1, 4, 5, 6, 7, 17, 20]. Also, there are a number of integer sequences in the On-Line Encyclopedia of Integer Sequences (OEIS) [19] that provide some existing results on the exact enumerations of several types of labeled and unlabeled rooted trees. These include full rooted trees (\underline{A319541}), balanced rooted trees (\underline{A306201}, \underline{A320160}, \underline{A320270}), complete rooted trees (\underline{A287211}), and rooted trees with all leaves at the same level (\underline{A238372}, \underline{A048816}). For the enumerations of labeled and unlabeled rooted trees in general, see also the sequences \underline{A000169}, \underline{A000081}, and \underline{A299038} in the OEIS [19].

Interestingly, a rooted tree (as a Hasse diagram of a poset) can be generated from a single element (the singleton poset) by taking the direct sum (disjoint sum or parallel composition) and ordinal sum (linear sum or series composition) only. Therefore, the aforementioned classes of rooted trees can be considered as nice subclasses of the frequently studied decomposable posets, more specifically, connected series-parallel posets; see [8]. Analogously, a rooted forest (a collection of rooted trees) can be considered as the direct sum of two or more rooted trees or seeds. Then, similar to series-parallel posets, an arbitrary rooted tree can be constructed by taking the ordinal sum of a single element (which becomes the root of the tree) and a rooted forest. Thus, for every 2 ≤ t < n, an n-element quasi-full t-ary rooted tree can be constructed by taking the ordinal sum of a single node (a seed) and an (n − 1)- element quasi-full rooted forest consisting of exactly t trees (quasi-full t-ary rooted trees) or seeds. This construction of rooted trees suggests a matrix recognition and, consequently, an exact enumeration of the unlabeled quasi-full rooted trees.

In this paper, we first give a matrix recognition of quasi-full rooted trees using the poset matrix, an incidence matrix used to represent posets. The notions of many incidence matrices were frequently introduced and applied to certain computational aspects of the concerned mathematical structures; see [2, 12, 18]. Particularly, matrix-based approaches for recognizing some mathematical objects are preferable because they induce a more efficient computational implementation of the methods. Mohammad and Talukder [8] coined the term poset matrix. Recently, the poset matrix has gained much attention in the recognition and classification of various classes of posets and graphs; see [2, 9, 11, 12, 16]. Secondly, we give an exact enumeration of the unlabeled quasi-full rooted trees that depends mainly on the nonisomorphic direct sum criterion of poset matrices obtained by Mohammad et al. [13, 14]. We find that the number of n-element unlabeled quasi-full t-ary rooted trees increases exponentially as the values of n and t increase. We give an algorithm to determine the values of some parameters involved in the enumeration formula. We prove that the enumeration algorithm runs in polynomial time with complexity O(n^{4}). Also, we computationally implement the enumeration algorithm and obtain the numerical result for the number of unlabeled quasi-full rooted trees according to their arity and the number of elements. These data yield a new integer sequence \underline{A352460} contributed to the OEIS [19].

In Section 2, we introduce the quasi-full rooted trees and quasi-full rooted forests as posets with constructive examples. In Section 3, we give the matrix recognitions of the quasi-full rooted trees and quasi-full rooted forests by using the poset matrix. In Section 4, we obtain an exact enumeration of the unlabeled quasi-full t-ary rooted trees with n elements, where 2 ≤ t < n. In Section 5, we give the enumeration algorithm and prove its time complexity. Moreover, in Section 6, we include the data (Table 3 and Table 4) regarding the number of n-element unlabeled quasi-full t-ary rooted trees for all 2 ≤ t < n ≤ 31.

2 Quasi-full rooted trees and forests as posets

A poset (partially ordered set) is a structure A = ⟨A, ⩽⟩ consisting of the nonempty set A with the order relation ⩽ on A, that is, the relation ⩽ is reflexive, antisymmetric, and transitive on A. Note that the results in this article are applicable to finite posets only. We use the notation 1 for the singleton poset, C_{n≥1} for the n-element chain poset, I_{n≥1} for the n-element antichain poset, and B_{m≥1,n≥1} for the complete bipartite poset with m minimal elements and n maximal elements. We write A ≅ B if A and B are order isomorphic. In particular, we have C_{1} ≅ I_{1} ≅ 1 and B_{1,1} ≅ C_{2}. We also use the notation A + B and A ⊕ B to denote, respectively, the direct sum and ordinal sum of the posets A and B. Here, the posets A and B are called the direct terms of A + B and the ordinal terms of A ⊕ B. For every m ≥ 1 and n ≥ 1, we have B_{m,n} ≅ I_{m} ⊕ I_{n}. Here, I_{m} and I_{n} are the ordinal terms of the poset B_{m,n}. Also, for every n ≥ 2, we have I_{n} ≅ \underbrace{1 + 1 + ⋯ + 1}_{n terms}

and C_{n} ≅ \underbrace{1 ⊕ 1 ⊕ ⋯ ⊕ 1}_{n terms}. A poset having two or more direct terms is called disconnected;

otherwise, it is called connected. A poset is called series-parallel if it can be generated from the singleton poset by taking the direct sum and ordinal sum only. For further details on posets, we refer readers to the classical book by Davey and Priestley [3].

A rooted tree is an acyclic graph with a fixed element (node or vertex) called the root of the tree. The immediate successors of an element in a rooted tree are called children of that element. An element except the root in a tree having no children is called a leaf, and an element having at least one child is called an internal element. In a rooted tree, the root is supposed to be at level 0, and the children of an internal element go to the immediate upper level. By a subtree of a rooted tree, we mean either the whole tree itself or a tree consisting of a child (which becomes the root of the subtree) and all of its successors of an internal element of the tree. A tree with a single element, the singleton poset 1, is called the nullary tree or seed. We can consider the tree 1 (the singleton poset) just as a seed. A rooted tree is said to have arity t, where t ≥ 1, if every internal element of the tree has at most t children. A t-ary rooted tree is called full if every internal element has exactly t children. A full rooted tree having all its leaves at the same level is called perfect. A t-ary rooted tree is called balanced if all its leaves are at the highest two levels. A t-ary balanced rooted tree is called complete if every internal element has exactly t children. Thus, every perfect rooted tree is complete, and every complete rooted tree is full. Note that there are full rooted trees that are not balanced, and there are balanced rooted trees that are not full. Note also that if a rooted tree is not balanced, then it is neither perfect nor even complete. In the following, we define and explain the term quasi-full rooted tree.

Definition 1. A t-ary rooted tree is called quasi-full if the root of every subtree with r elements has exactly min(r − 1, t) children.

For example, the rooted trees C_{2}, B_{1,2} ≅ 1 ⊕ I_{2}, 1 ⊕ (1 + C_{2}), B_{1,3} ≅ 1 ⊕ I_{3}, and 1 ⊕ (C_{2} + C_{2}), as shown in Figure 1 by their Hasse diagrams, are all quasi-full rooted trees. Let T_{n,t}, where n ≥ 1 and t ≥ 1, be the collections of quasi-full t-ary rooted trees with n elements. In particular, we have the following.

1. T_{1,1} = T_{1,2} = ⋯ = {1}, T_{2,1} = T_{2,2} = ⋯ = {C_{2}}, T_{3,1} = {C_{3}}, T_{4,1} = {C_{4}}, T_{5,1} = {C_{5}}, and so on.

2. T_{3,t≥2} = {1 ⊕ I_{2}} = {B_{1,2}}, T_{4,t≥3} = {1 ⊕ I_{3}} = {B_{1,3}}, and so on.

Also, we have T_{4,2} = {1 ⊕ (1 + C_{2})}, T_{5,2} = {1 ⊕ (C_{2} + C_{2}), 1 ⊕ (1 + B_{1,2})}, and T_{5,3} = {1 ⊕ (I_{2} + C_{2})}. In general, we have T_{n=1,t≥1} = {1}, T_{n=2,t≥1} = {C_{2}}, T_{n≥1,t=1} = {C_{n}}, T_{n≥2,t≥n−1} = {1 ⊕ I_{n−1}} = {B_{1,n−1}}, and T_{n≥4,t=n−2} = {1 ⊕ (I_{n−3} + C_{2})}.

C_{2}  B_{1,2}  1 ⊕ (1 + C_{2})  B_{1,3}  1 ⊕ (C_{2} + C_{2})

Figure 1: Some quasi-full rooted trees (Hasse diagrams of posets) up to 5 elements.

We see that every proper subtree of an n-element quasi-full t-ary rooted tree is also a quasi-full rooted tree with maximum n − t elements. We also see that a quasi-full rooted tree has the intention of fulfilling its arity in an internal element before it produces a new child in a leaf of that element. This structure of quasi-full rooted trees shows that every full rooted tree is quasi-full. On the other hand, we see that the binary rooted trees 1 ⊕ (1 + C_{2}) and 1 ⊕ (C_{2} + C_{2}), as given in Figure 1, are quasi-full but not full trees. Therefore, the class of full rooted trees is contained in the class of quasi-full rooted trees properly. Also, we see that the balanced rooted tree 1 ⊕ (1 + C_{2}) is not complete. Since 1 ⊕ (1 + C_{2}) is quasi-full, we call it quasi-complete. Similarly, we see that the quasi-full rooted tree 1 ⊕ (C_{2} + C_{2}) has all its leaves at the same level. Since 1 ⊕ (C_{2} + C_{2}) is not full, it is not perfect, and we call it quasi-perfect. Moreover, similar to full rooted trees, there are quasi-full rooted trees that are not balanced, and there are balanced rooted trees that are not quasi-full. However, all the quasi-full rooted trees up to 5 elements are balanced.

Note that the root of a tree (see Figure 1) is put at the bottom of the tree, and the children and leaves of the tree are drawn above the root in the upward direction. In general, we assume that in an internal element of a rooted tree, a subtree with a greater number of elements is positioned to the right (equivalently, left) of a subtree with a lesser number of elements. Also, throughout this paper, we consider only unlabeled rooted trees.

A forest is a collection of two or more trees or seeds. A rooted forest consists of two or more rooted trees or seeds. The number of elements of a forest equals the sum of the number of elements of the trees and the number of seeds in the forest. We now define the term quasi-full rooted forest.

Definition 2. A rooted forest consisting of exactly t quasi-full t-ary rooted trees or seeds is called a quasi-full t-ary rooted forest.

Let F_{n,t}, where 1 ≤ t ≤ n, be the collections of quasi-full t-ary rooted forests with n elements. In particular, we have the following.

1. F_{1,1} = {C_{1}}, F_{2,1} = {C_{2}}, F_{3,1} = {C_{3}}, and so on. Thus F_{n≥1,t=1} = {C_{n}}.

2. F_{2,2} = {I_{2}}, F_{3,3} = {I_{3}}, F_{4,4} = {I_{4}}, and so on. Thus F_{n≥1,t=n} = {I_{n}}.

3. F_{3,2} = {I_{1} + C_{2}}, F_{4,3} = {I_{2} + C_{2}}, and so on. Thus F_{n≥3,t=n−1} = {I_{n−2} + C_{2}}.

4. F_{4,2} = {C_{2} + C_{2}, 1 + B_{1,2}}, F_{5,2} = {C_{2} + B_{1,2}}, and F_{5,3} = {1 + C_{2} + C_{2}, I_{2} + B_{1,2}}.

Throughout the rest of the paper, by the term quasi-full tree (analogously, quasi-full forest), we will mean a t-ary quasi-full rooted tree (quasi-full rooted forest) with n elements.

3 Recognitions of the quasi-full trees and forests

Throughout this paper, we use the notation M_{m,n} for an m-by-n matrix and M_{n} for a square matrix of order n. In particular, we use the notation I_{n}, O_{n}, and Z_{n}, respectively, for the n-th order identity matrix, the matrix with all entries 1s, and the matrix with all entries 0s. We also use the notation C_{n} for the matrix [c_{ij}], 1 ≤ i, j ≤ n, defined as c_{ij} = 1 for all i ≤ j and c_{ij} = 0 otherwise. Note that here I_{1} = C_{1} = 1. An upper triangular (0, 1)-matrix M_{n} = [a_{ij}], 1 ≤ i, j ≤ n, with entries 1s in the main diagonal is called a poset matrix if and only if M_{n} is transitive, that is, a_{ij} = 1 and a_{jk} = 1 imply a_{ik} = 1 for all 1 ≤ i, j, k ≤ n. For example, for every n ≥ 1, the matrices I_{n} and C_{n} are all poset matrices, because these are upper triangular and clearly transitive. Also, the following matrices B_{3} and B_{3}^{t} are nontrivial poset matrices. For further details on the poset matrix and interpretations of several operations with poset matrices, see the results obtained by Mohammad et al. [8, 9, 11, 12].

B_{3} = [ \begin{matrix}1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ] B_{3}^{t} = [ \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ]

Let M_{n} = [a_{ij}], 1 ≤ i, j ≤ n, be a poset matrix. We associate a poset A = ⟨A, ⩽⟩ with the matrix M_{n}, where the underlying set A = {x_{1}, x_{2}, …, x_{n}} and x_{i} corresponds to the i-th row (or column) of M_{n}, by defining the order relation ⩽ on A such that for all 1 ≤ i, j ≤ n, we have x_{i} ⩽ x_{j} if and only if a_{ij} = 1. Then we say that the poset matrix M_{n} represents the poset A and vice versa. Clearly, for every n ≥ 1, the poset matrices I_{n} and C_{n} represent the posets I_{n} and C_{n}, respectively. Also, the poset matrices B_{3} and B_{3}^{t}, as given above, represent the complete bipartite posets B_{1,2} (as shown in Figure 1) and B_{2,1} (dual of B_{1,2}), respectively. Let M_{n} be a poset matrix. For some 1 ≤ i, j ≤ n, the interchange of the i-th and j-th rows along with the interchange of the i-th and j-th columns in M_{n} is called (i,j)-relabeling of M_{n}. For example, a relabeling of the poset matrix B_{3}^{t} is shown in the following.

B_{3}^{t} = [ \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} ] ⟶^{(1,3)-relabeling}  [ \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix} ] = B_{3}^{∂}

Mohammad and Talukder [8] gave the interpretations of relabeling in a poset matrix. They showed that every matrix obtained by a relabeling of a poset matrix is a poset matrix, and it represents the same poset up to isomorphism. They also showed that every poset matrix can be relabeled to an upper (equivalently, lower) triangular matrix with 1s in the main diagonal by a finite number of relabelings. Any two poset matrices M_{n} and M′_{n} are called relabeling equivalent, or briefly equivalent, if the matrix M′_{n} can be obtained by some relabeling of the matrix M_{n} and vice versa. We write M_{n} ∼ M′_{n} if M_{n} and M′_{n} are relabeling equivalent. Also, by a collection of equivalent (analogously, nonequivalent) poset matrices, we mean that the matrices are pairwise equivalent (nonequivalent). Obviously, if M_{n} ∼ M′_{n} (analogously, M_{n} ≁ M′_{n}), then the posets represented by M_{n} and M′_{n} are isomorphic (nonisomorphic). Note that throughout this paper, by a poset matrix we mean a poset matrix in upper triangular form.

Let M_{m} and N_{n} be any poset matrices. We write M_{m} ⊕ N_{n} and M_{m} ⊞ N_{n}, respectively, for the direct sum and ordinal sum of the matrices M_{m} and N_{n}. Note here that the matrices M_{m} and N_{n} are called the direct terms of M_{m} ⊕ N_{n} and the ordinal terms of M_{m} ⊞ N_{n}. Mohammad and Talukder [8] defined the block of 0s property and the block of 1s property in a poset matrix. A poset matrix M_{n} = [a_{ij}], 1 ≤ i, j ≤ n, satisfies the block of 0s property (analogously, block of 1s property) of length r, where 1 ≤ r < n, if and only if a_{ij} = 0 (analogously, a_{ij} = 1) for all 1 ≤ i ≤ r and r + 1 ≤ j ≤ n. For example, for every n ≥ 2, the poset matrix I_{n} satisfies the block of 0s property of lengths 1, 2, …, n − 1, and the poset matrix C_{n} satisfies the block of 1s property of lengths 1, 2, …, n − 1. Also, the following poset matrix B_{4} satisfies the block of 1s property of length 1, and the poset matrix F_{4} satisfies the block of 0s property of length 2.

B_{4} = [ \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] F_{4} = [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} ]

Note that for any relabeling, a poset matrix M_{n} can satisfy one of the two mentioned properties at a time, but not both properties together. In the case of the poset matrices B_{4} and F_{4} given above, we have B_{4} = 1⊞I_{3} and F_{4} = C_{2}⊕C_{2}. Also, we have I_{n} = \underbrace{1 ⊕ 1 ⊕ ⋯ ⊕ 1}_{n terms}

and C_{n} = \underbrace{1 ⊞ 1 ⊞ ⋯ ⊞ 1}_{n terms}. Mohammad and Talukder [8] obtained the following results

regarding the direct sum and ordinal sum of poset matrices.

Theorem 3. [8] For n ≥ 2, a poset matrix M_{n} satisfies the block of 0s property (analogously, block of 1s property) of lengths n_{1}, n_{2}, …, n_{m} if and only if M_{n} = M_{n_{1}}⊕M_{n_{2}−n_{1}}⊕⋯⊕M_{n−n_{m}} (analogously, M_{n} = M_{n_{1}} ⊞ M_{n_{2}−n_{1}} ⊞ ⋯ ⊞ M_{n−n_{m}}) for some poset matrices M_{n_{1}}, M_{n_{2}−n_{1}}, …, M_{n−n_{m}}.

Theorem 4. [8] For n ≥ 2, let M_{n_{i}} represent the poset P_{i} for every 1 ≤ i ≤ r. Then the matrix M_{n_{1}} ⊕ M_{n_{2}} ⊕ ⋯ ⊕ M_{n_{r}} (analogously, M_{n_{1}} ⊞ M_{n_{2}} ⊞ ⋯ ⊞ M_{n_{r}}) is a poset matrix and it represents the poset P_{1} + P_{1} + ⋯ + P_{r} (analogously, P_{1} ⊕ P_{1} ⊕ ⋯ ⊕ P_{r}).

We observe that the poset matrix B_{4} (as given above) that satisfies the block of 1s property of length 1 represents the connected poset B_{1,3}, and the poset matrix F_{4} that satisfies the block of 0s property of length 2 represents the disconnected poset C_{2} + C_{2}. Mohammad et al. [14] established the above observations in general and obtained the following results regarding the matrix recognitions of the connected posets and disconnected posets.

Theorem 5. [14] Let M represent the poset P ≇ 1. Then P is connected (analogously, disconnected) if M can be relabeled in such a form that it satisfies the block of 1s property (analogously, block of 0s property).

In general, the converse of the result obtained for connected posets in Theorem 5 is not true, because every nontrivial prime poset (particularly, the 4-element N-shaped or zigzag poset) is connected, where the poset matrix that represents a prime poset does not satisfy the block of 1s property for any labeling. However, the following result (Theorem 6) regarding the recognition of quasi-full rooted trees shows that the converse of the result obtained in Theorem 5 holds in the case of quasi-full rooted trees. We observe that the following matrix B_{4} satisfies the block of 1s property of length 1; and the successive nonunit ordinal term satisfies the block of 0s property of lengths 1, 2, where all the successive direct terms equal 1. We see that the poset matrix B_{4} represents the quasi-full rooted tree B_{1,3} (see Figure 1). On the other hand, we observe that the following matrix F_{4} satisfies the block of 0s property of length 2; and both the successive direct terms satisfy the block of 1s property of length 1, where all the successive ordinal terms equal 1. We see that the poset matrix F_{4} represents the quasi-full rooted forest C_{2} + C_{2}.

B_{4} = [ \begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] F_{4} = [ \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} ]

We now establish the above observations in general. We give the matrix recognition of the quasi-full rooted trees T ∈ T_{n≥3,t≥2} and the matrix recognition of the quasi-full rooted forest F ∈ F_{n≥2,t≥2}, respectively. Recall that T_{n≥1,t=1} = F_{n≥1,t=1} = {C_{n}} and T_{n=2,t≥1} = {C_{2}}. Note that none of the poset matrices C_{n}, n ≥ 1, satisfy the block of 0s property.

Theorem 6. For n ≥ 3 and t ≥ 2, let M_{n} represent the poset T. Then T is a quasi-full t-ary rooted tree if and only if M_{n} can be relabeled in such a form that it satisfies the block of 1s property of length 1; and every successive nonunit ordinal term M_{r} satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{h−1} for some l_{1} < l_{2} < ⋯ < l_{h−1}, where h = min(r, t), and every successive nonunit direct term satisfies the block of 1s property of length 1.

Proof. Let T be a quasi-full t-ary rooted tree with n elements, where 2 ≤ t < n, and M_{n} represent T. Then T can be considered as a connected series-parallel poset with a single minimal element known as the root of the tree T. Then by Theorem 5, there exists a poset P such that T ≅ 1 ⊕ P. Then P is a quasi-full t-ary rooted forest consisting of h − 1 subtrees of T, where h = min(n − 1, t). Thus there exist the quasi-full t-ary rooted trees (possibly, seeds) T_{1}, T_{2}, …, T_{h−1} such that P ≅ T_{1} + T_{2} + ⋯ + T_{h−1}. Let the poset matrices M_{r_{1}}, M_{r_{2}}, …, M_{r_{h−1}} represent the trees T_{1}, T_{2}, …, T_{h−1}, respectively. Then by Theorem 3 and Theorem 4, the poset matrix M_{r_{1}} ⊕M_{r_{2}} ⊕⋯⊕M_{r_{h−1}} represents the forest P ≅ T_{1} + T_{2} + ⋯ + T_{h−1}. This implies that 1 ⊞ (M_{r_{1}} ⊕ M_{r_{2}} ⊕ ⋯ ⊕ M_{r_{h−1}}) represents the tree 1⊕(T_{1}+T_{2}+⋯+T_{h−1}) ≅ 1⊕P ≅ T. This shows that M_{n} ∼ 1⊞(M_{r_{1}} ⊕M_{r_{2}} ⊕⋯⊕M_{r_{h−1}}). For every 1 ≤ i ≤ h − 1, if |T_{i}| = 1, that is, T_{i} ≅ 1, then we have M_{r_{i}} = 1; or if |T_{i}| = 2, then by definition, we have T_{i} ≅ C_{2}, and then M_{r_{i}} = C_{2}. Otherwise, for |T_{i}| ≥ 3, we must have T_{i_{j}} and M_{r_{i_{j}}}, 1 ≤ j ≤ h_{i} − 1, such that T_{i} ≅ 1 ⊕ (T_{i_{1}} + T_{i_{2}} + ⋯ + T_{i_{h_{i}−1}}) and M_{r_{i}} ∼ 1 ⊞ (M_{r_{i_{1}}} ⊕ M_{r_{i_{2}}} ⊕ ⋯ ⊕ M_{r_{i_{h_{i}−1}}}). Since every subtree of a quasi-full rooted tree is quasi-full, continuing the above process, we show that every successive nonunit ordinal term M_{r_{i}} satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{h−1} for some l_{1} < l_{2} < ⋯ < l_{h−1}, where h = min(r_{i}, t), and every successive nonunit direct term satisfies the block of 1s property of length 1. Thus, the matrix M_{n} can be relabeled in such a form that it follows the conditions in the hypothesis.

Conversely, suppose we can relabel M_{n} in such a form that it satisfies the conditions in the hypothesis. Then M_{n} satisfies the block of 1s property of length 1. Thus there exists a poset matrix Q_{n−1} such that M_{n} = 1 ⊞ Q_{n−1}. Since the ordinal term Q_{n−1} is nonunit, it must satisfy the block of 0s property of lengths l_{1}, l_{2}, …, l_{k−1} for some l_{1} < l_{2} < ⋯ < l_{k−1}. Assign r_{i} = l_{i} − l_{i−1}, 1 ≤ i ≤ k, where we assume l_{0} = 0 and l_{k} = n − 1. Then by Theorem 3, there exist Q_{r_{i}}, 1 ≤ i ≤ k, such that Q_{n−1} = Q_{r_{1}} ⊕ Q_{r_{2}} ⊕ ⋯ ⊕ Q_{r_{k}}. This gives M_{n} = 1 ⊞ (Q_{r_{1}} ⊕ Q_{r_{2}} ⊕ ⋯ ⊕ Q_{r_{k}}). If r_{i} ≤ 2 for every 1 ≤ i ≤ k, then by Theorem 4, Q_{r_{i}} ∼ C_{r_{i}} implies that M_{n} represents the poset 1 ⊕ (C_{r_{1}} + C_{r_{2}} + ⋯ + C_{r_{k}}) that is a quasifull rooted tree. If r_{i} ≥ 3 for some 1 ≤ i ≤ k, then there exist Q_{r_{i_{j}}}, 1 ≤ j ≤ k_{i}, such that Q_{r_{i}} = 1⊞(Q_{r_{i_{1}}} ⊕Q_{r_{i_{2}}} ⊕⋯⊕Q_{r_{i_{k_{i}}}}). Continuing the above process, we can show that r_{i_{j}} ≤ 2 for every 1 ≤ i ≤ k_{i} at some step i such that Q_{r_{i}} represents the poset 1⊕(C_{r_{i_{1}}} +C_{r_{i_{2}}} +⋯+C_{r_{k_{i}}}). Therefore, M_{n} = 1 ⊞ (Q_{r_{1}} ⊕ Q_{r_{2}} ⊕ ⋯ ⊕ Q_{r_{k}}) represents a quasi-full rooted tree.

Theorem 7. For n ≥ 2 and t ≥ 2, let M_{n} represent the poset F. Then F is a quasifull t-ary rooted forest if and only if M_{n} can be relabeled in such a form that it satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{t−1} for some l_{1} < l_{2} < ⋯ < l_{t−1}; and every successive nonunit direct term satisfies the block of 1s property of length 1, and every successive nonunit ordinal term M_{r} satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{h−1} for some l_{1} < l_{2} < ⋯ < l_{h−1}, where h = min(r, t).

Proof. Let F be a quasi-full t-ary rooted tree with n elements, where 2 ≤ t ≤ n, and M_{n} represent F. Then there exist the quasi-full t-ary rooted trees (possibly, seeds) T_{1}, T_{2}, …, T_{t} such that F ≅ T_{1} +T_{2} +⋯+T_{t}. Let the poset matrices M_{r_{1}}, M_{r_{2}}, …, M_{r_{t}} represent the trees T_{1}, T_{2}, …, T_{t}, respectively. Then by Theorem 3 and Theorem 4, M_{r_{1}} ⊕M_{r_{2}} ⊕⋯⊕M_{r_{t}} represents the forest F ≅ T_{1} + T_{2} + ⋯ + T_{t}. This shows that M_{n} ∼ M_{r_{1}} ⊕ M_{r_{2}} ⊕ ⋯ ⊕ M_{r_{t}}. For every 1 ≤ i ≤ t, since M_{r_{i}} represents the quasi-full rooted tree T_{i}, by Theorem 6, M_{r_{i}} satisfies the conditions for successive nonunit direct terms and ordinal terms given in the hypothesis. This shows that M_{n} follows the conditions in the hypothesis.

Conversely, suppose we can relabel M_{n} in such a form that it satisfies the conditions in the hypothesis. Then M_{n} satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{t−1} for some l_{1} < l_{2} < ⋯ < l_{t−1}. Assign r_{i} = l_{i} − l_{i−1}, 1 ≤ i ≤ t, where we assume l_{0} = 0 and l_{t} = n − 1. Then by Theorem 3, there exist Q_{r_{i}}, 1 ≤ i ≤ t, such that M_{n} = Q_{r_{1}} ⊕ Q_{r_{2}} ⊕ ⋯ ⊕ Q_{r_{t}}. For every 1 ≤ i ≤ t, since Q_{r_{i}} satisfies the conditions for successive nonunit direct terms and ordinal terms given in the hypothesis, by Theorem 6, matrix Q_{r_{i}} represents a quasi-full rooted tree, say T_{i}. Then by Theorem 4, matrix M_{n} = Q_{r_{1}} ⊕ Q_{r_{2}} ⊕ ⋯ ⊕ Q_{r_{t}} represents the forest T_{1} + T_{2} + ⋯ + T_{t}. Since M_{n} represents F, we have F ≅ T_{1} + T_{2} + ⋯ + T_{t}, and hence F is a quasi-full rooted forest.

4 Exact enumeration of the quasi-full trees

The enumeration method for the unlabeled quasi-full rooted trees obtained in this section is based mainly on the results (Theorem 6 and Theorem 7) obtained in Section 3. Let M_{n,t}, where n ≥ 1 and t ≥ 1, be the collections of pairwise nonequivalent (relabeling) poset matrices that represent a quasi-full t-ary rooted tree with n elements. Trivially, we have M_{1,t≥1} = {1}, M_{2,t≥1} = {C_{2}}, and M_{n≥3,1} = {C_{n}}. In general, for the enumeration of the n-element unlabeled quasi-full t-ary rooted trees, here we find a formula that gives an exact enumeration of the matrices contained in the collection M_{n,t} for every 2 ≤ t < n.

Let M ∈ M_{n,t} for some n ≥ 3 and t ≥ 2. By Theorem 6, matrix M satisfies the block of 1s property of length 1; and every successive ordinal term of order r, where 1 < r < n, satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{h−1} for some l_{1} < l_{2} < ⋯ < l_{h−1}, where h = min(r, t), and every successive nonunit direct term satisfies the block of 1s property of length 1. In particular, we have M_{n,t} as follows:

1. Let M ∈ M_{3,2}. Then M satisfies the block of 1s property of length 1, and the nonunit ordinal term (a matrix of order 3−1 = 2) can satisfy the block of 0s property of length 1 only. Thus, both the direct terms are 1. Then M = 1 ⊞ (1 ⊕ 1) = 1 ⊞ I_{2} = B_{3} (as given in Section 3), and hence M_{3,2} = {B_{3}}. In general, since h = min(3 − 1, t) = 2, we have B_{3} ∈ M_{3,t} for every t ≥ 2. Therefore, M_{3,t≥2} = {B_{3}}.

2. Let M ∈ M_{4,2}. Then M satisfies the block of 1s property of length 1; and the nonunit ordinal term can satisfy the block of 0s property of length 1 (in this case, the direct terms are 1 and C_{2}) and length 2 (in this case, the direct terms are C_{2} and 1). Since 1 ⊕ C_{2} ∼ C_{2} ⊕ 1, we have M = 1 ⊞ (1 ⊕ C_{2}), and hence M_{4,2} = {1 ⊞ (1 ⊕ C_{2})}.

3. Let M ∈ M_{4,3}. Then M satisfies the block of 1s property of length 1; and the nonunit ordinal term (a matrix of order 4−1 = 3) can satisfy the block of 0s property of lengths 1, 2. Thus, all the direct terms are 1. Then M = 1⊞(1⊕1⊕1) = 1⊞I_{3} = B_{4} (as given in Section 3) and hence M_{4,3} = {B_{4}}. In general, if t ≥ 3, then h = min(4 − 1, t) = 3 implies that B_{4} ∈ M_{3,t} for every t ≥ 3. Therefore, M_{4,t≥3} = {B_{4}}.

We now have the following remarks.

Remark 8. We have M_{1,1} = {1}, M_{2,1} = {C_{2}}, and M_{n≥3,1} = {C_{n}} in general. Also, for every t ≥ 1, we have 1 ∈ M_{1,t} and C_{2} ∈ M_{2,t}. On the other hand, for t ≥ 2, we see that C_{n} ∉ M_{n,t} for any n ≥ 3. These happen because in each of these cases, the nonunit ordinal term C_{n−1} does not satisfy the block of 0s property for any length. But by Theorem 6, since h = min(n − 1, t) ≥ 2, the nonunit ordinal term C_{n−1} must satisfy the block of 0s property of lengths l_{1}, l_{2}, …, l_{h−1} for some l_{1} < l_{2} < ⋯ < l_{h−1}.

Remark 9. We have M_{3,2} = {B_{3}}, M_{4,2} = {1 ⊞ (1 ⊕ C_{2})}, and M_{4,3} = {B_{4}}. Also, for every t ≥ 2, we have B_{3} ∈ M_{3,t} and B_{4} ∈ M_{4,t}. On the other hand, for every t ≥ 3, we see that 1 ⊞ (1 ⊕ C_{2}) ∉ M_{4,t} . These happen because in each of these cases, the nonunit ordinal term 1 ⊕ C_{2} can satisfy the block of 0s property of length 1 only. But by Theorem 6, since h = min(3, t) = 3, the ordinal term 1 ⊕ C_{2} must satisfy the block of 0s property of lengths l_{1}, l_{2} for some l_{1} < l_{2}.

In the following, we generalize the facts observed in Remark 8 and Remark 9.

Theorem 10. Let M be a poset matrix and n ≥ 3 be given. Then

(i) M ∈ M_{n,n−1} implies M ∈ M_{n,t≥n}, and

(ii) M ∈ M_{n,t} for some t ≤ n − 2 implies M ∉ M_{n,t≥n}.

Proof.

(i) Let M ∈ M_{n,n−1}. Since M satisfies the block of 1s property of length 1, the nonunit ordinal term of M, say P, is a matrix of order n − 1. Then P must satisfy the block of 0s property of lengths 1, 2, …, n − 2. Since min(n − 1, t) − 1 = n − 2 for all t ≥ n, by Theorem 6, we have M ∈ M_{n,t≥n}.

(ii) Let M ∈ M_{n,t} for some t ≤ n − 2. Then, since M satisfies the block of 1s property of length 1, the nonunit ordinal term of M, say Q, is a matrix of order n − 1. Since min(n − 1, t) = t, the matrix Q satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{k} for some l_{1} < l_{2} < ⋯ < l_{k}, where k = t − 1 ≤ n − 3. But, for all t ≥ n, we have k = min(n − 1, t) − 1 = n − 2 > n − 3. Therefore, by Theorem 6, we have M ∉ M_{n,t≥n}.

As an illustration of the result obtained in Theorem 10, we present the poset matrices M ∈ M_{n,t} for all 1 ≤ n ≤ 6 and 1 ≤ t ≤ 5 in Table 1.

t ⧹ n 1 2 3  4  5  6
1  1 C_{2} C_{3}  C_{4}  C_{5}  C_{6}
2  B_{3} 1 ⊞ (1 ⊕ C_{2}) \begin{matrix}1 ⊞ (1 ⊕ B_{3}), \\ 1 ⊞ (C_{2} ⊕ C_{2}) \end{matrix} \begin{matrix}1 ⊞ (C_{2} ⊕ B_{3}), \\ 1 ⊞ (1 ⊕ (1 ⊞ (1 ⊕ C_{2}))) \end{matrix}
3  B_{4}  1 ⊞ (I_{2} ⊕ C_{2})  \begin{matrix}1 ⊞ (I_{2} ⊕ B_{3}), \\ 1 ⊞ (1 ⊕ C_{2} ⊕ C_{2}) \end{matrix}
4  1⊞I_{4}  1 ⊞ (I_{3} ⊕ C_{2})
5  1 ⊞ I_{5}

Table 1: Poset matrices in M_{n,t} for all 1 ≤ n ≤ 6 and 1 ≤ t ≤ 5.

Let N_{n,t}, 2 ≤ t ≤ n, be the collections of pairwise nonequivalent (relabeling) poset matrices that represent a quasi-full t-ary rooted forest with n elements. For n ≥ 2, the result obtained in Theorem 7 implies that every matrix M_{n} ∈ N_{n,t} satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{t−1} for some l_{1} < l_{2} < ⋯ < l_{t−1}; and every successive direct term until 1 satisfies the block of 1s property of length 1, and every successive ordinal term M_{r} ≠ 1 satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{h−1} for some l_{1} < l_{2} < ⋯ < l_{h−1}, where h = min(r − 1, t). We apply this characterization of rooted forests to construct the matrices in M_{n+1,t} for every 2 ≤ t ≤ n, using the matrices in N_{n,t}. For example, let M ∈ N_{2,2}. Here, M satisfies the block of 0s property of length 1 only, so both direct terms are 1. Thus, M = 1 ⊕ 1 = I_{2}, and hence N_{2,2} = {I_{2}}. Again, take M ∈ N_{3,3}. In this case, M satisfies the block of 0s property for lengths 1, 2, so all direct terms are 1. Therefore, M = 1 ⊕ 1 ⊕ 1 = I_{3}, and hence N_{3,3} = {I_{3}}. In general, we have N_{n≥2,t=n} = {I_{n}}. For some 2 ≤ t < n, we observe the contents of N_{n,t} as follows:

1. Let M ∈ N_{3,2}. Then M can satisfy the block of 0s property of length 1 and length 2. In both cases, the direct terms are 1 and C_{2}. Since 1 ⊕ C_{2} ∼ C_{2} ⊕ 1, in this case, we have M = 1 ⊕ C_{2}. Thus, N_{3,2} = {1 ⊕ C_{2}}. Again, let M ∈ N_{4,3}. Then M can satisfy the block of 0s property of lengths 1, 2, lengths 1, 3, and lengths 2, 3. In all of these cases, the direct terms are 1, 1, and C_{2}. Since C_{2} ⊕ 1 ⊕ 1 ∼ 1 ⊕ C_{2} ⊕ 1 ∼ 1 ⊕ 1 ⊕ C_{2} = I_{2} ⊕ C_{2}, in this case, we have M = I_{2} ⊕ C_{2}. Thus, N_{4,3} = {I_{2} ⊕ C_{2}}.

2. Let M ∈ N_{4,2}. Then M can satisfy the block of 0s property of length 1 (here, the direct terms are 1 and B_{3}), length 2 (here, both the direct terms are C_{2}), and length 3 (here, the direct terms are B_{3} and 1). Since 1 ⊕ B_{3} ∼ B_{3} ⊕ 1, in this case, M = 1 ⊕ B_{3} or M = C_{2} ⊕ C_{2}. Thus, N_{4,2} = {1 ⊕ B_{3}, C_{2} ⊕ C_{2}}.

We now generalize the above observations. We recall the nonisomorphic direct sum criterion for poset matrices obtained by Mohammad et al. [14]. Here, we justify when a pair of poset matrices, each of which satisfies the block of 0s property of some lengths, are nonequivalent. Let M, M′ ∈ N_{n,t}, where 2 ≤ t ≤ n, such that both M and M′ satisfy the block of 0s property. The poset matrix M satisfies the block of 0s property of lengths l_{1}, l_{2}, …, l_{t−1} for some l_{1} < l_{2} < ⋯ < l_{t−1}, and matrix M′ satisfies the block of 0s property of lengths l′_{1}, l′_{2}, …, l′_{t−1} for some l′_{1} < l′_{2} < ⋯ < l′_{t−1}. Since the direct sum of poset matrices is commutative, it is possible that M ∼ M′ (relabeling equivalent) even if l_{k} ≠ l′_{k} for all 1 ≤ k ≤ t−1. Recall that if M ∼ M′, then the forests represented by the matrices M and M′ are isomorphic. In the following, a revision of the result obtained by Mohammad et al. [14] regarding the nonisomorphic direct sum of the poset matrices representing disconnected series-parallel posets gives the condition for the lengths l_{1}, l_{2}, …, l_{t−1} and l′_{1}, l′_{2}, …, l′_{t−1} of the block of 0s property satisfied by the matrices M and M′ so that the matrices M and M′ represent nonisomorphic forests.

Theorem 11. [14] Let M, M′ ∈ N_{n,t}, n ≥ 2, such that both M and M′ satisfy the block of 0s property of the nondecreasing inter-distant lengths l_{1}, l_{2}, …, l_{t−1} and lengths l′_{1}, l′_{2}, …, l′_{t−1}, respectively, where l_{k} ≠ l′_{k} for some 1 ≤ k ≤ t − 1; and every direct term of M and M′ satisfies the block of 1s property for some lengths. Then M and M′ are relabeling inequivalent, that is, M ≁ M′.

Proof. Let l: l_{1}, l_{2}, …, l_{t−1} and l′: l′_{1}, l′_{2}, …, l′_{t−1}. For all 0 ≤ i ≤ t − 1, say r_{i} = l_{i+1} − l_{i} and r′_{i} = l′_{i+1} − l′_{i}, where we assign l_{0} = l′_{0} = 0 and l_{t} = l′_{t} = n. Since both M and M′ satisfy the block of 0s property of the lengths l and l′, respectively, by Theorem 3, there exist M_{r_{i}}, M′_{r′_{i}}, 1 ≤ i ≤ t, such that M = M_{r_{1}} ⊕ M_{r_{2}} ⊕ ⋯ ⊕ M_{r_{t}} and M′ = M′_{r′_{1}} ⊕ M′_{r′_{2}} ⊕ ⋯ ⊕ M′_{r′_{t}}. Suppose that there exists 1 ≤ k_{0} ≤ t−1 such that l_{k_{0}} ≠ l′_{k_{0}}. This implies r_{k_{0}} ≠ r′_{k_{0}} and hence M_{r_{k_{0}}} ≠ M′_{r′_{k_{0}}}. Since the lengths l and l′ are nondecreasing inter-distant, both the sequences r_{i}, r′_{i}, 1 ≤ i ≤ t, are nondecreasing. This implies either M_{r_{k_{0}}} ≠ M′_{r′_{i}} for all k_{0} < i ≤ t or M′_{r′_{k_{0}}} ≠ M_{r_{i}} for all k_{0} < i ≤ t. Since for all 1 ≤ i ≤ t, the direct terms M_{r_{i}} and M′_{r′_{i}} satisfy the block of 1s property for some lengths, we have M_{r_{k_{0}}} ⊕ ⋯ ⊕ M_{r_{t}} ≁ M′_{r′_{k_{0}}} ⊕ ⋯ ⊕ M′_{r′_{t}}. This implies M_{r_{1}} ⊕ M_{r_{2}} ⊕ ⋯ ⊕ M_{r_{t}} ≁ M′_{r′_{1}} ⊕ M′_{r′_{2}} ⊕ ⋯ ⊕ M′_{r′_{t}}, that is, M ≁ M′.

As an illustration of the result obtained in Theorem 11, the poset matrices M ∈ N_{n,t} for all 2 ≤ t ≤ n ≤ 5 are presented in Table 2. The following observations show that every M ∈ N_{n,t} can be constructed uniquely by taking the direct sum of t matrices taken from the collections M_{r,t}, 1 ≤ r ≤ n − t + 1, given in Table 1.

t ⧹ n 2  3  4  5
2  I_{2} 1 ⊕ C_{2} C_{2} ⊕ C_{2}, 1 ⊕ B_{3} C_{2} ⊕ B_{3}, 1 ⊕ (1 ⊞ (1 ⊕ C_{2}))
3  I_{3}  I_{2} ⊕ C_{2}  1 ⊕ C_{2} ⊕ C_{2}, I_{2} ⊕ B_{3}
4  I_{4}  I_{3} ⊕ C_{2}
5  I_{5}

Table 2: Poset matrices in N_{n,t} for all 2 ≤ t ≤ n ≤ 5.

1. To construct the matrices in N_{2,2} = {I_{2} = 1 ⊕ 1}, N_{3,3} = {I_{3} = 1 ⊕ 1 ⊕ 1}, N_{4,4} = {I_{4} = 1 ⊕ 1 ⊕ 1 ⊕ 1}, and so on; we need only the unit matrix in M_{1,t≥2} = {1}.

2. To construct the matrices in N_{3,2} = {1 ⊕ C_{2}}, N_{4,3} = {I_{2} ⊕ C_{2}}, N_{5,4} = {I_{3} ⊕ C_{2}}, and so on; we need only the matrices in the collections M_{1,t≥2} = {1} and M_{2,t≥2} = {C_{2}}.

3. To construct the matrices in N_{4,2} = {1 ⊕ B_{3}, C_{2} ⊕ C_{2}}, N_{5,3} = {I_{2} ⊕ B_{3}, 1 ⊕ C_{2} ⊕ C_{2}} = {1 ⊕ 1 ⊕ B_{3}, 1 ⊕ C_{2} ⊕ C_{2}}, and so on; we need only the matrices in the collections M_{1,t≥2} = {1}, M_{2,t≥2} = {C_{2}}, and M_{3,t≥2} = {B_{3}}.

4. To construct the matrices in N_{5,2} = {1 ⊕ (1 ⊞ (1 ⊕ C_{2})), C_{2} ⊕ B_{3}}, and so on; we need only the matrices in the collections M_{1,t≥2} = {1}, M_{2,t≥2} = {C_{2}}, M_{3,t≥2} = {B_{3}}, M_{4,2} = {1 ⊞ (1 ⊕ C_{2})}, and M_{4,t≥3} = {1 ⊞ I_{3}}.

Suppose, for given n and t, where 2 ≤ t ≤ n, we want to enumerate the matrices in M_{n+1,t}. Also, let M_{r,t} be given for all 1 ≤ r ≤ n − t + 1. For t ≥ 2, to construct the matrices in M_{n+1,t}, we first construct the matrices in N_{n,t} by using the matrices in M_{r,t}, 1 ≤ r ≤ n − t + 1. Here, we apply the direct sum criterion for poset matrices obtained in Theorem 11. For every M ∈ N_{n,t}, by Theorem 6 and Theorem 7, the ordinal sum 1 ⊞ M satisfies the condition for being a member of M_{n+1,t}, that is, 1 ⊞ M ∈ M_{n+1,t}. Also, for every P ∈ M_{n+1,t}, there exists M′ ∈ N_{n,t} such that P = 1 ⊞ M′. Thus, there is a oneto-one correspondence between M_{n+1,t} and N_{n,t}, and hence |M_{n+1,t}| = |N_{n,t}|. Therefore, the enumeration of M_{n+1,t} is equivalent to the enumeration of N_{n,t}. Suppose we want to determine |N_{n,t}| for some 2 ≤ t ≤ n. Then, by Theorem 11, it is enough to determine the number of ways in which a poset matrix M_{n} can satisfy the block of 0s property of the nondecreasing inter-distant lengths l_{1}, l_{2}, …, l_{t−1} for some l_{1} < l_{2} < ⋯ < l_{t−1}, such that the direct terms M_{l_{1}}, M_{l_{2}−l_{1}}, …, M_{n−l_{t−1}} belong to some M_{r,t}, 1 ≤ r ≤ n − t + 1. We now obtain this result as a special case of the result [14, Theorem 4.3].

Theorem 12. Let 2 ≤ t ≤ n be given, and let every M_{n} ∈ N_{n,t} satisfy the block of 0s property of the nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)}, 1 ≤ j ≤ p, for some p ≤ \binom{n}{t}. Also let for every 1 ≤ j ≤ p and 1 ≤ k ≤ q_{j}, where q_{j} ≤ t, we have |M_{r_{jk},t}| and c_{jk}, the number of the k-th consecutive direct terms M_{r_{jk}} of M_{n}, where r_{jk} = l_{j(h+1)} − l_{jh} for some 0 ≤ h ≤ t − 1 with l_{j0} = 0 and l_{jt} = n. Then we have |N_{n,t}| as follows:

|N_{n,t}| = ∑_{j=1}^{p} ∏_{k=1}^{q_{j}} \binom{|M_{r_{jk},t}| + c_{jk}}{1 + c_{jk}}, 2 ≤ t ≤ n.  (1)

Proof. For every 1 ≤ j ≤ p, where p ≤ \binom{n}{t}, let S_{j} be the number of different ways in which an M_{n} ∈ N_{n,t} can satisfy the block of 0s property of the nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)} such that the direct terms M_{r_{jk}} of M_{n} belong to M_{r_{jk},t}. Then for every 1 ≤ j ≤ p, there are S_{j} pairwise nonequivalent poset matrices M_{n} in N_{n,t} that satisfy the j-th nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)}. Then we have r_{jk}, c_{jk}, 1 ≤ k ≤ q_{j}, where q_{j} ≤ t, as follows:

r_{j1} = l_{ji} − l_{j(i−1)}, 1 ≤ i ≤ t_{j1} + 1,
r_{j2} = l_{ji} − l_{j(i−1)}, t_{j1} + 2 ≤ i ≤ t_{j2} + 1,
⋮
r_{jq_{j}} = l_{ji} − l_{j(i−1)}, t_{j(q_{j}−1)} + 2 ≤ i ≤ t_{jq_{j}} + 1.

Here r_{j1} < r_{j2} < ⋯ < r_{jq_{j}}, and we assume l_{j0} = 0 and l_{jt} = n. Then the direct terms of M_{n} are the matrices M_{r_{jk}}, 1 ≤ i ≤ t_{jk} + 1, 1 ≤ k ≤ q_{j}. By hypothesis, for every 1 ≤ i ≤ t_{jk} + 1 and 1 ≤ k ≤ q_{j}, matrix M_{r_{jk}} ∈ M_{r_{jk},t}. For every 1 ≤ j ≤ p and 1 ≤ k ≤ q_{j}, since M_{r_{jk}} belong to M_{r_{jk},t}, by [14, Theorem 3.8], the number of distinct poset matrices M_{n} ∈ N_{n,t} that satisfy the j-th nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)} is

\binom{|M_{r_{jk},t}| + c_{jk}}{1 + c_{jk}}.

Since the lengths r_{jk}, 1 ≤ k ≤ q_{j}, are all strictly increasing, by [14, Theorem 3.7], we have S_{j} as follows:

S_{j} = ∏_{k=1}^{q_{j}} \binom{|M_{r_{jk},t}| + c_{jk}}{1 + c_{jk}}.  (2)

Since the equation (2) holds for all nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)}, 1 ≤ j ≤ p, by Theorem 11, we have |N_{n,t}| as follows:

|N_{n,t}| = ∑_{j=1}^{p} S_{j} = ∑_{j=1}^{p} ∏_{k=1}^{q_{j}} \binom{|M_{r_{jk},t}| + c_{jk}}{1 + c_{jk}}, 2 ≤ t ≤ n.

The following examples illustrate the result obtained in Theorem 12.

Example 13. To determine the number |M_{9,2}|, we determine the number |N_{8,2}| by using the numbers |M_{r,2}| for all 1 ≤ r ≤ 7.

\begin{matrix}r : & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ |M_{r,2}| : & 1 & 1 & 1 & 1 & 2 & 2 & 4 \end{matrix}

j  l_{j1}, …, l_{j(t−1)}  r_{j1}, …, r_{jq_{j}}  S_{j}
1  1  1, 7  \binom{1}{1}\binom{4}{1} = 4
2  2  2, 6  \binom{1}{1}\binom{2}{1} = 2
3  3  3, 5  \binom{1}{1}\binom{2}{1} = 2
4  4  4, 4  \binom{1+1}{1+1} = 1

Total: 9

Therefore, |M_{9,2}| = |N_{8,2}| = 9.

Example 14. To determine the number |M_{10,3}|, we determine the number |N_{9,3}| by using the numbers |M_{r,3}| for all 1 ≤ r ≤ 7.

\begin{matrix}r : & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ |M_{r,3}| : & 1 & 1 & 1 & 1 & 1 & 2 & 3 \end{matrix}

j  l_{j1}, …, l_{j(t−1)}  r_{j1}, …, r_{jq_{j}}  S_{j}
1  1, 2  1, 1, 7  \binom{1+1}{1+1}\binom{3}{1} = 3
2  1, 3  1, 2, 6  \binom{1}{1}\binom{1}{1}\binom{2}{1} = 2
3  1, 4  1, 3, 5  \binom{1}{1}\binom{1}{1}\binom{1}{1} = 1
4  1, 5  1, 4, 4  \binom{1}{1}\binom{1+1}{1+1} = 1
5  2, 4  2, 2, 5  \binom{1+1}{1+1}\binom{1}{1} = 1
6  2, 5  2, 3, 4  \binom{1}{1}\binom{1}{1}\binom{1}{1} = 1
7  3, 6  3, 3, 3  \binom{1+2}{1+2} = 1

Total: 10

Therefore, |M_{10,3}| = |N_{9,3}| = 10.

5 Enumeration algorithm

Recall that the numbers p and q_{j}, 1 ≤ j ≤ p, in equation (1) are not specified explicitly. For given 2 ≤ t ≤ n, the computation of p and q_{j} depends on the constructions of the nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)} and the quantities r_{j1}, r_{j2}, …, r_{jt} for every 1 ≤ j ≤ p. We use Algorithm 15 to determine the numbers p and q_{j}, 1 ≤ j ≤ p, and to compute finally |M_{n+1,t}| = |N_{n,t}|, the number of (n + 1)-element unlabeled quasi-full t-ary rooted trees for given n and t, where 2 ≤ t ≤ n.

Algorithm 15. To compute Count = |M_{n+1,t}| for given n and t, where 2 ≤ t ≤ n.

(1) Initialize Count = 0.

(2) Repeat (a) to (d) for every nondecreasing inter-distant length (there are p such distinct lengths; see equation (1)) as constructed in (b).

(a) Initialize S_{j} = 1.

(b) Construct the j-th nondecreasing inter-distant lengths l_{j1}, l_{j2}, …, l_{j(t−1)} (there are t − 1 integers l_{j1} ≤ l_{j2} ≤ ⋯ ≤ l_{j(t−1)}) chosen from 1, 2, …, n − 1.

(c) Compute the j-th quantities r_{j1}, r_{j2}, …, r_{jt} by taking the differences of the consecutive lengths l_{j1}, l_{j2}, …, l_{j(t−1)}, and repeat (i) and (ii) for every distinct collection (there are q_{j} collections in total; see equations (1) and (2)) of the quantities r_{j1}, r_{j2}, …, r_{jt}.

(i) Determine c_{jk}, the number of repetitions of the k-th collection of the same consecutive terms in the j-th quantities r_{j1}, r_{j2}, …, r_{jt}.

(ii) Update S_{j} with S_{j} × \binom{|M_{r_{jk}} |+c_{jk}}{1+c_{jk}}.

(d) Increase Count by S_{j}.

(3) Return Count.

Let n and t be given such that 2 ≤ t ≤ n. For j ≥ 1, we see that the numbers l_{j1}, l_{j2}, …, l_{j(t−1)} and r_{j1}, r_{j2}, …, r_{jt} are all integers. Therefore, the atomic operations considered in the above computation involve arithmetic on integers with at most O(log n) bits. For every 1 ≤ j ≤ p, where p ≥ 1, the computational process allocates space for the integers l_{ji}, 1 ≤ i ≤ t − 1, and r_{jk}, 1 ≤ k ≤ t, at two separate scopes. Thus, the computation uses at most O((t − 1) + t) ≈ O(n + n) ≈ O(n) space. In the following, we determine the time complexity of Algorithm 15.

Lemma 16. Algorithm 15 runs in time O(n^{4}).

Proof. The constructions of the sequences l_{j1}, l_{j2}, …, l_{j(t−1)} at step (b) have complexity equal to (t − 1)(n − 1). Since t ≤ n, we have (t − 1)(n − 1) ≈ O((n − 1)(n − 1)) ≈ O(n^{2}). Again, since 1 ≤ c_{jk}, q_{j} ≤ t − 1, and c_{jk} is inversely proportional to q_{j} for every k, the computations of c_{jk} at the step (i) have complexity equal to t − 1. Then t ≤ n implies that the repetitions at the step (c) induce an amount of complexity equal to t(t − 1) ≈ O(n(n − 1)) ≈ O(n^{2}). The sum of the complexities at the steps (b) and (c) then equals O(n^{2}) + O(n^{2}) ≈ O(n^{2}). By inspection, we have p ≤ n^{2}. Therefore, the repetitions at step (2) increase the overall complexity to n^{2}(O(n^{2})) ≈ O(n^{4}).

6 Data

We computationally implemented the enumeration algorithm (Algorithm 15) and determined the numbers |M_{n,t}| up to certain values of n for all 2 ≤ t < n. An implementation of Algorithm 15 in MATLAB is available on GitHub [15]. Here, we include the numbers |M_{n,t}| for all 2 ≤ t < n ≤ 31; see Table 3 for all 3 ≤ n ≤ 20 and 2 ≤ t ≤ 19, and Table 4 for all 21 ≤ n ≤ 31 and 2 ≤ t ≤ 30. Also, see the integer sequence \underline{A352460} contributed to the

OEIS [19]. t ⧹ n 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2  1 1 2 2 4 5 9 13 23 35 61 98 170 281 487 823 1430 2451
3  1 1 2 3 4 6 10 15 24 39 63 103 171 282 471 790 1329
4  1 1 2 3 5 6 10 14 23 34 55 84 136 212 343 545
5  1 1 2 3 5 7 10 14 21 31 47 71 109 167 257
6  1 1 2 3 5 7 11 14 21 29 43 61 93 135
7  1 1 2 3 5 7 11 15 21 29 41 57 82
8  1 1 2 3 5 7 11 15 22 29 41 55
9  1 1 2 3 5 7 11 15 22 30 41
10  1 1 2 3 5 7 11 15 22 30
11  1 1 2 3 5  7 11 15 22
12  1 1 2 3  5  7 11 15
13  1 1 2  3  5  7 11
14  1 1  2  3  5  7
15  1  1  2  3  5
16  1  1  2  3
17  1  1  2
18  1  1
19  1
Total: 1 2 4 6 11 16 27 41 67 102 167 260 425 678 1115 1813 3018 4992

Table 3: The number of unlabeled quasi-full t-ary rooted trees with n elements for all 3 ≤ n ≤ 20 and 2 ≤ t ≤ 19.

7 Acknowledgment

This work was supported by the Research Grant 2022-23, SUST Research Center, Shahjalal University of Science and Technology, Sylhet-3114, Bangladesh [Grant no. PS/2022/1/20]. Special thanks to the anonymous referee for carefully reviewing the manuscript and providing numerous corrections and suggestions to enhance the presentation of the results.

t⧹ n  21  22  23  24  25  26  27  28  29  30  31
2  4274 7404 12964 22633 39789 69892 123342 217717 385569 683344 1214044
3  2245 3811 6480 11061 18928 32471 55830 96215 166112 287350 497911
4  886 1422 2318 3755 6144 10022 16458 26994 44483 73284 121138
5  396 613 951 1483 2316 3632 5702 8977 14152 22361 35381
6  205 305 462 690 1047 1572 2389 3614 5509  8380 12822
7  117 170 248 364 535  789 1163 1716 2533  3745  5541
8  78 106 151 211 304  432  627  901 1311  1892  2750
9  55  76 102 140 192  266  370  521  734  1042  1483
10  42  55  76 100 136  181  247  332  458  626  872
11  30  42  56  76 100  134  177  236  313  420  563
12  22  30  42  56  77  100  134  175  232  302  401
13  15  22  30  42  56  77  101  134  175  230  298
14  11  15  22  30  42  56  77  101  135  175  230
15  7  11  15  22  30  42  56  77  101  135  176
16  5  7  11  15  22  30  42  56  77  101  135
17  3  5  7  11  15  22  30  42  56  77  101
18  2  3  5  7  11  15  22  30  42  56  77
19  1  2  3  5  7  11  15  22  30  42  56
20  1  1  2  3  5  7  11  15  22  30  42
21  1  1  2  3  5  7  11  15  22  30
22  1  1  2  3  5  7  11  15  22
23  1  1  2  3  5  7  11  15
24  1  1  2  3  5  7  11
25  1  1  2  3  5  7
26  1  1  2  3  5
27  1  1  2  3
28  1  1  2
29  1  1
30  1
Total: 8395 14101 23947 40708 69763 119763 206812 357905 622089 1083659 1894118

Table 4: The number of unlabeled quasi-full t-ary rooted trees with n elements for all 21 ≤ n ≤ 31 and 2 ≤ t ≤ 30.

References

[1] C. Chauve, S. Dulucq, and O. Guibert, Enumeration of some labeled trees, Formal Power Series and Algebraic Combinatorics, Springer-Verlag, Berlin, 2000, pp. 146–157.

[2] G. S. Cheon, B. Curtis, G. Kwon, and A. M. Mwafise, Riordan posets and associated incidence matrices, Linear Algebra Appl. 632 (2022), 308–331.

[3] B. A. Davey and H. A. Priestly, Introduction to Lattices and Order, 2nd Edition, Cambridge University Press, 2002.

[4] N. Dershowitz and S. Zaks, Enumerations of ordered trees, Discrete Math. 31 (1980), 9–28.

[5] N. Gabriel, K. Peske, L. Pudwell, and S. Tay, Pattern avoidance in ternary trees, J. Integer Sequences 15 (2012), Article 12.1.5.

[6] T. Gilmore, Trees, forests, and total positivity: I. q-trees and q-forests matrices, Electron. J. Combin. 28 (2021), Article P3.54.

[7] S. Guo and J. W. Guo, A recursive algorithm for trees and forests, Discrete Math. 340 (2017), 695–703.

[8] S. U. Mohammad and M. R. Talukder, Poset matrix and recognition of series-parallel posets, Int. J. Math. Comput. Sci. 15 (2020), 107–125.

[9] S. U. Mohammad and M. R. Talukder, Interpretations of Kronecker product and ordinal product of poset matrices, Int. J. Math. Comput. Sci. 16 (2021), 1665–1681.

[10] S. U. Mohammad, M. S. Noor, and M. R. Talukder, An exact enumeration of the unlabeled disconnected posets, J. Integer Sequences 25 (2022), Article 22.5.4.

[11] S. U. Mohammad, M. R. Talukder, and S. N. Begum, Recognition of decomposable posets by using the poset matrix, Ital. J. Pure Appl. Mat. 50 (2023), 455–466.

[12] S. U. Mohammad, M. S. Noor, and M. R. Talukder, Recognition of the N-free posets by using the poset matrix, Asia Pac. J. Math. 11 (2024), Article 72.

[13] S. U. Mohammad, M. R. Talukder, and S. N. Begum, Enumeration of P -series by using the poset matrix, Asia Pac. J. Math. 12 (2025), Article 68.

[14] S. U. Mohammad, M. R. Talukder, and S. N. Begum, Enumeration of series-parallel posets by using the poset matrix, Palest. J. Math. 14 (2025), 217–232.

[15] S. U. Mohammad, GitHub Repository: Enumeration of quasi-full rooted trees (an implementation in MATLAB), 2025. Available at https://github.com/SU-Mohammad/

Enumeration-of-Quasi-full-Rooted-Trees.git.

[16] A. M. Mwafise, Poset matrix structure via partial composition operations, arxiv preprint arXiv:2212.11644v4 [math.CO], 2024. Available at http://arxiv.org/abs/

2212.11644v4.

[17] P. W. Shor, A new proof of Cayley’s formula for counting labeled trees, J. Combin. Theory Ser. A 71 (1995), 154–158.

[18] M. Skandera and B. Reed, Total nonnegativity and (3 + 1)-free posets, J. Combin. Theory Ser. A 103 (2003), 237–256.

[19] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available

    at https://oeis.org.

[20] K. Yamanaka, Y. Otachi, S. Nakano, Efficient enumeration of ordered trees with k leaves, Theoret. Comput. Sci. 442 (2012), 22–27.

2020 Mathematics Subject Classification: Primary 06A07; Secondary 05A15, 11Y55. Keywords: quasi-full rooted tree, series-parallel poset, direct sum, ordinal sum, poset matrix, matrix recognition, exact enumeration.

(Concerned with sequences \underline{A000081}, \underline{A000169}, \underline{A048816}, \underline{A238372}, \underline{A287211}, \underline{A299038}, \underline{A306201}, \underline{A319541}, \underline{A320160}, \underline{A320270}, and \underline{A352460}.)

Received September 23 2024; revised version received October 23 2025. Published in Journal of Integer Sequences, October 27 2025.

Return to Journal of Integer Sequences home page.