# Generating function for $t$-ary tree

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?

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$. • Thanks, this makes sense. But, what exactly do you mean by relationship? – modpro Nov 23 '15 at 9:25 • @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\$? – Brian M. Scott Nov 23 '15 at 20:19