0
$\begingroup$

A $t$-ary tree is a plane rooted tree such that every node has either $t$ or $0$ succesors. A node with $t$ succesors is called internal nodes. How many leaves has a $t$-ary tree with n internal nodes? Moreover, let $a_n$ be the number of $t$-ary trees with $n$ internal nodes and $A(z)$ the generating function of this sequence. Find a functional equation for $A(z)$.

Let $a_n$ denote the number of $t$-ary trees with $n$ internal nodes. If there are $n$ internal nodes, then there are $t \cdot n$ leaves, while internal node cannot have $0$ successors, it will be a leaf then I guess. So, all the internal nodes must have $t$ successors, or namely $t$ leaves. I don't understand the part that asks how many leaves has a $t$-ary tree with $n$ internal nodes. And how can I find the functional equation for $A(z)$? Any ideas?

$\endgroup$
1
$\begingroup$

Let $T$ be a $t$-ary tree, and suppose that $T$ has $m$ nodes. Each node except the root has a unique parent, and that parent is an internal node. Let $V_0$ be the set of all non-root nodes, and let $V_i$ be the set of internal nodes; the map that takes a node to its parent is a $t$-to-$1$ map from $V_0$ onto $V_i$, so $|V_0|=t|V_i|$. If $T$ has $n$ internal nodes, then $m-1=|V_0|=tn$, and $m=tn+1$. If $T$ has tn+1$ nodes, $n$ of which are internal, how many leaves does it have?

If $n>0$, every $t$-ary tree with $n$ internal nodes is obtained in the following way. Let $T_1,\ldots,T_t$ be $t$-ary trees with $n_1,\ldots,n_t$ internal nodes, respectively, such that $n_1+\ldots+n_t=n-1$. Form a $t$-ary tree $T$ with $n$ internal nodes by taking a new node $r$ to be the root of $T$ and making $T_1,\ldots,T_t$ the children of $r$ in that order. Thus,

$$a_n=\sum_{n_1+\ldots+n_t=n-1}a_{n_1}a_{n_2}\ldots a_{n_t}\;,\tag{1}$$

where the sum is taken over all $t$-tuples $\langle n_1,\ldots,n_t\rangle$ of non-negative integers such that $$n_1+\ldots+n_t=n-1\;.$$ The initial condition is $a_0=1$: there is just one $t$-ary tree with no internal nodes, the tree consisting just of a root. By definition

$$A(z)=\sum_{n\ge 0}a_nz^n\;.\tag{2}$$

Thus,

$$\big(A(z)\big)^t=\left(\sum_{n\ge 0}a_nz^n\right)^t=\sum_{n\ge 0}c_nz^n\;,$$

where

$$c_n=\sum_{n_1+\ldots+n_t=n}a_{n_1}a_{n_2}\ldots a_{n_t}\;,\tag{3}$$

the sum being taken over all $t$-tuples of non-negative integers summing to $n$. Comparing $(1)$ and $(3)$, we see that $c_n=a_{n+1}$, so

$$\big(A(z)\big)^t=\sum_{n\ge 0}a_{n+1}z^n\;.\tag{4}$$

Now use $(2)$ and $(4)$ to find a relationship between $A(z)$ and $\big(A(z)\big)^t$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, this makes sense. But, what exactly do you mean by relationship? $\endgroup$ – modpro Nov 23 '15 at 9:25
  • $\begingroup$ @modpro: An equation relating them. Specifically, what fairly simple operations transform $\sum_{n\ge 0}a_{n+1}z^n$ into $\sum_{n\ge 0}a_nz^n$? $\endgroup$ – Brian M. Scott Nov 23 '15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.