test.py

# coding: UTF-8

MAX_ELE = 20
count = {}
def traverse(dep, ele):
    if ele > MAX_ELE: return
    count[ele] = count.get(ele,0) + 1
    for i in range(2 * dep + 1 - ele):
        # traverse all child nodes [1+ele, 2 * dep + 1]
        traverse(dep + 1, i + 1 + ele)

def test():
    '''
    >>> test()
    0 1
    1 1
    2 1
    3 2
    4 3
    5 6
    6 10
    7 20
    8 35
    9 70
    10 126
    11 252
    12 462
    13 924
    14 1716
    15 3432
    16 6435
    17 12870
    18 24310
    19 48620
    20 92378
    '''
    traverse(0, 0)
    for i in xrange(MAX_ELE + 1):
        print i, count[i]

if __name__ == '__main__':
    import doctest
    doctest.testmod()

http://www.wolframalpha.com/input/?i=binomial%28n+-+1%2C+floor%28%28n+-+1%29%2F2%29%29 binomial(n - 1, floor((n - 1)/2))

http://oeis.org/A001405