- A+

Category：Languages

This program is for count number of partitions of a set with n elements into k subsets I am confusing here `return k*countP(n-1, k) + countP(n-1, k-1);`

can some one explain what is happening here? why we are multiplying with k?

NOTE->I know this is not the best way to calculate number of partitions that would be DP

`// A C++ program to count number of partitions // of a set with n elements into k subsets #include<iostream> using namespace std; // Returns count of different partitions of n // elements in k subsets int countP(int n, int k) { // Base cases if (n == 0 || k == 0 || k > n) return 0; if (k == 1 || k == n) return 1; // S(n+1, k) = k*S(n, k) + S(n, k-1) return k*countP(n-1, k) + countP(n-1, k-1); } // Driver program int main() { cout << countP(3, 2); return 0; } `

What you mentioned is the Stirling numbers of the second kind which enumerates the number of ways to partition a set of n objects into k non-empty subsets and denoted by or .

Its recursive relation is:

for `k > 0`

with initial conditions:

.

Calculating it using dynamic programming is more faster than recursive approach:

`int secondKindStirlingNumber(int n, int k) { int sf[n + 1][n + 1]; for (int i = 0; i < k; i++) { sf[i][i] = 1; } for (int i = 1; i < n + 1; i++) { for (int j = 1; j < k + 1; j++) { sf[i][j] = j * sf[i - 1][j] + sf[i - 1][j - 1]; } } return sf[n][k]; } `