Stirling Number of the Second Kind

Problem

Count the ways to partition n labeled items into k nonempty unlabeled blocks using the closed form:

S(n, k) = (1 / k!) * sum over j of (-1)^j * C(k, j) * (k - j)^n.

Return 0 when n < 0, k < 0 or k > n.

Hint

The alternating sum counts surjections, and dividing by k! removes the labels.

case 1

in: [0,0]

expected: 1

case 2

in: [3,2]

expected: 3

case 3

in: [4,2]

expected: 7

case 4

in: [5,0]

expected: 0

case 5

in: [5,1]

expected: 1

Starter codePython

import math


def stirling_second(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor