# count number of partitions of a set with n elements into k subsets

• 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]; } ``