# Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors.
Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$.

For some $L \subseteq L(T)$, denote by $t(L)$ the smallest subtree of $T$ containing $L$. That is, $t(L)$ is the minimal (in terms of nodes) connected induced subgraph of $T$ that contains $L$.

A $k$-partition $P = \{L_1, \ldots, L_k\}$ of $L(T)$ is called valid if for any distinct $L_i, L_j \in P$, $t(L_i)$ and $t(L_j)$ are vertex-disjoint.

The question is : how many valid $k$-partitions of $L(T)$ does $T$ have ? Denote by $p(T)$ the number of such partitions.

I'd like to know if this problem is known/has been addressed previously.

I'd be happy with lower and upper bounds on $p(T)$. I'd also like to know if the structure of $T$ is relevant, or is $p(T)$ only dependent on $|L(T)|$ ?

NOTE : this originates from this thing called the Perfect Phylogeny Problem, which has been studied for some time - but no one seems to have bothered with counting $p(T)$.

• I don't know about useful bounds, but in general $p(T)$ will not be a function of $|L(T)|$ alone. To see this, you can find two non-isomorphic trees, each with ten nodes and $|L(T)| = 6$, that have different values for $p(T)$. – Will Brian Jun 9 '15 at 14:05
• @WillBrian: It turns out that $p(T)$ is, in fact, a function of $|L(T)|$ as was first discovered by Steel (1992). Details are given in the new answer below. – Max Alekseyev Feb 10 '16 at 2:44
• @MaxAlekseyev: I revisited my example this morning, and I think I must have simply miscounted the valid partitions for one (or both) of the trees the first time around. It seems you are certainly right -- thanks for correcting my mistake. – Will Brian Feb 10 '16 at 15:13

UPDATE. My original answer addressed the case when $t(L)$ is defined as the minimal binary subtree (which may be rooted, i.e. have one vertex of degree 2). This is now posed as Case 1.

Case 2 down below addresses the case when $t(L)$ is the minimal arbitrary subtree (i.e., connected acyclic graph).

Case 1. $t(L)$ is a binary subtree.

Each valid partition corresponds to a binary subtree of the given tree. Namely, let $T'$ be a binary subtree of $T$. If $T'$ consists of a single edge $t$, then this edge defines of a $2$-partition of $L(T)$ obtained by removal of $t$ from $T$, which splits $L(T)$ into two complementary subsets.

More generally, $T'$ with $k>2$ leaves defines a $k$-partition of $L(T)$ as follows. Every leaf $t$ of $T'$ corresponds to a subset of $L(T)$: removal of the leaf edge of $t$ in $T'$ from $T$ splits $T$ into two subgraphs, one of which is edge-disjoint with $T'$. The set of leaves of this subgraph defines a subset $L_t$ of $L(T)$. It is clear that $L_{t_1}$ and $L_{t_2}$ are disjoint for any distinct leaves $t_1$ and $t_2$ of $T'$. Furthermore, each leaf of $T$ belongs to $L_t$ for some leaf $t$ of $T$. That is, the sets $L_t$, where $t$ runs over the leaves of $T'$, form a valid $k$-partition of $L(T)$.

Here is a modification of the algorithm from Counting the number of subgraphs in a given labeled tree that counts the number of binary subtrees with $k$ leaves in the given binary $T$.

Let $\ell$ be a fixed leaf of $T$ and $r$ be its the only neighbor. Let $T_r$ be a rooted binary tree obtained from $T$ by removal of $\ell$, with the root at $r$. More generally, let $T_v$ denote the subtree of $T_r$, rooted at vertex $v$.

For a vertex $v$ in $T_r$, define $$A_v(z)=a_1\cdot z+a_2\cdot z^2+\dots,$$ $$B_v(z)=b_1\cdot z+b_2\cdot z^2+\dots,$$ where $a_i$ is the number of binary subtrees of $T_v$ that have $i$ leaves and include $v$; and similarly, $b_i$ is the number of binary subtrees of $T_v$ that have $i$ leaves and do not include $v$.

If $v$ is a leaf then $A_v(z)=z$ and $B_v(z)=0$.

