I have a function that takes at least two inputs, no upper bound. Also, the order of the inputs doesn't matter. If I have $n$ inputs, what is the number of ways I can pass them to the function to get the final answer (the structure forms rooted trees since we always end up with one result, the "root")? This is a follow-up to the following question: Number of ways to apply a function taking any number of inputs and producing one output to $n$ items. The key difference is that some of the trees that were being counted there could be converted into each other by permuting the leaves (does that mean they weren't "topologically distinct"?). So for three inputs, while the count of trees in the link is $4$, the number of "topologically distinct" ones is actually $2$.
Here, I'll draw the first few trees in the sequence:
I'm pretty sure I captured all trees with $5$ leaves, but am not completely sure. If we go with this, the sequence becomes: 1,1,2,5,13,…
Searching this in OEIS leads to the following page: http://oeis.org/A001519
This describes (among other things) "Number of ordered trees with n+1 edges and height at most 3". Which doesn't sound right.
So, what is this sequence? Is there a recurrence that can help me generate it for arbitrarily large values of leave nodes, $n$ (or better still, a closed form)?
Best Answer
It looks like this is asking about the combinatorial class $\mathcal{F}$ where
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{F} = \mathcal{U} \times \mathcal{Z} + \mathcal{Z} \times \textsc{MSET}_{\ge 2}(\mathcal{F}).$$
We first compute these trees by the number of nodes represented by $\mathcal{Z}$ classified by the number of leaves and then extract the coefficient on the number of leaves, which are marked here with $\mathcal{U}.$ Translating to generating functions and using the exponential formula for the multiset operator we find
$$F(z,u) = uz + z \left( \exp\left(\sum_{\ell\ge 1} \frac{F(z^\ell, u^\ell)}{\ell} \right) - 1 - F(z,u) \right).$$
We introduce $F_n(u) = [z^n] F(z,u)$ to get
$$F(z,u) = uz + z \left( \exp\left(\sum_{\ell\ge 1} \frac{1}{\ell} \sum_{q\ge 0} F_q(u^\ell) z^{q\ell} \right) - 1 - F(z,u) \right).$$
Differentiating with respect to $z$ we obtain
$$F'(z,u) = u + (F(z,u)-uz)/z \\ + z \left( \exp\left(\sum_{\ell\ge 1} \frac{F(z^\ell, u^\ell)}{\ell} \right) \left(\sum_{\ell\ge 1} \sum_{q\ge 1} q F_q(u^\ell) z^{q\ell-1} \right) - F'(z,u) \right).$$
This is
$$F'(z,u) = F(z,u)/z \\ + z \left( ( (F(z,u)-uz)/z + 1 + F(z,u)) \times \left(\sum_{\ell\ge 1} \sum_{q\ge 1} q F_q(u^\ell) z^{q\ell-1} \right) - F'(z,u) \right)$$
or alternatively
$$F'(z,u)/z - F(z,u)/z^2 + F'(z,u) \\ = (1-u + F(z,u) + F(z,u)/z) \times \left(\sum_{\ell\ge 1} \sum_{q\ge 1} q F_q(u^\ell) z^{q\ell-1} \right) .$$
Extracting the coefficient on $z^{n-2}$ we obtain for the LHS
$$n F_n(u) - F_n(u) + (n-1) F_{n-1}(u) = (n-1) (F_n(u) + F_{n-1}(u)).$$
We get for the first piece on the RHS
$$(1-u) [z^{n-2}] \left(\sum_{\ell=1}^{n-1} \sum_{q\ge 1} q F_q(u^\ell) z^{q\ell-1} \right).$$
Here we must have $n-2 = q\ell-1$ or $n-1=q\ell.$ We find $$(n-1) (1-u) \sum_{\ell|(n-1)} \frac{1}{\ell} F_{(n-1)/\ell}(u^\ell).$$
We get for the second piece
$$\begin{align*} & [z^{n-2}] \left(\sum_{\ell=1}^{n-1} \sum_{q\ge 1} q F_q(u^\ell) z^{q\ell-1} \right) (F(z,u) + F(z,u)/z) \\ & = \sum_{\ell=1}^{n-1} \sum_{q\ge 1} q F_q(u^\ell) [z^{n-1-q\ell}] (F(z,u) + F(z,u)/z) \\ & = \sum_{\ell=1}^{n-1} \sum_{q=1}^{\lfloor (n-1)/\ell \rfloor} q F_q(u^\ell) [z^{n-1-q\ell}] (F(z,u) + F(z,u)/z) \\ & = \sum_{\ell=1}^{n-1} \sum_{q=1}^{\lfloor (n-1)/\ell \rfloor} q F_q(u^\ell) (F_{n-1-q\ell}(u) + F_{n-q\ell}(u)).\end{align*}$$
This gives the recurrence for $n\ge 2$ where $F_0(u) = 0$ and $F_1(u) = u$:
$$\bbox[5px,border:2px solid #00A000]{ \begin{align*} F_n(u) & = - F_{n-1}(u) + (1-u) \sum_{\ell|(n-1)} \frac{1}{\ell} F_{(n-1)/\ell}(u^{\ell}) \\ & + \frac{1}{n-1} \sum_{\ell=1}^{n-1} \sum_{q=1}^{\lfloor (n-1)/\ell \rfloor} q F_q(u^\ell) (F_{n-1-\ell q}(u)+F_{n-\ell q}(u)). \end{align*}}$$
As an example we have
$$F_5(u) = u^4 + u^3.$$
The reader is invited to replicate these trees from the number of leaves. We also have as another example
$$F_{10}(u) = {u}^{9}+6\,{u}^{8}+16\,{u}^{7}+12\,{u}^{6}.$$ This says that e.g. there are sixteen of these trees on ten nodes having seven leaves.
We get for the count of our trees the sequence $\{F_n(1)\}_{n\ge 0}$ which is
$$0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, \ldots $$
which points us to OEIS A001678 where a considerable amount of material both theoretic and applied can be found. We quote from the definition of the sequence which says it is the "number of unordered rooted trees with $n$ nodes where nodes cannot have out-degree $1$." This is precisely the meaning of the combinatorial class we have used so we know we have the correct answer.
Now to collect the trees with $m$ leaves on some number of nodes we first observe that we need at least $m+1$ nodes (this gives the star graph). On the other hand the maximum number of nodes happens in a full binary tree on $2m-1$ nodes. Therefore the number of trees with $m$ leaves where $m\ge 2$ is given by$$G_m = \sum_{q=m+1}^{2m-1} [u^m] F_q(u).$$
We also have $G_1 = 1.$ If we desire a single formula for $m\ge 1$ and don't mind a zero term for $m\ge 2$ we may also use
$$G_m = \sum_{q=m}^{2m-1} [u^m] F_q(u).$$
This gives the sequence $\{G_m\}_{m\ge 1}$ which is
$$1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, \ldots $$
Note that the diagram by OP for $m=5$ contains a duplicate (trees number two and three). The sequence points us to OEIS A000669 where we learn that this object is known as a "series-reduced planted tree with $n$ leaves" and there is much more.
Here is some Maple code for those who are interested in working with these sequences. (The variable names originate with the MathJax above.)with(numtheory); F := proc(n) option remember; local res, ell, q; if n=0 then return 0 fi; if n=1 then return u fi; res := - F(n-1) + (1-u)*add(1/ell*subs(u=u^ell, F((n-1)/ell)), ell in divisors(n-1)) + 1/(n-1)* add(add(q*subs(u=u^ell, F(q))* (F(n-1-ell*q)+F(n-ell*q)), q=1..floor((n-1)/ell)), ell=1..n-1); expand(res); end; G := m -> local q; add(coeff(F(q), u, m), q=m..2*m-1);