Stirling number

Compute Stirling numbers of the second kind efficiently with dynamic programming.

stirling-numbers dynamic-programming combinatorics math

The Stirling number of the second kind S(n, k) counts the number of ways to partition a set of n labeled objects into k non-empty unlabeled subsets. It can be computed recursively:

S(n, k) = k * S(n-1, k) + S(n-1, k-1)

with base cases S(0,0)=1, S(n,0)=0 for n>0, and S(0,k)=0 for k>0.

Write a function `stirling_number(n, k)` that returns S(n, k) as an integer. Your solution should handle up to n = 30 efficiently (use dynamic programming, not naive recursion).

Constraints

0 <= n <= 30, 0 <= k <= n. Return an integer. Expected time complexity: O(n*k), space O(k).

Example

>>> stirling_number(5, 2)
15
>>> stirling_number(4, 3)
6
>>> stirling_number(3, 1)
1

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a table or rolling array to avoid recomputation.

Remember the base cases for n=0 and k=0.

For k=1, the answer is always 1 for n>=1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.