If $u_1,u_2$ are the children of a non-leaf $v$, then $$\begin{cases} A_v(z) = z + A_{u_1}(z)\cdot A_{u_2}(z), \\ B_v(z) = A_{u_1}(z) + B_{u_1}(z) + A_{u_2}(z) + B_{u_2}(z), \end{cases}$$ and the answer is the coefficient of $z^{k-1}$ in $$A_r(z)+B_r(z).$$ Here we account for the fact that rooted binary subtrees in $T_r$ with $k-1$ leaves correspond to unrooted binary subtrees in $T$ with $k$ leaves, namely, a subtree with a root $r'$ in $T_r$ gets the "parent" edge of $r'$ attached in $T$ (in particular, for $r'=r$, we get an extra leaf $\ell$ in the corresponding subtree of $T$).

The two recurrences need to be applied once for each vertex of $T_r$ in the bottom-up fashion, starting from the leaves of $T_r$ and ending at the root $r$.

P.S. Elements of valid partitions of $L(T)$ are studied to some extent in my paper under the name of $T$-consistent multicolors.

Case 2. $t(L)$ is an arbitrary subtree.

Smilarly to the above, we define $\ell$, $r$, and $T_v$.

For a vertex $v$ in $T_r$, define $$A_v(z)=a_1\cdot z+a_2\cdot z^2+\dots,$$ $$B_v(z)=b_1\cdot z+b_2\cdot z^2+\dots,$$ $$C_v(z)=c_1\cdot z+c_2\cdot z^2+\dots,$$ where

• $a_i$ is the number of forests in $T_v$, containing $v$ and consisting of $t(L_j)$, where $L_j$ ($j=1,2,\dots,i$) form an $i$-partition of $L(T_v)$ (notice that a subtree containing $v$ must also contain both its children in $T_v$ if there are any);

• $b_i$ is the number of forests in $T_v$, not containing $v$ and consisting of $t(L_j)$, where $L_j$ ($j=1,2,\dots,i$) form a partition of $L(T_v)$;

• $c_i$ is the number of forests in $T_v$, containing $v$ as a leaf and consisting of $t(L_1),\dots, t(L_{i-1})$ and $t(L_i\cup\{v\})$, where $L_j$ ($j=1,2,\dots,i$) form an $i$-partition of $L(T_v)$ (notice that a subtree containing $v$ must also contain exactly one child of $v$ in $T_v$).

If $v$ is a leaf then $A_v(z)=z$ and $B_v(z)=C_v(z)=0$.

If $u_1,u_2$ are the children of a non-leaf $v$, then $$\begin{cases} A_v(z) = \frac{1}{z}\cdot (A_{u_1}(z)+C_{u_1}(z))\cdot (A_{u_2}(z)+C_{u_2}(z)), \\ B_v(z) = (A_{u_1}(z)+B_{u_1}(z))\cdot (A_{u_2}(z)+B_{u_2}(z)), \\ C_v(z) = (A_{u_1}(z)+C_{u_1}(z))\cdot (A_{u_2}(z)+B_{u_2}(z))+(A_{u_1}(z)+B_{u_1}(z))\cdot (A_{u_2}(z)+C_{u_2}(z)). \end{cases}$$

The number of valid $k$-partitions of $T$ in given by the coefficient of $z^k$ in $$(1+z)\cdot A_r(z) + z\cdot B_r(z) + C_r(z).$$

Example. Let $T$ be a tree on 6 vertices $a,b,c,d,e,f$ with edges $(a,b)$, $(b,c)$, $(c,d)$, $(b,e)$, $(c,f)$. So the leaves of $T$ are $a,d,e,f$.

First we fix a leaf $\ell$, say, $\ell = a$. Then $r=b$ and we have a rooted tree $T_r$ with leaves $d,e,f$. For each of them we have $$(A_d(z),B_d(z),C_d(z)) = (A_e(z),B_e(z),C_e(z)) = (A_f(z),B_f(z),C_f(z)) = (z,0,0).$$

From ABC-values at $d,f$, we compute them at their parent $c$: $$(A_c(z),B_c(z),C_c(z)) = (z,z^2,2z^2).$$

From ABC-values at $c,e$, we compute them at their parent $r=b$: $$(A_r(z),B_r(z),C_r(z)) = (z+2z^2,z^2+z^3,2z^2+3z^3).$$

Now we compute the answer: $$(1+z)\cdot A_r(z) + z\cdot B_r(z) + C_r(z) = (1+z)\cdot (z+2z^2)+z\cdot (z^2+z^3)+(2z^2+3z^3)$$ $$=z+5z^2+6z^3+z^4.$$ It is easy to check that we indeed have one valid 1-parition of $L(T)$, five (equal number of edges in $T$) valid 2-partitions, six ($=\binom{4}{2}$) valid 3-partitions, and one valid 4-partition.

• Thank you for your answer ! You have convinced me that every binary subtree with $k$ leaves defines a valid $k$-partition, but I am struggling with the converse. Take a path of length 4 with vertices $a, b, c, d$ with leaves $a$, $b$. Then add a neighbor $e$ to $b$ and a neighbor $f$ to $c$. The $3$-partition $ad | e | f$ is valid, but I can't find a corresponding binary subtree. In fact, what I think would fit your description is the subtree induced by $\{e,b,c,f\}$, which has 2 leaves and is not binary. Do you think that the subtrees to cound need to be extended to be exact ? – Manuel Lafond Jun 9 '15 at 20:26
• (erratum) The leaves of the path described above are $a, d$ and not $a, b$. – Manuel Lafond Jun 9 '15 at 20:39
• @ManuelLafond: I understand $t(L)$ as a minimal binary subtree (as otherwise it does not make sense from the phylogenetic perspective). In these settings $ad|e|f$ is not a valid partition. – Max Alekseyev Jun 9 '15 at 21:33
• Well, a non-binary $t(L)$ making sense or not depends on what you're doing I suppose. For my purposes, a valid partition (binary subtrees or not) means that the tree has a rooting that explains the trait corresponding to the partition without homoplasy - i.e. a value of the trait does not get inherited by two ancestors independently. Still, best answer so far...it gives me some hints on where to look for a lower bound. – Manuel Lafond Jun 10 '15 at 14:40
• @ManuelLafond: I have addressed the case of arbitrary subtrees $t(L)$ in the update. Check it out. – Max Alekseyev Jun 10 '15 at 21:58

The number of valid ("convex" in the terminology of the aforementioned papers) $k$-partitions $L(T)$ does not depend on the topology of a binary tree $T$ but only on the number of its leaves $n=|L(T)|$, and is given by the binomial coefficient: $$\binom{2n-k-1}{k-1}.$$ Correspondingly, the total number of valid partitions is the Fibonacci number: $$\sum_{k=1}^n \binom{2n-k-1}{k-1} = F_{2n-1}.$$