Stirling Numbers of the Second Kind
Statement
Goal
A Stirling number of the second kind (S2), often used in probability and combinatorics problems, is the number of ways you can partition a set of n objects into k non-empty subsets. It can be calculated using:S2(n, k) = k*S2(n-1, k) + S2(n-1, k-1), n > 1
S2(1, k) = 0, k > 1
S2(1, 1) = 1
Input
Line 1: n
Line 2: k
Line 2: k
Output
S2(n,k)
Constraints
1 ≤ k ≤ n ≤ 25
S2(n,k) < 2^63
S2(n,k) < 2^63
Example
Input
5 4
Output
10
Game modes
Fastest, Shortest
Test cases
Test 1 Test
Input
5
4
Output
10
Validator 1 Validator
Input
5
2
Output
15
Test 2 Test
Input
10
5
Output
42525
Validator 2 Validator
Input
12
8
Output
159027
Test 3 Test
Input
15
10
Output
12662650
Validator 3 Validator
Input
15
7
Output
408741333
Test 4 Test
Input
20
11
Output
1900842429486
Validator 4 Validator
Input
20
9
Output
12011282644725
Test 5 Test
Input
25
12
Output
362262620784874680
Validator 5 Validator
Input
25
16
Output
526655161695960
Solution language
Solution
Stub generator input