GraphEnumeration

"""
Write a function answer(N, K) which returns the number of ways to connect N
distinctly labelled Nodes with exactly K Edges, so that there is a path
between any two Nodes.

The return value must be a string representation of the total number of
ways to do so, in base 10.
N will be at least 2 and at most 20.
K will be at least one less than N and at most (N * (N - 1)) / 2
"""

def binomial(n, k):
    result = 1
    for i in range(1, k+1):
        result = result * (n-i+1) / i
    return result

def answer(N, K):
    placeholder = 0
    for i in xrange(N-1, (N*(N-1)/2), 1):
        placeholder += qq(N,K)*(1**K)
    return placeholder

def qq(N, K):

    if K < N-1 or K > N*(N-1)/2:
        return 0;
    if K == N-1:
        return N^(N-2)

    res = binomial(N*(N-1)/2, K)

    for m in xrange(0, N-2):
        res1 = 0
        for p in xrange(K-1/2*(m+1)*m,K-m,1):
            res1 += binomial((N-1-m)*(N-2-m)/2, p)*qq(m+1, K-p)
        res -= binomial(N-1, m)*res1
    return res

def test():
    print answer(2,1) #should be 1
    print answer(4,3) #should be 16
    print answer(3,2) #should be 3
    print answer(4,6) ##should be 1
test()