Counting Chains and Antichains in the Complete Binary Tree

Abstract

Let \(T_n\) be the complete binary tree of height \(n\) considered as the Hasse-diagram of a poset with its root \(1_n\) as the maximum element. For a tree or forest \(T\), we count the embeddings of \(T\) into \(T_n\) as posets by the functions \(A(n;T) = |\{S \subseteq T_n : 1_n \in S, S \cong T\}|\), and \(B(n;T) = |\{S \subseteq T_n : 1_n \notin S, S \cong T\}|\). Here we summarize what we know about the ratio \(A(n;T)/B(n;T)\), in case of \(T\) being a chain or an antichain.