The elder binary trees

Such ancestral binary tree is normally called a full binary tree. It is well-known that the number of full binary trees with $2n+1$ vertices is $C_n$ , where $C_n$ is the $n$ -th Catalan number given as $\frac{1}{n+1} \binom{2n}{n}$ . (One simple proof is to consider the sizes of the subtrees of the root, and compare it with the identity $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$ .) Simply plugging this in, we want to find the last three digits of $C_{1007} = \frac{1}{1008} \binom{2014}{1007}$ ; with some language that supports arbitrary precision integer (like Java or Python), we can compute that this 602-digit number ends with $\boxed{480}$ .

All ancestral trees have an odd number of nodes. A tree with $2n+1$ nodes consists of a top node, and continues with trees of sizes $2k+1$ and $2k'+1$ . We have $k + k' = n-1$ .

The numbers get large quickly! Therefore I truncate all values modulo 1000. After all, we only need the last three digits. This code gives the correct answer of $\boxed{480}$ :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

        int trees[] = new int[1008];            // trees[n] = ways to make 2n+1 tree

        trees[0] = 1;

        for (int N = 1; N <= 1007; N++) {
            trees[N] = 0;

            for (int k = 0; k < N; k++) {
                trees[N] += trees[k] * trees[N-k-1];
                trees[N] %= 1000;
            }
        }

        out.println(trees[1007]);

Simple python:

l=[0,1]
for i in range(2,2016):
  s=0
  for j in range(1,i):
    s+=l[j]*l[i-1-j]
  l.append(s%1000)
print(l[2015])