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$.