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)$.
 A: 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.
A: ANSWER #2 (Feb. 9, 2016)
Nikita Alexeev and I have extended the approach that I outlined in the previous answer (case 2) to the case of phylogenetic networks, which resulted in the paper Combinatorial Scoring of Phylogenetic Networks. 
Along the way, we have obtained a closed-form solution for the case of binary trees, and later discovered that this result was long known and first obtained by Steel (1992). This result (quoted in Theorem 1 in our paper) is the following.
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}.$$
