Number of all possible sub-trees of m nodes of a given k-regular tree of n nodes.

Question

I have a k-regular tree of n nodes rooted at u and I wish to find all its possible sub-trees of m nodes, again rooted at u. It will be of immense help. Thank you.

Answer 1

I think we have to be satisfied with a recursive formula. Let $T$ be a $k$-regular tree rooted at $u$ and let $u_1,u_2,\dots,u_k$ be the children of $u$. For $n=1,2,\dots,k$ let $T_k$ be the subtree rooted at $u_n$ containing u_n and all of its descendants, together with the edge $uu_n.$ I include the edge $uu_n$ so that $T_n$ will be $k$-regular. The subtrees of $T_n$ rooted at $u_n$ that contain uu_n are in one-to-one correspondence with with the subtrees that don't contain it, so we can include half the subtrees of $T_n$ in constructing subtrees of $T$. Also, we may not include $u_n$ at all.

Let $f_k$ be the function that counts the labeled subtrees rooted at $u$. Then the foregoing considerations show $$f(T)= \cases{1,&height($T$)=0\\ \prod_{n=1}^k(1+f(T_n)/2),&otherwise}$$