Average number of leaves in an uniformly random, label-less, binary tree with a total number of nodes of n.

script.py

# Fast nCk with memoization.
memo_b = {}
def binomial(n, k):
    """
    A fast way to calculate binomial coefficients by Andrew Dalke.
    See http://stackoverflow.com/questions/3025162/statistics-combinations-in-python
    """
    if (n, k) not in memo_b:
        if 0 <= k <= n:
            ntok = 1
            ktok = 1
            for t in range(1, min(k, n - k) + 1):
                ntok *= n
                ktok *= t
                n -= 1
            memo_b[n, k] = ntok // ktok
        else:
            memo_b[n, k] = 0
    return memo_b[n, k]

# Catalan number: number of different label-less, binary trees with n nodes. 
def C(n):
    return binomial(2 * n, n) / (n + 1)

# Sum of the number of leaves of every tree having a total number of nodes of n.
# N(n) = | SUM(i = 0..n-1){N(i) * C(n-1-i) + N(n-1-i) * C(i)} if n > 1
#        | 1 if n == 1
#        | 0 else
#
# Let n be the given number of nodes of a tree we are trying to build;
# you can either build it with 0 node on the left and n-1 on the right or 1 on the left and n-2 on the right, etc.
# Each tree built by applying this reasoning on the left (respectivly right) will be different for each subtree
# you can build on the right (respectivly left).
memo_N = {}
def N(n):
    if n not in memo_N:
        if i > 1:
            memo_N[n] = sum(N(i) * C(n - 1 - i) + N(n - 1 - i) * C(i) for i in range(n))
        elif i == 1:
            memo_N[n] = 1
        else:
            memo_N[n] = 0
    return memo_N[n]

# Expectation of the number of leaves.
def E(n):
    return N(n)/C(n)

for i in range(516):
    print(i, "nodes :", int(E(i) * 1000)/1000, "leaves on average")

# General formula assuming E is affine a*(x-2) + b (wich it isn't but works well for low values)
# (it's just a guess, it might be in fact diverging)
print("Formula : ", (E(515)-E(2)) / (515 - 2) ,"* n +", E(2))