## 1 Introduction
Since both encoder and decoder will know what hierarchical type class is being encoded, the decoder will know what the root label of the tree representation should be, and then the successive bits of the codeword allow the decoder to grow the tree representation from the root downward. Before discussing the nature of the results to be obtained in this paper, we need some definitions and notation. Fix integers \(m,k\geq 2\), which serve as parameters in the subsequent development; \(k\) is the partitioning parameter already introduced, and \(m\) is called the \"alphabet cardinality parameter\" because we shall be dealing with an \(m\)-letter data alphabet, denoted \(\mathcal{A}_{m}=\{a_{1},a_{2},\cdots,a_{m}\}\). For each \(j\geq 0\), we define a \(j\)-string \(x\) to be a string of length \(k^{j}\) over \(\mathcal{A}_{m}\). Note that if \(j\geq 1\), for each \(j\)-string \(x\) there is a unique \(k\)-tuple \((x^{1},x^{2},\cdots,x^{k})\) whose entries are \((j-1)\)-strings such that \(x=x^{1}*x^{2}*\cdots*x^{k}\); this \(k\)-tuple is called the \(k\)-partitioning of \(x\). If \(S_{1},S_{2},\cdots,S_{k}\) are non-empty sets of \(j\)-strings, let \(S_{1}*S_{2}*\cdots*S_{k}\) be the set of all \((j+1)\)-strings of the form \(x^{1}*x^{2}*\cdots*x^{k}\), where \(x^{i}\) belongs to \(S_{i}\) for \(i=1,2,\cdots,k\). The \(0\)-strings are the individual letters in \(\mathcal{A}_{m}\). We wish to formally define the family \(\mathcal{S}_{m,k}\) of all hierarchical type classes in which the alphabet cardinality parameter is \(m\) and the partitioning parameter is \(k\). Instead of using the tree isomorphism definition of hierarchical type class given at the beginning of the paper, we will use an equivalent inductive definition, which is more convenient in the subsequent development. First, we define the hierarchical type class of a \(0\)-string to be the set consisting of the string itself. Given \(j\)-string \(x\) with \(j\geq 1\), and assume hierarchical type classes of \((j-1)\)-strings have been defined. Let \((x^{1},\cdots,x^{k})\) be the \(k\)-partitioning of \(x\) and let \(S_{i}\) be the hierarchical type class of \(x^{i}\) (\(i=1,\cdots,k\)). The hierarchical type class of \(x\) is then defined as  
\[\bigcup_{\pi\in\Pi_{k}}\big{[}S_{\pi(1)}*S_{\pi(2)}*\cdots*S_{\pi(k)}\big{]} \tag{1}\]  
Figure 1: Example 1 Tree Representations and Codeword Table. where, from now on, \(\Pi_{k}\) is the set of all permutations of \(\{1,2,\cdots,k\}\). A set is called a hierarchical type class of order \(j\) if it is the hierarchical type class of some \(j\)-string. A set is called a hierarchical type class if it is a hierarchical type class of order \(j\) for some \(j\geq 0\). The family \(\mathcal{S}_{m,k}\) is then the set of all hierarchical type classes, of all orders. We define the type of \(j\)-string \(x\) to be the vector \((n_{1},\cdots,n_{m})\) whose \(i\)-th component \(n_{i}\) is the frequency of letter \(a_{i}\) in \(x\). For each \(j\geq 0\), let \(\Lambda_{j}(m,k)\) be the set of all types of \(j\)-strings. Let \(\Lambda(m,k)\) be the union of the \(\Lambda_{j}(m,k)\)'s for \(j\geq 0\), and let \(\Lambda^{+}(m,k)\) be the union of the \(\Lambda_{j}(m,k)\)'s for \(j\geq 1\). A type in \(\Lambda_{j}(m,k)\) will be said to be of order \(j\). If \(\lambda\in\Lambda(m,k)\), let \(\|\lambda\|\) denote the sum of the components of \(\lambda\). If \(\lambda\) is of order \(j\), then \(\|\lambda\|=k^{j}\). All strings in a hierarchical type class have the same type, because permuting a string does not change the type. This property is listed below, along with some other properties whose simple proofs are omitted. * **Prop. 1:** All strings in a hierarchical type class have the same type. * **Prop. 2:** For each \(j\geq 0\), the distinct hierarchical type classes of order \(j\) form a partition of the set of all \(j\)-strings. * **Prop. 3:** Let \(\lambda\in\Lambda(m,k)\), and let \(\mathcal{S}_{m,k}(\lambda)\) denote the set of all hierarchical type classes in \(\mathcal{S}_{m,k}\) whose strings are of type \(\lambda\).