Tree permutations

Write a program to calculate the different number of tree structures possible,
given n identical values.
For Example:

    For one node, the tree is a trivial one node tree.
    For two nodes, two combinations are possible:
    O               O
     \      and    /
      O           O

    For three nodes :
      O      O      O      O        O
     /      /      / \      \        \
    O      O      O   O      O        O
   /        \                 \      /
  O          O                 O    O

Answer:

/*
For the above diagrams, we can see the recursive property,
i.e, 
For given N nodes:
* One node becomes the root
* Divide the remaining N-1 nodes between left and right subtrees, and this can be
  done as follows:
  Left Subtree              Right Subtree
      0                         N-1
      1                         N-2
      2                         N-3
      ...                       ...
     N-1                         0

  Summing up the above combinations, to get the value of N, 
  The solution can be recursively defined as following:

            { 1 if n == 1  }
  F(n) =    { sigma( F(i) * F(n-i-1 ) where i = 0 to n-1 }

  note that its F(i) * F(n-i-1) , product, not a sum because its a combinatorics problem,
  If event A can be in m ways, and another event B can be done in n ways, then the total
  possible events are (m x n)

  Note that optimization can be achived by caching the results in the recursive call.


*/


#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
// the cache used to "cache the results in a recursive call"
vector cache;
size_t TreeCombinations(size_t n)
{
    if ( (n == 1) || (n == 0) )
        return cache[n];
    // Check if the result was already computed
    if ( cache[n] != 0 )
        return cache[n];
    else
    {
        int i = 0;
        size_t combinations = 0;
        //printf("{ %d \n", n);
        for ( i =0 ; i <= n-1; ++i)
        {
            size_t tmp = TreeCombinations(i) * TreeCombinations(n-i-1);
            //printf(" f(%d) * f(%d) = %d \n", i, n-i-1, tmp );
            combinations += tmp;
        }
        //printf("}\n");
        cache[n] = combinations;
    }

    return cache[n];
}

int main(int argc, char* argv[])
{
    size_t n = atoi(argv[1]);
    // initialize the cache
    cache.reserve(n+1);
    for ( int i = 0; i <= n; ++i )
    {
        cache[i] = 0;
    }
    cache[0] = 1;
    cache[1] = 1;
    // ----
    return printf("Tree combinations for %d nodes = %d \n", n, TreeCombinations(n) );
}