disney.py

from functools import lru_cache
import itertools as it
from scipy.misc import comb

@lru_cache(None)
def f(k, n):
    if k == 0:
        return 0
    return k ** n - sum(int(comb(k, i)) * f(i, n) for i in range(k))

def g(k, n):
    return sum(1 for x in it.product(range(k), repeat=n) if len(set(x)) == k)