Given a tree-structure with a root node, the node can either get zero, one or two children, all with the same probability of 1/3. The children also has the same probability of getting zero, one or two children, which is 1/3. Recursively the algorithm creates the tree. What is the probability that the tree has more than N nodes in total?
Came across this question after programming a random tree generator and got really curious, would be cool if someone knew the answer.
On
Let $T_n$ be the number of ordered, rooted trees with $n$ nodes, where each node has degree $\le 3.$ These are exactly the $n$-node trees that can be generated by the random process. The probability that a given $n$-node tree is generated is $3^{-n},$ for each node is associated with a factor of $1/3,$ the probability that of having the number of children it has (or does not have, in the case of the leaves.) Therefore, the probability of generating a tree with exactly $n$ nodes is $$p_n=3^{-n}T_n.$$
$T_n$ satisfies the recurrence relation $$T_n = T_{n-1} + \sum_{k=1}^{n-2}{T_kT_{n-1-k}},\tag{1}$$ since the root may have either a single subtree with $n-1$ nodes, or two subtrees, one with $k$ nodes and one with $n-k-1$ nodes.
Notice that we distinguish the case where the first subtree has $k$ nodes from the case where the second subtree has $k$ nodes. This is what makes it an ordered tree. It's not the same thing as a binary tree, for when there is only one subtree we don't care if it the left or right subtree. It's clear from the description of the random process that this is the kind of tree we want.
Now $(1)$ is almost identical to the recurrence relation for the Motzkin numbers $$M_n = M_{n-1} + \sum_{k=0}^{n-2}{M_kM_{n-2-k}},$$ and $T_1=M_0=1, T_2=M_1=1,$ so that $T_n=M_{n-1},$ and $\boxed{p_n=3^{-n}M_{n-1}}.$
The Wikipedia article linked above gives a more convenient formula for calculating the Motzkin numbers a s a three-term recurrence, and a closed-form expression as a sum involving binomial coefficients and Catalan numbers.
Using this closed form expression, I was able to obtain a closed-form formula for the OP's question, for the OP's question, but I can't see how to simplify it into something more useful than computing the $p_n'$s individually and adding them up. For what it's worth,$$ Pr(X>M)= 1 - \sum_{n=1}^{M-1}\sum_{k=0}^{\lfloor (n-1)/2\rfloor}{\left[\binom{n-1}{k,k,n-1-2k}-\binom{n-1}{k+1,k-1,n-1-2k}\right]} $$
Interesting question! Not a full answer, but an interesting problem representation that could lead to solutions. Too long for a comment.
For this analysis the only thing that's really relevant is the number of 'live' ends where the tree can grow. We start with $1$ live end. At each step a live end is explored, replacing it with 0, 1, or 2 new live ends. View each number of live ends as a state $k$, at each step we have the chance of going to a state with $k-1, k$ or $k+1$ live ends. If we hit state $0$ we are stuck there.
Let's represent our possibilities as a polynomial $f_n(x)$, where $n$ is the number of steps, and the coefficient of $x^k$ tells us the probability of being in state $k$ after $n$ steps. Initially we have $f_0(x) = x$, we have a 100% chance of having $1$ live end. Note that $f_n(0)$ is neatly the probability of hitting state $0$ after $n$ steps.
Now the beauty of this representation is that $f_{n+1}(x) = \frac{1}{3}(x^{-1} + 1 + x) \cdot (f_{n}(x) - f_{n}(0)) + f_{n}(0)$, cancelling fractions such as $x^2 \cdot x^{-1} = x$ (so that we do not divide by zero later).
Since $f_n(0)$ is exactly the chance that after $n$ steps our tree is no longer growing, if we want to know the probability of our tree having at least $n$ nodes we simply look at $1 - f_{n-1}(0)$.
Let's be crazy, and instead of looking directly at the value of $f_n(0)$, let's look at the limit instead. We also reorder terms a bit:
$$\lim_{x\to 0}\quad f_{n+1}(x) = \frac{1}{3}(1 + x + x^2) \frac{f_{n}(x) - f_{n}(0)}{x} +f_{n}(0)$$
Doesn't that remind you of something?
$$\lim_{x\to 0}\quad f_{n+1}(x) = \frac{1}{3}(1 + x + x^2) f'_n(x) +f_{n}(0)$$ $$f_{n+1}(0) = \frac{1}{3} f'_n(0) +f_{n}(0)$$
This looked really exciting until I realized that $f'_n(0)$ is simply the coefficient of state $1$.