n_balls_k_buckets.py

def f(k, n):
    '''
    k indistinct bucket,
    n (n > k) balls,
    each bucket must have at least one ball,
    how many ways are there to put n balls in k buckets?
    '''
    if k == 1:
        # Only one way to put things in one bucket
        return 1
    elif n == k:
        # Each bucket has exactly one ball
        return 1
    else:
        # If the nth ball is by itself, it and its bucket can be ignored, giving
        # the f(k - 1, n - 1) term.

        # On the other hand, if the nth ball is in some bucket that is already
        # occupied, that is equivalent to solving the problem without the nth
        # ball, hence f(k, n - 1), multiplied by the ways the nth ball could be
        # added to that.
        return f(k - 1, n - 1) + k * f(k, n - 1)