I believe I can state with some confidence that TREE(3) is larger than $f_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, given a natural definition of $f$ up to $\vartheta (\Omega^{\omega}, 0)$. I can state with certainty that TREE(3) is larger than $H_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, where H is a certain version of the Hardy hierarchy.
To obtain this result, I will first define a version of TREE(n) for unlabeled trees:
Let tree(n) be the length of the longest sequence of unlabeled rooted trees $T_1, T_2, \ldots, T_m$ such that $T_i$ has less than or equal to $n+i$ vertices and for no $i, j$ with $i < j$ do we have $T_i$ homeomorphically embeddable into $T_j$. (Note the term "embeddable" rather than "subtree"; the terms are different, and I believe using "subtree" would lead to infinite sequences.)
In order to obtain a long sequence of trees, we will define a well-order on unlabeled rooted trees. This definition will be by induction on the sum of the heights of the two trees being compared.
Define an immediate subtree of a rooted tree $T$ to be a full subtree starting at one of its children.
Given two rooted trees $S, T$, we define $S = T$ if the two trees are identical. We define $S \leq T$ if $S = T$ or $S < T$.
Given two rooted trees $S, T$, we define $ < $ as follows. Say $S < T$ if $S \leq T_i$, where $T_i$ is an immediate subtree of $T$. Similarly, say $T < S$ if $T \leq S_i$, where $S_i$ is an immediate subtree of $S$.
Otherwise, compare the number of children of $S$ and $T$. If $S$ has more children than $T$, then $S > T$, and vice versa.
Otherwise, suppose $S$ and $T$ both have $n$ children. Let $S_1, S_2, \ldots, S_n$ and $T_1, T_2, \ldots T_n$ be the immediate subtrees of $S$ and $T$ respectively, ordered from smallest to largest. Compare $S_1$ to $T_1$, then $S_2$ to $T_2$, etc., until we get a pair of unequal trees $S_i$ and $T_i$. If $S_i > T_i$ then $S > T$, and vice versa. Of course, of all pairs of immediate subtrees are equal, then $S$ and $T$ will be equal.
This gives a linear order on unlabeled rooted trees, and one can prove that this is a well-order. Further, this well-ordering has order type $\vartheta(\Omega^\omega,0)$. This definition is a modification of a well-ordering of ordered rooted trees due to Levitz, and expounded on in papers by Jervell.
From this well-ordering we can define fundamental sequences for ordinals up to $\vartheta (\Omega^{\omega}, 0)$. Simply put, given an ordinal $\alpha$, let $\alpha[n]$ be the largest ordinal less than $\alpha$ corresponding to a tree of $n$ vertices or less.
From this, we can define our version of the Hardy hierarchy:
$H_0(n) = n$
$H_{\alpha + 1}( n) = H_{\alpha}( n+1)$
For $\alpha$ a limit ordinal, $H_{\alpha}( n) = H_{\alpha[n+1]}( n+1)$
Note the $n+1$'s in the last line - this differs from the usual values of $n$. Of course, this will only make the functions larger.
$H_{\alpha}( n)$ for $\alpha < \vartheta (\Omega^{\omega}, 0)$ is the final index $m$ in the sequence of trees $T_n, T_{n+1}, \ldots, T_m$ where $T_n$ corresponds to $\alpha$ and $T_i$ is the largest tree with at most $i$ vertices that is smaller than $T_{i-1}$, and $T_m$ is the tree with one vertex. Thus $H_{\vartheta (\Omega^{\omega}, 0)}( n)$ will be the final index $m$ in the sequence of trees $T_{n+1}, T_{n+2}, \ldots, T_m$ where $T_{n+1}$ is arbitrary.
Thus tree(n) $\geq H_{\vartheta (\Omega^{\omega}, 0)}( n) - n$.
So where does TREE(3) come in? Harvey Friedman himself explains in a post to the Foundations of Mathematics message boards:
http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html
In the post he explains why a proof of the theorem "TREE(3) exists" in the theory $ACA_0 + \Pi^1_2\text{-}BI$ must have more than $2\uparrow\uparrow 1000$ symbols. He does this by showing that TREE(3) must be very large - specifically, he constructs a sequence of more than $n(4)$ rooted trees labeled from {1,2,3} such that $T_i$ has at most $i$ vertices, for no $i, j$ with $i < j$ do we have $T_i$ homeomorphically embeddable into $T_j$, and each tree contains either a 2 label or a 3 label. We can obviously continue this with tree($n(4)$) trees with all labels 1. Thus we have
TREE(3) $\geq$ tree$(n(4)) + n(4) \geq H_{\vartheta (\Omega^{\omega}, 0)}(n(4))$
In fact, we can do somewhat better than this; we can replace the $n(4)$ above by $F(4)$, where $F(4)$ is defined as the length of the longest sequence of sequences $x_1, x_2, \ldots x_n$ from {1,2,3,4} such that $x_i$ has length $i+1$ and for no $i,j$ with $i < j$ do we have $x_i$ a subsequence of $x_j$. I can prove much better bounds for $F(4)$ than Friedman's lower bound for $n(4)$; specifically,
$F(4) > f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega}f_{\omega^2 + 1}f_{\omega^2 + 1}f_{\omega^2}f_{ \omega + 1}f_{ \omega + 1}f_{\omega}(30)$
But such specificity is perhaps unwarranted given how far from TREE(3) it may be.
Late edit: having now read through the OP comments, I can see that my proof is essentially a carbon copy of @darij.grinberg's approach (although my derivation was independent). I'm okay to delete this answer once/if darij chooses to post theirs.
Pick a canonical ordering of unlabelled rooted trees, say, with lexicographical comparison of tuples $(n, T_1, \ldots, T_k)$, where $n$ is the number of vertices, $T_1, \ldots, T_k$ is the non-descending sequence of children subtrees. Throughout $T, T_1, T_2$ are unlabelled rooted trees in canonical form (that is, subtrees of any vertex are ordered as above).
Let $A_n$ be the set of pairs $(T, v)$ with $|T| = n$, $v$ is a non-root vertex of $T$. Also, let $B_n$ be the set of tuples $(T_1, T_2, k, u)$ such that $|T_1| + k|T_2| = n$, $u$ is a vertex of $T_2$. Observe that $|A_n|$ and $|B_n|$ are LHS and RHS of the recurrence in OP, more readily seen by rewriting $(n - 1)t_n = \sum_{m = 1}^{n - 1}mt_m \sum_{0 < km < n} t_{n - km}$.
The bijection between $A_n$ and $B_n$ is as follows:
- we associate $(T_1, T_2, k, u)$ to $(T, v)$ by:
- $T_2$ = the subtree of $T$ containing $v$,
- $u$ = the respective vertex of $T_2$,
- $k$ = the number of children subtrees of $T$ isomorphic to $T_2$ not later than the copy containing $v$ in the ordered sequence of children subtrees,
- $T_1$ = the result of removing the $k$ children subtrees from $T$.
- we associate $(T, v)$ to $(T_1, T_2, k, u)$ by inserting $k$ copies of $T_2$ as children subtrees of the root of $T_1$ (and naming the result $T$), and picking the respective vertex $u$ in the $k$-th copy as $v$.
Best Answer
1) Concerning Bell-numbers and generalizations: you might be interested in the treatize
http://go.helms-net.de/math/binomial_new/04_5_SummingBellStirling.pdf
where I deal with continuous interpolations based on E.T.Bell's original article and then using the matrix-approach for a comparision.
2) ad Question 2: the most intuitive problem for series to be summable by some summation is the rate of growth of the coefficients (but this is not the only relevant one). A very short example: if we are in a context of powerseries, then if the sequence of coefficients grows with a constant rate (the ratio $c_{k+1} / c_k$ is constant, in other words, it has "geometric growth") and the sign is alternating, then the series can be summed for instance by Euler-summation.
If the rate is hypergeometric (and signs are alternating), where the ratio $c_{k+1}/c_k$ is linearly increasing with the index, for instance $1!x - 2!x^2+3!x^3 -...+...$ Borel-Summation can assign a meaningful value. The growthrate of the powerseries for fractional iterates of $exp(x)-1$ seems to be even more than hypergeometric, so even Borel-summation may not be sufficient. I fiddled with Noerlund-summation adapted to such growthrate, but have only heuristics so far, no thorough analysis of the validity of the results.
The key reference should be G.H.Hardy, "Divergent series"; if I recall right you can look at parts of it using google-books to get some impression of that work.
I have some discussion of this matter on my homepage http://go.helms-net.de/math/tetdocs