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](http://en.wikipedia.org/wiki/Perfect_phylogeny "Perfect phylogeny problem"), 
which has been studied for some time - but no one seems to have bothered with counting $p(T)$.



Partitioning a binary tree into vertex-disjoint subtrees
**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](https://mathoverflow.net/questions/86817/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](http://dx.doi.org/10.1101/gr.082784.108) 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.


