stirling.py

# Fast way to compute the Stirling numbers of the second kind.
# https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

from math import factorial

def binom(a,b):
    return factorial(a) / (factorial(b)*factorial(a-b))

def stirling_fast(n,k):
    "Returns the Stirling number of the second kind."
    if n<=0 or n!=0 and n==k:
        return 1
    elif k<=0 or n<k:
        return 0
    elif n==0 and k==0:
        return -1
    else:
        s = sum((-1)**(k-j)*binom(k,j)*j**n for j in range(k+1))
        return s / factorial(k)