\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[table]{xcolor}
\usepackage{multirow}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,0.5,0}
\definecolor{webbrown}{rgb}{0.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\DeclareMathOperator{\lcm}{lcm}
\newcommand\la{\langle}
\newcommand\ra{\rangle}
\newcommand\df{\emph}
\newcommand\ls{\leqslant}
\newcommand\nls{\nleqslant}
\newcommand\pos{\mathbf}
\newcommand\dg{\cellcolor{gray}}
\newcommand\g{\cellcolor{lightgray}}
\newcommand\bb{\cellcolor{blue}}
\newcommand\tb[1][0.3cm]{\hspace*{#1}}
\newcommand\tab[1][0.7cm]{\hspace*{#1}}
\newcommand\taab[1][1.5cm]{\hspace*{#1}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{algorithm}[theorem]{Algorithm}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}

\vskip 1cm
{\LARGE\bf 
Recognition and Enumeration of the\\
\vskip .1in
Quasi-Full Rooted Trees
}
\vskip 1cm
\large
Salah Uddin Mohammad, Md.\ Shah Noor, and Md.\ Rashed Talukder\\
Department of Mathematics\\
Shahjalal University of Science and Technology\\
Sylhet-3114\\
Bangladesh\\   
\href{mailto:salahuddin-mat@sust.edu}{\tt salahuddin-mat@sust.edu}\\
\href{mailto:msnoor-mat@sust.edu}{\tt msnoor-mat@sust.edu}\\
\href{mailto:r.talukder-mat@sust.edu}{\tt r.talukder-mat@sust.edu}
\end{center}

\vskip 0.2in

\begin{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\leq 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\leq t<n\leq 31$.
\end{abstract}


\section{Introduction}
We introduce a new class of rooted trees, which we call the \df{quasi-full rooted trees}. A rooted tree with arity $t$ is called \df{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 quasi-full 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~\cite{Chauve2000,Dershowitz1980,Gabriel2012,Gilmore2021,Guo2017,Shor1995,Yamanaka2012}. Also, there are a number of integer sequences in the {\it On-Line Encyclopedia of Integer
Sequences} (OEIS)~\cite{Sloane2024} that provide some existing results on the exact enumerations of several types of labeled and unlabeled rooted trees. These include full rooted trees (\seqnum{A319541}), balanced rooted trees (\seqnum{A306201}, \seqnum{A320160}, \seqnum{A320270}), complete rooted trees (\seqnum{A287211}), and rooted trees with all leaves at the same level (\seqnum{A238372}, \seqnum{A048816}). For the enumerations of labeled and unlabeled rooted trees in general, see also the sequences \seqnum{A000169}, \seqnum{A000081}, and \seqnum{A299038} in the OEIS~\cite{Sloane2024}.

 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~\cite{Mohammad2020}. 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\leq 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~\cite{Cheon2022,Mohammad2024,Skandera2003}. 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~\cite{Mohammad2020} coined the term \df{poset matrix}. Recently, the poset matrix has gained much attention in the recognition and classification of various classes of posets and graphs; see~\cite{Cheon2022,Mohammad2021,Mohammad2023,Mohammad2024,Mwafise2024}. 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.~\cite{Mohammad2025APJM,Mohammad2025PJM}. 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 $\mathcal{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~\seqnum{A352460} contributed to the OEIS~\cite{Sloane2024}.
 
 In Section~\ref{Preliminaries}, we introduce the quasi-full rooted trees and quasi-full rooted forests as posets with constructive examples. In Section~\ref{SecRecogTreesForests}, we give the matrix recognitions of the quasi-full rooted trees and quasi-full rooted forests by using the poset matrix. In Section~\ref{SecEnumerQuasiFullRootedTrees}, we obtain an exact enumeration of the unlabeled quasi-full $t$-ary rooted trees with $n$ elements, where $2\leq t<n$. In Section~\ref{SecEnumAlgorithm}, we give the enumeration algorithm and prove its time complexity. Moreover, in Section~\ref{SecEnumerData}, we include the data (Table~\ref{TabEnumTreesUpto20} and Table~\ref{TabEnumTreesUpto31}) regarding the number of $n$-element unlabeled quasi-full $t$-ary rooted trees for all $2\leq t<n\leq 31$.




\section{Quasi-full rooted trees and forests as posets}
\label{Preliminaries}
A \df{poset} (\df{partially ordered set}) is a structure $\pos{A}=\la A,\ls \ra$ consisting of the nonempty set $A$ with the order relation $\ls$ on $A$, that is, the relation $\ls$ is reflexive, antisymmetric, and transitive on $A$. Note that the results in this article are applicable to finite posets only. We use the notation $\textbf{1}$ for the singleton poset, $\pos{C}_{n\geq 1}$ for the $n$-element chain poset, $\pos{I}_{n\geq 1}$ for the $n$-element antichain poset, and $\pos{B}_{m\geq 1,n\geq 1}$ for the complete bipartite poset with $m$ minimal elements and $n$ maximal elements. We write $\pos{A}\cong \pos{B}$ if $\pos{A}$ and $\pos{B}$ are order isomorphic. In particular, we have $\pos{C}_1\cong\pos{I}_1\cong\pos{1}$ and $\pos{B}_{1,1}\cong\pos{C}_2$. We also use the notation $\pos{A}+\pos{B}$ and $\pos{A}\oplus\pos{B}$ to denote, respectively, the direct sum and ordinal sum of the posets $\pos{A}$ and $\pos{B}$. Here, the posets $\pos{A}$ and $\pos{B}$ are called the \df{direct terms} of $\pos{A}+\pos{B}$ and the \df{ordinal terms} of $\pos{A}\oplus\pos{B}$. For every $m\geq 1$ and $n\geq 1$, we have $\pos{B}_{m,n}\cong\pos{I}_m\oplus\pos{I}_n$. Here, $\pos{I}_m$ and $\pos{I}_n$ are the ordinal terms of the poset $\pos{B}_{m,n}$. Also, for every $n\geq 2$, we have $\pos{I}_n\cong\underbrace{\pos{1}+\pos{1}+\cdots+\pos{1}}_{n\text{ terms }}$ and $\pos{C}_n\cong\underbrace{\pos{1}\oplus\pos{1}\oplus\cdots\oplus\pos{1}}_{n\text{ terms }}$. A poset having two or more direct terms is called \df{disconnected}; otherwise, it is called \df{connected}. A poset is called \df{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~\cite{Davey2002}.
 
 A \df{rooted tree} is an acyclic graph with a fixed element (node or vertex) called the \df{root} of the tree. The immediate successors of an element in a rooted tree are called \df{children} of that element. An element except the root in a tree having no children is called a \df{leaf}, and an element having at least one child is called an \df{internal element}. In a rooted tree, the root is supposed to be at \df{level} $0$, and the children of an internal element go to the immediate upper level. By a \df{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 $\pos{1}$, is called the \df{nullary tree} or \df{seed}. We can consider the tree $\pos{1}$ (the singleton poset) just as a seed. A rooted tree is said to have \df{arity} $t$, where $t\geq 1$, if every internal element of the tree has at most $t$ children. A $t$-ary rooted tree is called \df{full} if every internal element has exactly $t$ children. A full rooted tree having all its leaves at the same level is called \df{perfect}. A $t$-ary rooted tree is called \df{balanced} if all its leaves are at the highest two levels. A $t$-ary balanced rooted tree is called \df{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 \df{quasi-full rooted tree}.

\begin{definition}
 A $t$-ary rooted tree is called \df{quasi-full} if the root of every subtree with $r$ elements has exactly $\min(r-1,t)$ children.
\end{definition}

For example, the rooted trees $\pos{C}_2$, $\pos{B}_{1,2}\cong\pos{1}\oplus\pos{I}_2$, $\pos{1}\oplus(\pos{1}+\pos{C}_2)$, $\pos{B}_{1,3}\cong\pos{1}\oplus\pos{I}_3$, and $\pos{1}\oplus(\pos{C}_2+\pos{C}_2)$, as shown in Figure~\ref{Fig234ElemQfullRootedTrees} by their Hasse diagrams, are all quasi-full rooted trees. Let $\mathcal{T}_{n,t}$, where $n\geq 1$ and $t\geq 1$, be the collections of quasi-full $t$-ary rooted trees with $n$ elements. In particular, we have the following.
\begin{enumerate}
\item $\mathcal{T}_{1,1}=\mathcal{T}_{1,2}=\cdots=\{\pos{1}\}$, $\mathcal{T}_{2,1}=\mathcal{T}_{2,2}=\cdots=\{\pos{C}_2\}$, $\mathcal{T}_{3,1}=\{\pos{C}_3\}$, $\mathcal{T}_{4,1}=\{\pos{C}_4\}$, $\mathcal{T}_{5,1}=\{\pos{C}_5\}$, and so on.
\item $\mathcal{T}_{3,t\geq 2}=\{\pos{1}\oplus\pos{I}_2\}=\{\pos{B}_{1,2}\}$, $\mathcal{T}_{4,t\geq 3}=\{\pos{1}\oplus\pos{I}_3\}=\{\pos{B}_{1,3}\}$, and so on.
\end{enumerate}
Also, we have $\mathcal{T}_{4,2} = \{\pos{1}\oplus(\pos{1}+\pos{C}_2)\}$, $\mathcal{T}_{5,2} = \{\pos{1}\oplus(\pos{C}_2+\pos{C}_2),\pos{1}\oplus(\pos{1}+\pos{B}_{1,2})\}$, and $\mathcal{T}_{5,3} = \{\pos{1}\oplus(\pos{I}_2+\pos{C}_2)\}$. In general, we have $\mathcal{T}_{n=1,t\geq 1} = \{\pos{1}\}$, $\mathcal{T}_{n=2,t\geq 1} = \{\pos{C}_2\}$, $\mathcal{T}_{n\geq 1,t=1} = \{\pos{C}_n\}$, $\mathcal{T}_{n\geq 2,t\geq n-1} = \{\pos{1}\oplus\pos{I}_{n-1}\} = \{\pos{B}_{1,n-1}\}$, and $\mathcal{T}_{n\geq 4,t=n-2}=\{\pos{1}\oplus(\pos{I}_{n-3}+\pos{C}_2)\}$.

\begin{figure}[H]
\centering \scalebox{1.0}{
  \setlength{\unitlength}{1bp}
  \begin{picture}(430.65, 105.02)(0,0)
  \put(0,0){\includegraphics{Fig234elemQfullRootedTrees.eps}}
  \put(7.67,8.12){\fontsize{12}{13.66}\selectfont $\pos{C}_2$}
  \put(84.36,8.12){\fontsize{12}{13.66}\selectfont $\pos{B}_{1,2}$}
  \put(160.47,8.12){\fontsize{12}{13.66}\selectfont $\pos{1}\oplus(\pos{1}+\pos{C}_2)$}
  \put(278.98,8.12){\fontsize{12}{13.66}\selectfont $\pos{B}_{1,3}$}
  \put(356.17,8.12){\fontsize{12}{13.66}\selectfont $\pos{1}\oplus(\pos{C}_2+\pos{C}_2)$}
  \end{picture}}
\caption{Some quasi-full rooted trees (Hasse diagrams of posets) up to $5$ elements.}
\label{Fig234ElemQfullRootedTrees}
\end{figure}

 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 $\pos{1}\oplus(\pos{1}+\pos{C}_2)$ and $\pos{1}\oplus(\pos{C}_2+\pos{C}_2)$, as given in Figure~\ref{Fig234ElemQfullRootedTrees}, 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 $\pos{1}\oplus(\pos{1}+\pos{C}_2)$ is not complete. Since $\pos{1}\oplus(\pos{1}+\pos{C}_2)$ is quasi-full, we call it \df{quasi-complete}. Similarly, we see that the quasi-full rooted tree $\pos{1}\oplus(\pos{C}_2+\pos{C}_2)$ has all its leaves at the same level. Since $\pos{1}\oplus(\pos{C}_2+\pos{C}_2)$ is not full, it is not perfect, and we call it \df{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~\ref{Fig234ElemQfullRootedTrees}) 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 \df{forest} is a collection of two or more trees or seeds. A \df{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 \df{quasi-full rooted forest}.

\begin{definition}
A rooted forest consisting of exactly $t$ quasi-full $t$-ary rooted trees or seeds is called a \df{quasi-full $t$-ary rooted forest}.
\end{definition}

Let $\mathcal{F}_{n,t}$, where $1\leq t\leq n$, be the collections of quasi-full $t$-ary rooted forests with $n$ elements. In particular, we have the following.
\begin{enumerate}
\item $\mathcal{F}_{1,1}=\{\pos{C}_1\}$, $\mathcal{F}_{2,1}=\{\pos{C}_2\}$, $\mathcal{F}_{3,1}=\{\pos{C}_3\}$, and so on. Thus $\mathcal{F}_{n\geq 1,t=1}=\{\pos{C}_n\}$.
\item $\mathcal{F}_{2,2}=\{\pos{I}_2\}$, $\mathcal{F}_{3,3}=\{\pos{I}_3\}$, $\mathcal{F}_{4,4}=\{\pos{I}_4\}$, and so on. Thus $\mathcal{F}_{n\geq 1,t=n}=\{\pos{I}_n\}$. 
\item $\mathcal{F}_{3,2}=\{\pos{I}_1+\pos{C}_2\}$, $\mathcal{F}_{4,3}=\{\pos{I}_2+\pos{C}_2\}$, and so on. Thus $\mathcal{F}_{n\geq 3,t=n-1}=\{\pos{I}_{n-2}+\pos{C}_2\}$.
\item $\mathcal{F}_{4,2}=\{\pos{C}_2+\pos{C}_2, \pos{1}+\pos{B}_{1,2}\}$, $\mathcal{F}_{5,2}=\{\pos{C}_2+\pos{B}_{1,2}\}$, and $\mathcal{F}_{5,3}=\{\pos{1}+\pos{C}_2+\pos{C}_2, \pos{I}_2+\pos{B}_{1,2}\}$.
\end{enumerate}

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




\section{Recognitions of the quasi-full trees and forests}
\label{SecRecogTreesForests}
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 $1$s, and the matrix with all entries $0$s. We also use the notation $C_n$ for the matrix $[c_{ij}]$, $1\leq i,j\leq n$, defined as $c_{ij}=1$ for all $i\leq 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\leq i,j\leq n$, with entries $1$s in the main diagonal is called a $\df{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\leq i,j,k\leq n$. For example, for every $n\geq 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.~\cite{Mohammad2020,Mohammad2021,Mohammad2023,Mohammad2024}.
%\def\arraystretch{1.0}
\[
 B_3 =
  \left[{\begin{array}{ccc}
   1 & 1 & 1\\
   0 & 1 & 0\\
   0 & 0 & 1\\
  \end{array}}\right]
\taab\taab B_3^{t} =
  \left[{\begin{array}{ccc}
   1 & 0 & 0\\
   1 & 1 & 0\\
   1 & 0 & 1\\
  \end{array}}\right]
\]
 
 Let $M_n=[a_{ij}]$, $1\leq i,j\leq n$, be a poset matrix. We associate a poset $\pos{A}=\la A,\ls\ra$ with the matrix $M_n$, where the underlying set $A$ = $\{x_1$, $x_2$, $\dots$, $x_n\}$ and $x_i$ corresponds to the $i$-th row (or column) of $M_n$, by defining the order relation $\ls$ on $A$ such that for all $1\leq i,j\leq n$, we have $x_i\ls x_j$ if and only if $a_{ij}=1$. Then we say that the poset matrix $M_n$ \df{represents} the poset $\pos{A}$ and vice versa. Clearly, for every $n\geq 1$, the poset matrices $I_n$ and $C_n$ represent the posets $\pos{I}_n$ and $\pos{C}_n$, respectively. Also, the poset matrices $B_3$ and $B_3^t$, as given above, represent the complete bipartite posets $\pos{B}_{1,2}$ (as shown in Figure~\ref{Fig234ElemQfullRootedTrees}) and $\pos{B}_{2,1}$ (dual of $\pos{B}_{1,2}$), respectively. Let $M_n$ be a poset matrix. For some $1\leq i,j\leq 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 \df{(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} =
  \left[ {\begin{array}{ccc}
   1 & 0 & 0\\
   1 & 1 & 0\\
   1 & 0 & 1\\
  \end{array}}\right]
\tab\xrightarrow{\text{ (1,3)-relabeling }}
 \tab \left[{\begin{array}{ccc}
   1 & 0 & 1\\
   0 & 1 & 1\\
   0 & 0 & 1\\
  \end{array}}\right] = B_3^{\partial}
\]           

 Mohammad and Talukder~\cite{Mohammad2020} 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 $1$s in the main diagonal by a finite number of relabelings. Any two poset matrices $M_n$ and $M'_n$ are called \df{relabeling equivalent}, or briefly \df{equivalent}, if the matrix $M'_n$ can be obtained by some relabeling of the matrix $M_n$ and vice versa. We write $M_n\sim 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 \df{pairwise} equivalent (nonequivalent). Obviously, if $M_n\sim M'_n$ (analogously, $M_n\nsim 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\oplus N_n$ and $M_m\boxplus 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 \df{direct terms} of $M_m\oplus N_n$ and the \df{ordinal terms} of $M_m\boxplus N_n$. Mohammad and Talukder~\cite{Mohammad2020} defined the block of $0$s property and the block of $1$s property in a poset matrix. A poset matrix $M_n=[a_{ij}]$, $1\leq i,j\leq n$, satisfies the \df{block of $0$s property} (analogously, \df{block of $1$s property}) of length $r$, where $1\leq r<n$, if and only if $a_{ij}=0$ (analogously, $a_{ij}=1$) for all $1\leq i\leq r$ and $r+1\leq j\leq n$. For example, for every $n\geq 2$, the poset matrix $I_n$ satisfies the block of $0$s property of lengths $1$, $2$, $\dots$, $n-1$, and the poset matrix $C_n$ satisfies the block of $1$s property of lengths $1$, $2$, $\dots$, $n-1$. Also, the following poset matrix $B_4$ satisfies the block of $1$s property of length $1$, and the poset matrix $F_4$ satisfies the block of $0$s property of length $2$. 
\[
  B_4 =
  \left[{\begin{array}{cccc}
   1 & 1\g & 1\g & 1\g\\
   0 & 1 & 0 & 0\\
   0 & 0 & 1 & 0\\
   0 & 0 & 0 & 1\\
  \end{array}}\right]
\taab\taab F_4 =
  \left[{\begin{array}{cccc}
   1 & 1 & 0\g & 0\g\\
   0 & 1 & 0\g & 0\g\\
   0 & 0 & 1 & 1\\
   0 & 0 & 0 & 1\\
  \end{array}}\right]
\]

 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\boxplus I_3$ and $F_4 = C_2\oplus C_2$. Also, we have $I_n=\underbrace{1\oplus 1\oplus\cdots\oplus1}_{n\text{ terms }}$ and $C_n=\underbrace{1\boxplus 1\boxplus\cdots\boxplus1}_{n\text{ terms }}$. Mohammad and Talukder~\cite{Mohammad2020} obtained the following results regarding the direct sum and ordinal sum of poset matrices.

\begin{theorem}~\cite{Mohammad2020}
\label{TheoBlockZerosOnesSum}
For $n\geq 2$, a poset matrix $M_n$ satisfies the block of $0$s property (analogously, block of $1$s property) of lengths $n_1$, $n_2$, $\dots$, $n_m$ if and only if $M_n = M_{n_1}\oplus M_{n_2-n_1}\oplus\cdots\oplus M_{n-n_m}$ (analogously, $M_n = M_{n_1}\boxplus M_{n_2-n_1}\boxplus\cdots\boxplus M_{n-n_m}$) for some poset matrices $M_{n_1}$, $M_{n_2-n_1}$, $\dots$, $M_{n-n_m}$.
\end{theorem}

\begin{theorem}~\cite{Mohammad2020}
\label{TheoPosetRepresent}
 For $n\geq 2$, let $M_{n_i}$ represent the poset $\pos{P}_i$ for every $1\leq i\leq r$. Then the matrix $M_{n_1}\oplus M_{n_2}\oplus\cdots\oplus M_{n_r}$ (analogously, $M_{n_1}\boxplus M_{n_2}\boxplus\cdots\boxplus M_{n_r}$) is a poset matrix and it represents the poset $\pos{P}_1+\pos{P}_1+\cdots+\pos{P}_r$ (analogously, $\pos{P}_1\oplus\pos{P}_1\oplus\cdots\oplus\pos{P}_r$).
\end{theorem}

 We observe that the poset matrix $B_4$ (as given above) that satisfies the block of $1$s property of length $1$ represents the connected poset $\pos{B}_{1,3}$, and the poset matrix $F_4$ that satisfies the block of $0$s property of length $2$ represents the disconnected poset $\pos{C}_2+\pos{C}_2$. Mohammad et al.~\cite{Mohammad2025PJM} established the above observations in general and obtained the following results regarding the matrix recognitions of the connected posets and disconnected posets.

\begin{theorem}~\cite{Mohammad2025PJM}
\label{TheoConnDisconnPosets}
Let $M$ represent the poset $\pos{P}\ncong \pos{1}$. Then $\pos{P}$ is connected (analogously, disconnected) if $M$ can be relabeled in such a form that it satisfies the block of $1$s property (analogously, block of $0$s property).
\end{theorem}

 In general, the converse of the result obtained for connected posets in Theorem~\ref{TheoConnDisconnPosets} 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 $1$s property for any labeling. However, the following result (Theorem~\ref{TheoRecogRootedTrees}) regarding the recognition of quasi-full rooted trees shows that the converse of the result obtained in Theorem~\ref{TheoConnDisconnPosets} holds in the case of quasi-full rooted trees. We observe that the following matrix $B_4$ satisfies the block of $1$s property of length $1$; and the successive nonunit ordinal term satisfies the block of $0$s 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 $\pos{B}_{1,3}$ (see Figure~\ref{Fig234ElemQfullRootedTrees}). On the other hand, we observe that the following matrix $F_4$ satisfies the block of $0$s property of length $2$; and both the successive direct terms satisfy the block of $1$s 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 $\pos{C}_2+\pos{C}_2$.
\[
  B_4 =
  \left[{\begin{array}{cccc}
   1 & 1\g & 1\g & 1\g\\ 
   0 & 1 & 0\dg & 0\dg\\
   0 & 0 & 1 & 0\dg\\
   0 & 0 & 0 & 1\\
  \end{array}}\right]
\taab\taab F_4 =
  \left[{\begin{array}{cccc}
   1 & 1\dg & 0\g & 0\g\\
   0 & 1 & 0\g & 0\g\\
   0 & 0 & 1 & 1\dg\\
   0 & 0 & 0 & 1\\
  \end{array}}\right]
\]

 We now establish the above observations in general. We give the matrix recognition of the quasi-full rooted trees $\pos{T}\in\mathcal{T}_{n\geq 3,t\geq 2}$ and the matrix recognition of the quasi-full rooted forest $\pos{F}\in\mathcal{F}_{n\geq 2,t\geq 2}$, respectively. Recall that $\mathcal{T}_{n\geq 1,t=1}=\mathcal{F}_{n\geq 1,t=1}=\{\pos{C}_n\}$ and $\mathcal{T}_{n=2,t\geq 1}=\{\pos{C}_2\}$. Note that none of the poset matrices $C_n$, $n\geq 1$, satisfy the block of $0$s property. 

\begin{theorem}
\label{TheoRecogRootedTrees}
 For $n\geq 3$ and $t\geq 2$, let $M_n$ represent the poset $\pos{T}$. Then $\pos{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 $1$s property of length $1$; and every successive nonunit ordinal term $M_r$ satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{h-1}$ for some $l_1<l_2<\cdots<l_{h-1}$, where $h=\min(r,t)$, and every successive nonunit direct term satisfies the block of $1$s property of length $1$.
\end{theorem}

\begin{proof}
Let $\pos{T}$ be a quasi-full $t$-ary rooted tree with $n$ elements, where $2\leq t<n$, and $M_n$ represent $\pos{T}$. Then $\pos{T}$ can be considered as a connected series-parallel poset with a single minimal element known as the root of the tree $\pos{T}$. Then by Theorem~\ref{TheoConnDisconnPosets}, there exists a poset $\pos{P}$ such that $\pos{T}\cong\pos{1}\oplus \pos{P}$. Then $\pos{P}$ is a quasi-full $t$-ary rooted forest consisting of $h-1$ subtrees of $\pos{T}$, where $h=\min(n-1,t)$. Thus there exist the quasi-full $t$-ary rooted trees (possibly, seeds) $\pos{T}_1$, $\pos{T}_2$, $\dots$, $\pos{T}_{h-1}$ such that $\pos{P}$ $\cong$ $\pos{T}_1+\pos{T}_2+\dots+\pos{T}_{h-1}$. Let the poset matrices $M_{r_1}$, $M_{r_2}$, $\dots$, $M_{r_{h-1}}$ represent the trees $\pos{T}_1$, $\pos{T}_2$, $\dots$, $\pos{T}_{h-1}$, respectively. Then by Theorem~\ref{TheoBlockZerosOnesSum} and Theorem~\ref{TheoPosetRepresent}, the poset matrix $M_{r_1}\oplus M_{r_2}\oplus\dots\oplus M_{r_{h-1}}$ represents the forest $\pos{P}$ $\cong$ $\pos{T}_1+\pos{T}_2+\dots+\pos{T}_{h-1}$. This implies that $1\boxplus(M_{r_1}\oplus M_{r_2}\oplus\dots\oplus M_{r_{h-1}})$ represents the tree $\pos{1}\oplus(\pos{T}_1+\pos{T}_2+\dots+\pos{T}_{h-1})$ $\cong$ $\pos{1}\oplus\pos{P}$ $\cong$ $\pos{T}$. This shows that $M_n\sim 1\boxplus(M_{r_1}\oplus M_{r_2}\oplus\dots\oplus M_{r_{h-1}})$. For every $1\leq i\leq h-1$, if $|\pos{T}_i|=1$, that is, $\pos{T}_i\cong\pos{1}$, then we have $M_{r_i}=1$; or if $|\pos{T}_i|=2$, then by definition, we have $\pos{T}_i\cong\pos{C}_2$, and then $M_{r_i}=C_2$. Otherwise, for $|\pos{T}_i|\geq 3$, we must have $\pos{T}_{i_j}$ and $M_{r_{i_j}}$, $1\leq j\leq h_i-1$, such that $\pos{T}_i$ $\cong$ $\pos{1}\oplus(\pos{T}_{i_1}+\pos{T}_{i_2}+\dots+\pos{T}_{i_{h_i-1}})$ and $M_{r_i}\sim 1\boxplus(M_{r_{i_1}}\oplus M_{r_{i_2}}\oplus\dots\oplus 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 $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{h-1}$ for some $l_1<l_2<\cdots<l_{h-1}$, where $h=\min(r_i,t)$, and every successive nonunit direct term satisfies the block of $1$s 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 $1$s property of length $1$. Thus there exists a poset matrix $Q_{n-1}$ such that $M_n=1\boxplus Q_{n-1}$. Since the ordinal term $Q_{n-1}$ is nonunit, it must satisfy the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{k-1}$ for some $l_1<l_2<\cdots<l_{k-1}$. Assign $r_i=l_i-l_{i-1}$, $1\leq i\leq k$, where we assume $l_0=0$ and $l_k=n-1$. Then by Theorem~\ref{TheoBlockZerosOnesSum}, there exist $Q_{r_i}$, $1\leq i\leq k$, such that $Q_{n-1}=Q_{r_1}\oplus Q_{r_2}\oplus\dots\oplus Q_{r_k}$. This gives $M_n=1\boxplus (Q_{r_1}\oplus Q_{r_2}\oplus\dots\oplus Q_{r_k})$. If $r_i\leq 2$ for every $1\leq i\leq k$, then by Theorem~\ref{TheoPosetRepresent}, $Q_{r_i}\sim C_{r_i}$ implies that $M_n$ represents the poset $\pos{1}\oplus (\pos{C}_{r_1}+\pos{C}_{r_2}+\cdots +\pos{C}_{r_k})$ that is a quasi-full rooted tree. If $r_i\geq 3$ for some $1\leq i\leq k$, then there exist $Q_{r_{i_j}}$, $1\leq j\leq k_i$, such that $Q_{r_i}=1\boxplus(Q_{r_{i_1}}\oplus Q_{r_{i_2}}\oplus\dots\oplus Q_{r_{i_{k_i}}})$. Continuing the above process, we can show that $r_{i_j}\leq 2$ for every $1\leq i\leq k_i$ at some step $i$ such that $Q_{r_i}$ represents the poset $\pos{1}\oplus (\pos{C}_{r_{i_1}}+\pos{C}_{r_{i_2}}+\cdots +\pos{C}_{r_{k_i}})$. Therefore, $M_n=1\boxplus (Q_{r_1}\oplus Q_{r_2}\oplus\dots\oplus Q_{r_k})$ represents a quasi-full rooted tree. 
\end{proof}

\begin{theorem}
\label{TheoRecogRootedForests}
 For $n\geq 2$ and $t\geq 2$, let $M_n$ represent the poset $\pos{F}$. Then $\pos{F}$ is a quasi-full $t$-ary rooted forest if and only if $M_n$ can be relabeled in such a form that it satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ for some $l_1<l_2<\cdots<l_{t-1}$; and every successive nonunit direct term satisfies the block of $1$s property of length $1$, and every successive nonunit ordinal term $M_r$ satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{h-1}$ for some $l_1<l_2<\cdots<l_{h-1}$, where $h=\min(r,t)$.
\end{theorem}

\begin{proof}
Let $\pos{F}$ be a quasi-full $t$-ary rooted tree with $n$ elements, where $2\leq t\leq n$, and $M_n$ represent $\pos{F}$. Then there exist the quasi-full $t$-ary rooted trees (possibly, seeds) $\pos{T}_1$, $\pos{T}_2$, $\dots$, $\pos{T}_t$ such that $\pos{F}$ $\cong$ $\pos{T}_1+\pos{T}_2+\dots+\pos{T}_t$. Let the poset matrices $M_{r_1}$, $M_{r_2}$, $\dots$, $M_{r_t}$ represent the trees $\pos{T}_1$, $\pos{T}_2$, $\dots$, $\pos{T}_t$, respectively. Then by Theorem~\ref{TheoBlockZerosOnesSum} and Theorem~\ref{TheoPosetRepresent}, $M_{r_1}\oplus M_{r_2}\oplus\dots\oplus M_{r_t}$ represents the forest $\pos{F}$ $\cong$ $\pos{T}_1+\pos{T}_2+\dots+\pos{T}_t$. This shows that $M_n\sim M_{r_1}\oplus M_{r_2}\oplus\dots\oplus M_{r_t}$. For every $1\leq i\leq t$, since $M_{r_i}$ represents the quasi-full rooted tree $\pos{T}_i$, by Theorem~\ref{TheoRecogRootedTrees}, $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 $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ for some $l_1<l_2<\cdots<l_{t-1}$. Assign $r_i=l_i-l_{i-1}$, $1\leq i\leq t$, where we assume $l_0=0$ and $l_t=n-1$. Then by Theorem~\ref{TheoBlockZerosOnesSum}, there exist $Q_{r_i}$, $1\leq i\leq t$, such that $M_n=Q_{r_1}\oplus Q_{r_2}\oplus\dots\oplus Q_{r_t}$. For every $1\leq i\leq t$, since $Q_{r_i}$ satisfies the conditions for successive nonunit direct terms and ordinal terms given in the hypothesis, by Theorem~\ref{TheoRecogRootedTrees}, matrix $Q_{r_i}$ represents a quasi-full rooted tree, say $\pos{T}_i$. Then by Theorem~\ref{TheoPosetRepresent}, matrix $M_n=Q_{r_1}\oplus Q_{r_2}\oplus\dots\oplus Q_{r_t}$ represents the forest $\pos{T}_1+\pos{T}_2+\dots+\pos{T}_t$. Since $M_n$ represents $\pos{F}$, we have $\pos{F}\cong\pos{T}_1+\pos{T}_2+\dots+\pos{T}_t$, and hence $\pos{F}$ is a quasi-full rooted forest. 
\end{proof}




\section{Exact enumeration of the quasi-full trees}
\label{SecEnumerQuasiFullRootedTrees}
The enumeration method for the unlabeled quasi-full rooted trees obtained in this section is based mainly on the results (Theorem~\ref{TheoRecogRootedTrees} and Theorem~\ref{TheoRecogRootedForests}) obtained in Section~\ref{SecRecogTreesForests}. Let $\mathcal{M}_{n,t}$, where $n\geq 1$ and $t\geq 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 $\mathcal{M}_{1,t\geq 1}=\{1\}$, $\mathcal{M}_{2,t\geq 1}=\{C_2\}$, and $\mathcal{M}_{n\geq 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 $\mathcal{M}_{n,t}$ for every $2\leq t<n$.
 
 Let $M\in\mathcal{M}_{n,t}$ for some $n\geq 3$ and $t\geq 2$. By Theorem~\ref{TheoRecogRootedTrees}, matrix $M$ satisfies the block of $1$s property of length $1$; and every successive ordinal term of order $r$, where $1<r<n$, satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{h-1}$ for some $l_1<l_2<\cdots<l_{h-1}$, where $h=\min(r,t)$, and every successive nonunit direct term satisfies the block of $1$s property of length $1$. In particular, we have $\mathcal{M}_{n,t}$ as follows:

\begin{enumerate}
\item Let $M\in\mathcal{M}_{3,2}$. Then $M$ satisfies the block of $1$s property of length $1$, and the nonunit ordinal term (a matrix of order $3-1=2$) can satisfy the block of $0$s property of length $1$ only. Thus, both the direct terms are $1$. Then $M=1\boxplus (1\oplus 1)= 1\boxplus I_2= B_3$ (as given in Section~\ref{SecRecogTreesForests}), and hence $\mathcal{M}_{3,2}=\{B_3\}$. In general, since $h=\min(3-1,t)=2$, we have $B_3\in\mathcal{M}_{3,t}$ for every $t\geq 2$. Therefore, $\mathcal{M}_{3,t\geq 2}=\{B_3\}$.
\item Let $M\in\mathcal{M}_{4,2}$. Then $M$ satisfies the block of $1$s property of length $1$; and the nonunit ordinal term can satisfy the block of $0$s 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\oplus C_2\sim C_2\oplus 1$, we have $M=1\boxplus(1\oplus C_2)$, and hence $\mathcal{M}_{4,2}=\{1\boxplus(1\oplus C_2)\}$. 
\item Let $M\in\mathcal{M}_{4,3}$. Then $M$ satisfies the block of $1$s property of length $1$; and the nonunit ordinal term (a matrix of order $4-1=3$) can satisfy the block of $0$s property of lengths $1,2$. Thus, all the direct terms are $1$. Then $M=1\boxplus(1\oplus 1\oplus 1)=1\boxplus I_3=B_4$ (as given in Section~\ref{SecRecogTreesForests}) and hence $\mathcal{M}_{4,3}=\{B_4\}$. In general, if $t\geq 3$, then $h=\min(4-1,t)=3$ implies that $B_4\in\mathcal{M}_{3,t}$ for every $t\geq 3$. Therefore, $\mathcal{M}_{4,t\geq 3}=\{B_4\}$.
\end{enumerate}  

We now have the following remarks.

\begin{remark}
\label{RemC3forAllt2}
 We have $\mathcal{M}_{1,1}=\{1\}$, $\mathcal{M}_{2,1}=\{C_2\}$, and $\mathcal{M}_{n\geq 3,1}=\{C_n\}$ in general. Also, for every $t\geq 1$, we have $1\in\mathcal{M}_{1,t}$ and $C_2\in\mathcal{M}_{2,t}$. On the other hand, for $t\geq 2$, we see that $C_n\notin\mathcal{M}_{n,t}$ for any $n\geq 3$. These happen because in each of these cases, the nonunit ordinal term $C_{n-1}$ does not satisfy the block of $0$s property for any length. But by Theorem~\ref{TheoRecogRootedTrees}, since $h=\min(n-1,t)\geq 2$, the nonunit ordinal term $C_{n-1}$ must satisfy the block of $0$s property of lengths $l_1,l_2,\dots, l_{h-1}$ for some $l_1<l_2<\cdots<l_{h-1}$. 
\end{remark}

\begin{remark}
\label{RemM4forAllt2}
 We have $\mathcal{M}_{3,2}=\{B_3\}$, $\mathcal{M}_{4,2}=\{1\boxplus(1\oplus C_2)\}$, and $\mathcal{M}_{4,3}=\{B_4\}$. Also, for every $t\geq 2$, we have $B_3\in\mathcal{M}_{3,t}$ and $B_4\in\mathcal{M}_{4,t}$. On the other hand, for every $t\geq 3$, we see that $1\boxplus(1\oplus C_2)\notin\mathcal{M}_{4,t}$ . These happen because in each of these cases, the nonunit ordinal term $1\oplus C_2$ can satisfy the block of $0$s property of length $1$ only. But by Theorem~\ref{TheoRecogRootedTrees}, since $h=\min(3,t)=3$, the ordinal term $1\oplus C_2$ must satisfy the block of $0$s property of lengths $l_1,l_2$ for some $l_1<l_2$.
\end{remark}

In the following, we generalize the facts observed in Remark~\ref{RemC3forAllt2} and Remark~\ref{RemM4forAllt2}.
\begin{theorem}
\label{TheoObservRemM4RemC3}
 Let $M$ be a poset matrix and $n\geq 3$ be given. Then
\begin{enumerate} 
 \item[(i)] $M\in\mathcal{M}_{n,n-1}$ implies $M\in\mathcal{M}_{n,t\geq n}$, and
 \item[(ii)] $M\in\mathcal{M}_{n,t}$ for some $t\leq n-2$ implies $M\notin\mathcal{M}_{n,t\geq n}$.
\end{enumerate}
\end{theorem}

\begin{proof}
\leavevmode
\begin{enumerate}
\item[(i)] Let $M\in\mathcal{M}_{n,n-1}$. Since $M$ satisfies the block of $1$s 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 $0$s property of lengths $1,2,\dots,n-2$. Since $\min(n-1,t)-1=n-2$ for all $t\geq n$, by Theorem~\ref{TheoRecogRootedTrees}, we have $M\in\mathcal{M}_{n,t\geq n}$. 
\item[(ii)] Let $M\in\mathcal{M}_{n,t}$ for some $t\leq n-2$. Then, since $M$ satisfies the block of $1$s 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 $0$s property of lengths $l_1,l_2,\dots,l_{k}$ for some $l_1<l_2<\cdots<l_{k}$, where $k=t-1\leq n-3$. But, for all $t\geq n$, we have $k=\min(n-1,t)-1 = n-2>n-3$. Therefore, by Theorem~\ref{TheoRecogRootedTrees}, we have $M\notin\mathcal{M}_{n,t\geq n}$.
\end{enumerate} 
\end{proof}

As an illustration of the result obtained in Theorem~\ref{TheoObservRemM4RemC3}, we present the poset matrices $M\in\mathcal{M}_{n,t}$ for all $1\leq n\leq 6$ and $1\leq t\leq 5$ in Table~\ref{TabMntRepreQfullRootedTrees}.
\begin{table}[H]
\centering 
%\def\arraystretch{1.2}
%\resizebox{\columnwidth}{!}{
\begin{tabular}{| c | c | c | c | c | c | c |} 
\hline
$t~\diagdown$ $n$ & 1 & 2 & 3 & 4 & 5 & 6\\
\hline\hline
1 & \multirow{7}{0.5 em}{$1$} & \multirow{7}{1.2 em}{$C_2$} & $C_3$ & $C_4$ & $C_5$ & $C_6$\\
\cline{1-1}\cline{4-7} 
2 &  &  & \multirow{5}{1.2 em}{$B_3$} & $1\boxplus(1\oplus C_2)$ & $\begin{array}{c} 1\boxplus(1\oplus B_3),\\1\boxplus(C_2\oplus C_2)\end{array}$ & $\begin{array}{c} 1\boxplus(C_2\oplus B_3),\\ 1\boxplus(1\oplus(1\boxplus(1\oplus C_2)))\end{array}$\\
\cline{1-1}\cline{5-7}  
3 &  &  &  & \multirow{3}{1.2 em}{$B_4$} & $1\boxplus(I_2\oplus C_2)$ & $\begin{array}{c} 1\boxplus(I_2\oplus B_3),\\1\boxplus(1\oplus C_2\oplus C_2)\end{array}$\\
\cline{1-1}\cline{6-7}  
4 &  &  &  &  & \multirow{2}{2.3 em}{$1\boxplus I_4$} & $1\boxplus(I_3\oplus C_2)$\\
\cline{1-1}\cline{7-7} 
5 &  &  &  &  &  & $1\boxplus I_5$\\ 
\hline
\end{tabular}
% }
\caption{Poset matrices in $\mathcal{M}_{n,t}$ for all $1\leq n\leq 6$ and $1\leq t\leq 5$.}
\label{TabMntRepreQfullRootedTrees}
\end{table}

 Let $\mathcal{N}_{n,t}$, $2\leq t\leq n$, be the collections of pairwise nonequivalent (relabeling) poset matrices that represent a quasi-full $t$-ary rooted forest with $n$ elements. For $n\geq 2$, the result obtained in Theorem~\ref{TheoRecogRootedForests} implies that every matrix $M_n\in \mathcal{N}_{n,t}$ satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ for some $l_1<l_2<\cdots<l_{t-1}$; and every successive direct term until $1$ satisfies the block of $1$s property of length $1$, and every successive ordinal term $M_r\neq 1$ satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{h-1}$ for some $l_1<l_2<\cdots<l_{h-1}$, where $h=\min(r-1,t)$. We apply this characterization of rooted forests to construct the matrices in $\mathcal{M}_{n+1,t}$ for every $2\leq t\leq n$, using the matrices in $\mathcal{N}_{n,t}$. For example, let $M \in \mathcal{N}_{2,2}$. Here, $M$ satisfies the block of $0$s property of length $1$ only, so both direct terms are $1$. Thus, $M = 1 \oplus 1 = I_2$, and hence $\mathcal{N}_{2,2} = \{I_2\}$. Again, take $M \in \mathcal{N}_{3,3}$. In this case, $M$ satisfies the block of $0$s property for lengths $1,2$, so all direct terms are $1$. Therefore, $M = 1 \oplus 1 \oplus 1 = I_3$, and hence $\mathcal{N}_{3,3} = \{I_3\}$. In general, we have $\mathcal{N}_{n\geq 2, t=n} = \{I_n\}$. For some $2 \leq t < n$, we observe the contents of $\mathcal{N}_{n,t}$ as follows:    
\begin{enumerate}
\item Let $M\in\mathcal{N}_{3,2}$. Then $M$ can satisfy the block of $0$s property of length $1$ and length $2$. In both cases, the direct terms are $1$ and $C_2$. Since $1\oplus C_2\sim C_2\oplus 1$, in this case, we have $M=1\oplus C_2$. Thus, $\mathcal{N}_{3,2}=\{1\oplus C_2\}$. Again, let $M\in\mathcal{N}_{4,3}$. Then $M$ can satisfy the block of $0$s 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\oplus 1\oplus 1$ $\sim$ $1\oplus C_2\oplus 1$ $\sim$ $1\oplus 1\oplus C_2$ = $I_2\oplus C_2$, in this case, we have $M=I_2\oplus C_2$. Thus, $\mathcal{N}_{4,3}=\{I_2\oplus C_2\}$. 
\item Let $M\in\mathcal{N}_{4,2}$. Then $M$ can satisfy the block of $0$s 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\oplus B_3\sim B_3\oplus 1$, in this case, $M=1\oplus B_3$ or $M=C_2\oplus C_2$. Thus, $\mathcal{N}_{4,2}=\{1\oplus B_3, C_2\oplus C_2\}$.
\end{enumerate}  

 We now generalize the above observations. We recall the nonisomorphic direct sum criterion for poset matrices obtained by Mohammad et al.~\cite{Mohammad2025PJM}. Here, we justify when a pair of poset matrices, each of which satisfies the block of $0$s property of some lengths, are nonequivalent. Let $M, M'\in\mathcal{N}_{n,t}$, where $2\leq t\leq n$, such that both $M$ and $M'$ satisfy the block of $0$s property. The poset matrix $M$ satisfies the block of $0$s property of lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ for some $l_1<l_2<\cdots<l_{t-1}$, and matrix $M'$ satisfies the block of $0$s property of lengths $l'_1$, $l'_2$, $\dots$, $l'_{t-1}$ for some $l'_1<l'_2<\cdots<l'_{t-1}$. Since the direct sum of poset matrices is commutative, it is possible that $M\sim M'$ (relabeling equivalent) even if $l_k \neq l'_k$ for all $1\leq k\leq t-1$. Recall that if $M\sim 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.~\cite{Mohammad2025PJM} regarding the nonisomorphic direct sum of the poset matrices representing disconnected series-parallel posets gives the condition for the lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ and $l'_1$, $l'_2$, $\dots$, $l'_{t-1}$ of the block of $0$s property satisfied by the matrices $M$ and $M'$ so that the matrices $M$ and $M'$ represent nonisomorphic forests.   
 
\begin{theorem}~\cite{Mohammad2025PJM}
\label{TheoDirectSumCriteria}
 Let $M, M'\in\mathcal{N}_{n,t}$, $n\geq 2$, such that both $M$ and $M'$ satisfy the block of $0$s property of the nondecreasing inter-distant lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ and lengths $l'_1$, $l'_2$, $\dots$, $l'_{t-1}$, respectively, where $l_k \neq l'_k$ for some $1\leq k\leq t-1$; and every direct term of $M$ and $M'$ satisfies the block of $1$s property for some lengths. Then $M$ and $M'$ are relabeling inequivalent, that is, $M\nsim M'$.
\end{theorem}

\begin{proof}
Let $l$: $l_1$, $l_2$, $\dots$, $l_{t-1}$ and $l'$: $l'_1$, $l'_2$, $\dots$, $l'_{t-1}$. For all $0\leq i\leq 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 $0$s property of the lengths $l$ and $l'$, respectively, by Theorem~\ref{TheoBlockZerosOnesSum}, there exist $M_{r_i}$, $M'_{r'_i}$, $1\leq i\leq t$, such that $M=M_{r_1}\oplus M_{r_2}\oplus\cdots\oplus M_{r_t}$ and $M'=M'_{r'_1}\oplus M'_{r'_2}\oplus\cdots\oplus M'_{r'_t}$. Suppose that there exists $1\leq k_0\leq t-1$ such that $l_{k_0} \neq l'_{k_0}$. This implies $r_{k_0}\neq r'_{k_0}$ and hence $M_{r_{k_0}}\neq M'_{r'_{k_0}}$. Since the lengths $l$ and $l'$ are nondecreasing inter-distant, both the sequences $r_i$, $r'_i$, $1\leq i\leq t$, are nondecreasing. This implies either $M_{r_{k_0}}\neq M'_{r'_i}$ for all $k_0<i\leq t$ or $M'_{r'_{k_0}}\neq M_{r_i}$ for all $k_0<i\leq t$. Since for all $1\leq i\leq t$, the direct terms $M_{r_i}$ and $M'_{r'_i}$ satisfy the block of $1$s property for some lengths, we have $M_{r_{k_0}}\oplus\cdots\oplus M_{r_t}$ $\nsim$ $M'_{r'_{k_0}}\oplus\cdots\oplus M'_{r'_t}$. This implies $M_{r_1}\oplus M_{r_2}\oplus\cdots\oplus M_{r_t}\nsim M'_{r'_1}\oplus M'_{r'_2}\oplus\cdots\oplus M'_{r'_t}$, that is, $M\nsim M'$. 
\end{proof}

As an illustration of the result obtained in Theorem~\ref{TheoDirectSumCriteria}, the poset matrices $M\in\mathcal{N}_{n,t}$ for all $2\leq t\leq n\leq 5$ are presented in Table~\ref{TabNntRepreQfullRootedForests}. The following observations show that every $M\in\mathcal{N}_{n,t}$ can be constructed uniquely by taking the direct sum of $t$ matrices taken from the collections $\mathcal{M}_{r,t}$, $1\leq r\leq n-t+1$, given in Table~\ref{TabMntRepreQfullRootedTrees}.
\begin{table}[H]
\centering 
%\def\arraystretch{1.2}
%\resizebox{\columnwidth}{!}{
\begin{tabular}{| c | c | c | c | c |}
\hline
$t~\diagdown$ $n$ &2  &3  &4  &5\\ 
\hline\hline 
2  &$~I_2~$ & $~1\oplus C_2~$  & $~C_2\oplus C_2, ~1\oplus B_3~$ & $~C_2\oplus B_3, ~1\oplus(1\boxplus(1\oplus C_2))~$\\ 
\hline 
3  &  &~$I_3$~ & $I_2\oplus C_2$  & $1\oplus C_2\oplus C_2, ~I_2\oplus B_3$\\ 
\hline 
4  &  &  & $I_4$ & $I_3\oplus C_2$\\ 
\hline 
5  &  &  &  & $I_5$\\ 
\hline 
\end{tabular}
%}
\caption{Poset matrices in $\mathcal{N}_{n,t}$ for all $2\leq t\leq n\leq 5$.}
\label{TabNntRepreQfullRootedForests}
\end{table}

\begin{enumerate}
\item To construct the matrices in $\mathcal{N}_{2,2}=\{I_2=1\oplus 1\}$, $\mathcal{N}_{3,3}=\{I_3=1\oplus 1\oplus 1\}$, $\mathcal{N}_{4,4}=\{I_4=1\oplus 1\oplus 1\oplus 1\}$, and so on; we need only the unit matrix in $ \mathcal{M}_{1,t\geq 2}=\{1\}$. 
\item To construct the matrices in $\mathcal{N}_{3,2}=\{1\oplus C_2\}$, $\mathcal{N}_{4,3}=\{I_2\oplus C_2\}$, $\mathcal{N}_{5,4}=\{I_3\oplus C_2\}$, and so on; we need only the matrices in the collections $\mathcal{M}_{1,t\geq 2}=\{1\}$ and $\mathcal{M}_{2,t\geq 2}=\{C_2\}$. 
\item To construct the matrices in $\mathcal{N}_{4,2}=\{1\oplus B_3, C_2\oplus C_2\}$, $\mathcal{N}_{5,3}=\{I_2\oplus B_3, 1\oplus C_2\oplus C_2\}=\{1\oplus 1\oplus B_3, 1\oplus C_2\oplus C_2\}$, and so on; we need only the matrices in the collections $\mathcal{M}_{1,t\geq 2}=\{1\}$, $\mathcal{M}_{2,t\geq 2}=\{C_2\}$, and $\mathcal{M}_{3,t\geq 2}=\{B_3\}$.
\item To construct the matrices in $\mathcal{N}_{5,2}=\{1\oplus (1\boxplus(1\oplus C_2)), C_2\oplus B_3\}$, and so on; we need only the matrices in the collections $\mathcal{M}_{1,t\geq 2}=\{1\}$, $\mathcal{M}_{2,t\geq 2}=\{C_2\}$, $\mathcal{M}_{3,t\geq 2}=\{B_3\}$, $\mathcal{M}_{4,2}=\{1\boxplus(1\oplus C_2)\}$, and $\mathcal{M}_{4,t\geq 3}=\{1\boxplus I_3\}$.
\end{enumerate} 

 Suppose, for given $n$ and $t$, where $2\leq t\leq n$, we want to enumerate the matrices in $\mathcal{M}_{n+1,t}$. Also, let $\mathcal{M}_{r,t}$ be given for all $1\leq r\leq n-t+1$. For $t\geq 2$, to construct the matrices in $\mathcal{M}_{n+1,t}$, we first construct the matrices in $\mathcal{N}_{n,t}$ by using the matrices in $\mathcal{M}_{r,t}$, $1\leq r\leq n-t+1$. Here, we apply the direct sum criterion for poset matrices obtained in Theorem~\ref{TheoDirectSumCriteria}. For every $M\in\mathcal{N}_{n,t}$, by Theorem~\ref{TheoRecogRootedTrees} and Theorem~\ref{TheoRecogRootedForests}, the ordinal sum $1\boxplus M$ satisfies the condition for being a member of $\mathcal{M}_{n+1,t}$, that is, $1\boxplus M\in\mathcal{M}_{n+1,t}$. Also, for every $P\in\mathcal{M}_{n+1,t}$, there exists $M'\in\mathcal{N}_{n,t}$ such that $P=1\boxplus M'$. Thus, there is a one-to-one correspondence between $\mathcal{M}_{n+1,t}$ and $\mathcal{N}_{n,t}$, and hence $|\mathcal{M}_{n+1,t}|$ = $|\mathcal{N}_{n,t}|$. Therefore, the enumeration of $\mathcal{M}_{n+1,t}$ is equivalent to the enumeration of $\mathcal{N}_{n,t}$. Suppose we want to determine $|\mathcal{N}_{n,t}|$ for some $2\leq t\leq n$. Then, by Theorem~\ref{TheoDirectSumCriteria}, it is enough to determine the number of ways in which a poset matrix $M_n$ can satisfy the block of $0$s property of the nondecreasing inter-distant lengths $l_1$, $l_2$, $\dots$, $l_{t-1}$ for some $l_1<l_2<\cdots<l_{t-1}$, such that the direct terms $M_{l_1}$, $M_{l_2-l_1}$, $\dots$, $M_{n-l_{t-1}}$ belong to some $\mathcal{M}_{r,t}$, $1\leq r\leq n-t+1$. We now obtain this result as a special case of the result \cite[Theorem 4.3]{Mohammad2025PJM}.
  
\begin{theorem}
\label{TheoEnumQfullRootedForests}
Let $2\leq t\leq n$ be given, and let every $M_n\in\mathcal{N}_{n,t}$ satisfy the block of $0$s property of the nondecreasing inter-distant lengths $l_{j1}, l_{j2},\dots,l_{j(t-1)}$, $1\leq j\leq p$, for some $p\leq\binom{n}{t}$. Also let for every $1\leq j\leq p$ and $1\leq k\leq q_j$, where $q_j\leq t$, we have $|\mathcal{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\leq h\leq t-1$ with $l_{j0}=0$ and $l_{jt}=n$. Then we have $|\mathcal{N}_{n,t}|$ as follows:
\begin{equation}\label{EquEnumQfullRootedForests}
 |\mathcal{N}_{n,t}|=\sum_{j=1}^{p}\prod_{k=1}^{q_j}\binom{|\mathcal{M}_{r_{jk},t}|+c_{jk}}{1+c_{jk}},\tb 2\leq t\leq n. 
\end{equation}
\end{theorem}

\begin{proof}
For every $1\leq j\leq p$, where $p\leq\binom{n}{t}$, let $S_j$ be the number of different ways in which an $M_n\in\mathcal{N}_{n,t}$ can satisfy the block of $0$s property of the nondecreasing inter-distant lengths $l_{j1}, l_{j2},\dots,l_{j(t-1)}$ such that the direct terms $M_{r_{jk}}$ of $M_n$ belong to $\mathcal{M}_{r_{jk},t}$. Then for every $1\leq j\leq p$, there are $S_j$ pairwise nonequivalent poset matrices $M_n$ in $\mathcal{N}_{n,t}$ that satisfy the $j$-th nondecreasing inter-distant lengths $l_{j1}, l_{j2},\dots,l_{j(t-1)}$. Then we have $r_{jk}$, $c_{jk}$, $1\leq k\leq q_j$, where $q_j\leq t$, as follows:
\begin{align*} 
 r_{j1} &= l_{ji}-l_{j(i-1)}, ~1\leq i\leq t_{j1}+1,\\
 r_{j2} &= l_{ji}-l_{j(i-1)}, ~t_{j1}+2\leq i\leq t_{j2}+1,\\
        & ~\vdots\\
 r_{jq_j} &= l_{ji}-l_{j(i-1)}, ~t_{j(q_{j}-1)}+2\leq i\leq t_{jq_j}+1.
\end{align*}
Here $r_{j1}<r_{j2}<\cdots<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\leq i\leq t_{jk}+1$, $1\leq k\leq q_j$. By hypothesis, for every $1\leq i\leq t_{jk}+1$ and $1\leq k\leq q_j$, matrix $M_{r_{jk}}\in\mathcal{M}_{r_{jk},t}$. For every $1\leq j\leq p$ and $1\leq k\leq q_j$, since $M_{r_{jk}}$ belong to $\mathcal{M}_{r_{jk},t}$, by \cite[Theorem 3.8]{Mohammad2025PJM}, the number of distinct poset matrices $M_n\in\mathcal{N}_{n,t}$ that satisfy the $j$-th nondecreasing inter-distant lengths $l_{j1}$, $l_{j2}$, $\dots$, $l_{j(t-1)}$ is
\[\binom{|\mathcal{M}_{r_{jk},t}|+c_{jk}}{1+c_{jk}}.\]
Since the lengths $r_{jk}$, $1\leq k\leq q_j$, are all strictly increasing, by \cite[Theorem 3.7]{Mohammad2025PJM}, we have $S_j$ as follows:
\begin{equation}
\label{EquSjSumforEnumForests}
 S_j=\prod_{k=1}^{q_j}\binom{|\mathcal{M}_{r_{jk},t}|+c_{jk}}{1+c_{jk}}.
\end{equation}
Since the equation \eqref{EquSjSumforEnumForests} holds for all nondecreasing inter-distant lengths $l_{j1}$, $l_{j2}$, $\dots$, $l_{j(t-1)}$, $1\leq j\leq p$, by Theorem~\ref{TheoDirectSumCriteria}, we have $|\mathcal{N}_{n,t}|$ as follows:
\begin{equation*}
   |\mathcal{N}_{n,t}|=\sum_{j=1}^{p}S_j=\sum_{j=1}^{p}\prod_{k=1}^{q_j}\binom{|\mathcal{M}_{r_{jk},t}|+c_{jk}}{1+c_{jk}},\tb 2\leq t\leq n. 
\end{equation*}
\end{proof}

The following examples illustrate the result obtained in Theorem~\ref{TheoEnumQfullRootedForests}.
\begin{example}
To determine the number $|\mathcal{M}_{9,2}|$, we determine the number $|\mathcal{N}_{8,2}|$ by using the numbers $|\mathcal{M}_{r,2}|$ for all $1\leq r\leq 7$.
\begin{center}
\def\arraystretch{1.2}
\begin{tabular}{r c c c c c c c c c c c c c c c c}
\hline
  $r:$&   &1&   &2&   &3&   &4&   &5&   &6&   &7&\\
\hline
  $|\mathcal{M}_{r,2}|:$&   &1&   &1&   &1&   &1&   &2&   &2&   &4&\\
\hline
\end{tabular}
\end{center}
\begin{center}
\def\arraystretch{1.5}
\begin{tabular}{c  c  c  c  c  c  r}
$j$& \tab &$l_{j1},\dots,l_{j(t-1)}$& \tab &$r_{j1},\dots,r_{jq_j}$&  &$S_j$\\
\hline
$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$\\
\hline
   &   &   &   &   & \taab & Total: $9$\\
\end{tabular}
\end{center}
Therefore, $|\mathcal{M}_{9,2}|=|\mathcal{N}_{8,2}|=9$.
\end{example}

\begin{example}
To determine the number $|\mathcal{M}_{10,3}|$, we determine the number $|\mathcal{N}_{9,3}|$ by using the numbers $|\mathcal{M}_{r,3}|$ for all $1\leq r\leq 7$.
\begin{center}
\def\arraystretch{1.2}
\begin{tabular}{r c c c c c c c c c c c c c c c c c c}
\hline
  $r:$&   &1&   &2&   &3&   &4&   &5&   &6&   &7&\\
\hline
  $|\mathcal{M}_{r,3}|:$&  &1&   &1&   &1&   &1&   &1&   &2&   &3&\\
\hline
\end{tabular}
\end{center}
\begin{center}
\def\arraystretch{1.5}
\begin{tabular}{c  c  c  c  c  c  r}
$j$& \tab &$l_{j1},\dots,l_{j(t-1)}$& \tab &$r_{j1},\dots,r_{jq_j}$&  &$S_j$\\
\hline
$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$\\
\hline
   &   &   &   &   & \taab & Total: $10$\\
\end{tabular}
\end{center}
Therefore, $|\mathcal{M}_{10,3}|=|\mathcal{N}_{9,3}|=10$.
\end{example} 
 
\section{Enumeration algorithm}
\label{SecEnumAlgorithm}
Recall that the numbers $p$ and $q_j$, $1\leq j\leq p$, in equation \eqref{EquEnumQfullRootedForests} are not specified explicitly. For given $2\leq t\leq n$, the computation of $p$ and $q_j$ depends on the constructions of the nondecreasing inter-distant lengths $l_{j1}, l_{j2},\dots,l_{j(t-1)}$ and the quantities $r_{j1}, r_{j2},\dots, r_{jt}$ for every $1\leq j\leq p$. We use Algorithm~\ref{AlgorEnumerQfullRootedTrees} to determine the numbers $p$ and $q_j$, $1\leq j\leq p$, and to compute finally $|\mathcal{M}_{n+1,t}|=|\mathcal{N}_{n,t}|$, the number of $(n+1)$-element unlabeled quasi-full $t$-ary rooted trees for given $n$ and $t$, where $2\leq t\leq n$.
 
\begin{algorithm}
To compute $Count = |\mathcal{M}_{n+1,t}|$ for given $n$ and $t$, where $2\leq t\leq n$. \hfill
\label{AlgorEnumerQfullRootedTrees}
\centering
\begin{enumerate}
\item[(1)] Initialize $Count=0$.
\item[(2)] Repeat (a) to (d) for every nondecreasing inter-distant length (there are $p$ such distinct lengths; see equation \eqref{EquEnumQfullRootedForests}) as constructed in (b).
  \begin{enumerate}
    \item[(a)] Initialize $S_j=1$.
    \item[(b)] Construct the $j$-th nondecreasing inter-distant lengths $l_{j1}, l_{j2},\dots,l_{j(t-1)}$ (there are $t-1$ integers $l_{j1}\leq l_{j2}\leq\dots\leq l_{j(t-1)}$) chosen from $1, 2, \dots, n-1$.
    \item[(c)] Compute the $j$-th quantities $r_{j1}, r_{j2},\dots, r_{jt}$ by taking the differences of the consecutive lengths $l_{j1}, l_{j2},\dots,l_{j(t-1)}$, and repeat (i) and (ii) for every distinct collection (there are $q_j$ collections in total; see equations \eqref{EquEnumQfullRootedForests} and \eqref{EquSjSumforEnumForests}) of the quantities $r_{j1}, r_{j2},\dots, r_{jt}$.
     \begin{enumerate}
       \item[(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},\dots, r_{jt}$.
       \item[(ii)] Update $S_j$ with $S_j\times\binom{|\mathcal{M}_{r_{jk}}|+c_{jk}}{1+c_{jk}}$.
    \end{enumerate}
    \item[(d)] Increase $Count$ by $S_j$.
 \end{enumerate}
\item[(3)] Return $Count$.
\end{enumerate}
\end{algorithm}

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

\begin{lemma}
 Algorithm~\ref{AlgorEnumerQfullRootedTrees} runs in time $\mathcal{O}(n^{4})$.
\end{lemma}
\begin{proof}
 The constructions of the sequences $l_{j1}, l_{j2},\dots,l_{j(t-1)}$ at step (b) have complexity equal to $(t-1)(n-1)$. Since $t\leq n$, we have $(t-1)(n-1)\approx\mathcal{O}((n-1)(n-1))\approx\mathcal{O}(n^2)$. Again, since $1\leq c_{jk}, q_{j}\leq 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\leq n$ implies that the repetitions at the step (c) induce an amount of complexity equal to $t(t-1)\approx\mathcal{O}(n(n-1))\approx\mathcal{O}(n^2)$. The sum of the complexities at the steps (b) and (c) then equals $\mathcal{O}(n^2)+\mathcal{O}(n^2)\approx\mathcal{O}(n^2)$. By inspection, we have $p\leq n^2$. Therefore, the repetitions at step (2) increase the overall complexity to $n^2(\mathcal{O}(n^2))\approx\mathcal{O}(n^4)$.
\end{proof}




\section{Data}
\label{SecEnumerData}
We computationally implemented the enumeration algorithm (Algorithm~\ref{AlgorEnumerQfullRootedTrees}) and determined the numbers $|\mathcal{M}_{n,t}|$ up to certain values of $n$ for all $2\leq t<n$. An implementation of Algorithm~\ref{AlgorEnumerQfullRootedTrees} in MATLAB is available on GitHub~\cite{MohammadGitHubQfullRootedTrees}. Here, we include the numbers $|\mathcal{M}_{n,t}|$ for all $2\leq t<n\leq 31$; see Table~\ref{TabEnumTreesUpto20} for all $3\leq n\leq 20$ and $2\leq t\leq 19$, and Table~\ref{TabEnumTreesUpto31} for all $21\leq n\leq 31$ and $2\leq t\leq 30$. Also, see the integer sequence~\seqnum{A352460} contributed to the OEIS~\cite{Sloane2024}.
\begin{table}[htb]
\centering 
%\def\arraystretch{1.0}
\resizebox{\columnwidth}{!}{
\begin{tabular}{| c | r r r r r r r r r r r r r r r r r r |}
\hline
$t~\diagdown$ $n$ &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15 &16 &17 &18 &19 &20\\ 
\hline\hline 
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\\
\hline 
Total: &1 &2 &4 &6 &11 &16 &27 &41 &67 &102 &167 &260 &425 &678 &1115 &1813 &3018 &4992\\
\hline 
\end{tabular}
}
\caption{The number of unlabeled quasi-full $t$-ary rooted trees with $n$ elements for all $3\leq n\leq 20$ and $2\leq t\leq 19$.}
\label{TabEnumTreesUpto20}
\end{table}



\section{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.

\begin{table}[H]
\centering 
%\def\arraystretch{1.0}
\resizebox{\columnwidth}{!}{
\begin{tabular}{| c | r r r r r r r r r r r |}
\hline
$t\diagdown$ $n$ &21 &22 &23 &24 &25 &26 &27 &28 &29 &30  &31\\ 
\hline\hline 
 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\\
\hline 
Total: &8395 &14101 &23947 &40708 &69763 &119763 &206812 &357905 &622089 &1083659 &1894118\\
\hline 
\end{tabular}
}
\caption{The number of unlabeled quasi-full $t$-ary rooted trees with $n$ elements for all $21\leq n\leq 31$ and $2\leq t\leq 30$.}
\label{TabEnumTreesUpto31}
\end{table}


\begin{thebibliography}{99}
\bibitem{Chauve2000}
    C. Chauve, S. Dulucq, and O. Guibert, Enumeration of some labeled trees, \textit{Formal Power Series and Algebraic Combinatorics}, Springer-Verlag, Berlin, 2000, pp. 146--157.

\bibitem{Cheon2022}
    G. S. Cheon, B. Curtis, G. Kwon, and A. M. Mwafise, Riordan posets and associated incidence matrices, \textit{Linear Algebra Appl.} \textbf{632} (2022), 308--331.

\bibitem{Davey2002}
    B. A. Davey and H. A. Priestly, \textit{Introduction to Lattices and Order}, 2nd Edition, Cambridge University Press, 2002.

\bibitem{Dershowitz1980}
    N. Dershowitz and S. Zaks, Enumerations of ordered trees, \textit{Discrete Math.} \textbf{31} (1980), 9--28.

\bibitem{Gabriel2012}
    N. Gabriel, K. Peske, L. Pudwell, and S. Tay, Pattern avoidance in ternary trees, \textit{J. Integer Sequences} \textbf{15} (2012), \href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Pudwell/pudwell.html}{Article 12.1.5}.

\bibitem{Gilmore2021}
    T. Gilmore, Trees, forests, and total positivity: I. $q$-trees and $q$-forests matrices, \textit{Electron. J. Combin.} \textbf{28} (2021), Article P3.54.

\bibitem{Guo2017}
    S. Guo and J. W. Guo, A recursive algorithm for trees and forests, \textit{Discrete Math.} \textbf{340} (2017), 695--703.

\bibitem{Mohammad2020}
    S. U. Mohammad and M. R. Talukder, Poset matrix and recognition of series-parallel posets, \textit{Int. J. Math. Comput. Sci.} \textbf{15} (2020), 107--125.

\bibitem{Mohammad2021}
    S. U. Mohammad and M. R. Talukder, Interpretations of Kronecker product and ordinal product of poset matrices, \textit{Int. J. Math. Comput. Sci.} \textbf{16} (2021), 1665--1681.

\bibitem{Mohammad2022}
    S. U. Mohammad, M. S. Noor, and M. R. Talukder, An exact enumeration of the unlabeled disconnected posets, \textit{J. Integer Sequences} \textbf{25} (2022), \href{https://cs.uwaterloo.ca/journals/JIS/VOL25/Uddin/uddin6.html}{Article 22.5.4}.

\bibitem{Mohammad2023}
    S. U. Mohammad, M. R. Talukder, and S. N. Begum, Recognition of decomposable posets by using the poset matrix, \textit{Ital. J. Pure Appl. Mat.} \textbf{50} (2023), 455--466.

\bibitem{Mohammad2024}
    S. U. Mohammad, M. S. Noor, and M. R. Talukder, Recognition of the $N$-free posets by using the poset matrix, \textit{Asia Pac. J. Math.} \textbf{11} (2024), Article 72.

\bibitem{Mohammad2025APJM}
    S. U. Mohammad, M. R. Talukder, and S. N. Begum, Enumeration of $P$-series by using the poset matrix, \textit{Asia Pac. J. Math.} \textbf{12} (2025), Article 68.

\bibitem{Mohammad2025PJM}
    S. U. Mohammad, M. R. Talukder, and S. N. Begum, Enumeration of series-parallel posets by using the poset matrix, \textit{Palest. J. Math.} \textbf{14} (2025), 217--232.

\bibitem{MohammadGitHubQfullRootedTrees}
    S. U. Mohammad, GitHub Repository: Enumeration of quasi-full rooted trees (an implementation in MATLAB), 2025. Available at \url{https://github.com/SU-Mohammad/Enumeration-of-Quasi-full-Rooted-Trees.git}.

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

\bibitem{Shor1995}  
    P. W. Shor, A new proof of Cayley's formula for counting labeled trees, \textit{J. Combin. Theory Ser. A} \textbf{71} (1995), 154--158.

\bibitem{Skandera2003}
    M. Skandera and B. Reed, Total nonnegativity and $(3+1)$-free posets, \textit{J. Combin. Theory Ser. A} \textbf{103} (2003), 237--256.

\bibitem{Sloane2024}
    N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2024. Available at \url{https://oeis.org}.

\bibitem{Yamanaka2012}
    K. Yamanaka, Y. Otachi, S. Nakano, Efficient enumeration of ordered trees with $k$ leaves, \textit{Theoret. Comput. Sci.} \textbf{442} (2012), 22--27.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 06A07; Secondary 05A15, 11Y55. 

\noindent \emph{Keywords: } quasi-full rooted tree, series-parallel poset, direct sum, ordinal sum, poset matrix, matrix recognition, exact enumeration.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 23 2024; revised version received
October 23 2025. 
Published in {\it Journal of Integer Sequences}, October 27 2025.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in


\end{document}

                                                                                

