balls.py

# draw 100 balls of 40 colors, where the color of each ball is uniformly random, the probability of drawn at least 1 ball of each color
def g(colors, balls):
    total_colors = colors
    cache = {}
    def f(rest_colors, rest_balls):
        if (rest_colors, rest_balls) in cache:
            return cache[(rest_colors, rest_balls)]
        if rest_colors == 0:
            return 1
        if rest_balls == 0:
            return 0
        result = ((rest_colors / total_colors) * f(rest_colors - 1, rest_balls - 1) +
                  (1 - (rest_colors / total_colors)) * f(rest_colors, rest_balls - 1))
        cache[(rest_colors, rest_balls)] = result
        return result
    return f(colors, balls)