# From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives
## 3 Tree-Realizations of Barcodes
### The Combinatorics of Tree-Realization  
Let \(B=\{(b_{i},d_{i})\}_{i=0,...,n}\) be a strict barcode. In this section, we analyze the _tree-realization number_ of \(B\),  
\[\operatorname{TRN}(B)=\#\mathcal{T}(B),\]  
i.e., the number of combinatorial equivalence classes of tree-realizations of \(B\). We provide a formula for \(\operatorname{TRN}(B)\) in terms of the _index_ of each bar \((b_{i},d_{i})\), i.e., the number of bars that include \((b_{i},d_{i})\) strictly:  
\[\operatorname{index}_{i}(B)=\#\{j\mid b_{j}<b_{i}<d_{i}<d_{j}\}=\#\{j<i\mid d_ {i}<d_{j}\}.\]  
A version of this formula was established by [PERSON] in [22]. **Lemma 2**: _The tree-realization number of a strict barcode \(B=\{(b_{i},d_{i})\}_{i=0,...,n}\) is equal to the product of the indices of its bars, i.e.,_  
\[\operatorname{TRN}(B)=\prod_{1\leq i\leq n}\operatorname{index}_{i}(B).\]  
Because of the Elder Rule applied in the TMD, one branch can be attached to another only if its corresponding bar is included in the other bar. This simple observation enables us to prove the lemma by a straightforward recursion on the number of bars. In particular, the maximum tree-realization number for a strict barcode with \(n+1\) bars is \(n!\), in the specific case where \(d_{n}<...<d_{1}<d_{0}\). We call this case a strictly ordered barcode. Note that the tree-realization number does **not** satisfy  
\[\operatorname{TRN}(B)=\operatorname{TRN}(B^{\prime})\implies B\sim B^{\prime}\]  
in general, i.e., the tree-realization number is not a complete invariant of the barcode equivalence relation. For instance, barcodes (231) and (312) in Figure 7 both have \(\operatorname{TRN}(B)=2\) but have different permutation types. The inverse clearly does hold, however:  
\[\operatorname{TRN}(B)\
eq\operatorname{TRN}(B^{\prime})\implies B\
eq B^{ \prime},\]  
enabling us to detect non-equivalence of barcodes. For the pairs of barcodes studied in Sections 4 and 5 of this paper, though, it is usually true that if they have same TRN, then they are equivalent, so that we can use the TRN to detect equivalence of barcodes in these special cases. In particular, if a new bar is added to a barcode or two deaths are transposed and no other changes take place, then the tree-realization number does change. Figure 6: The two possible moves that respect the condition of a realizable barcode. Move (**A**) modifies the barcode’s ordering, whereas move (**B**) does not change the order of the deaths. Lemma 2 enables us to quantify how adding a new bar changes tree-realization number. **Lemma 3**. : _Let \(B=\{(b_{i},d_{i})\}_{i=0,\ldots,n}\) and \(B^{\prime}=B\cup\{(b_{n+1},d_{n+1})\}\), where \(b_{n+1}>b_{i}\) for all \(0\leq i\leq n\), be strict barcodes. If \(d_{i_{1}}>...d_{i_{k-1}}>d_{n+1}>d_{i_{k}}>...d_{i_{n}}\), then_  
\[\mathrm{TRN}(B^{\prime})=\mathrm{TRN}(B)\cdot k.\]  
Proof. : The condition on \(d_{n+1}\) implies that the new bar \((b_{n+1},d_{n+1})\) is included in exactly \(k\) other bars, so its index is \(k\). **Example 1**. : _Let \(B\) be a barcode with four bars such that \(b_{0}<b_{1}<b_{2}<b_{3}\) and \(d_{0}>d_{2}>d_{1}>d_{3}\), i.e., its equivalence class is (213). It is easy to see that \(\mathrm{TRN}(B)=3\) (see Figure 8). If we add a new bar \((b_{4},d_{4})\) such that \(d_{1}>d_{4}>d_{3}\), the equivalence class of the new barcode \(B^{\prime}\) is (2143), and bar \((b_{4},d_{4})\) is included in \((b_{0},d_{0})\), \((b_{2},d_{2})\), and \((b_{1},d_{1})\), but not in \((b_{3},d_{3})\) because \(d_{4}>d_{3}\). Therefore, its index is \(3\), whence \(\mathrm{TRN}(B^{\prime})=3\times 3=9\)._  
We can also apply Lemma 2 to determining how switching the order of two consecutive deaths in the barcodes affects the tree realization number. Figure 8: A barcode \(B\) in equivalence class (213) is shown in black. There are three possible combinatorial equivalence classes of trees whose TMD barcode is \(B\), also represented in black. After adding the extra bar in red, we obtain a new barcode \(B^{\prime}\), in the equivalence class (2143).