Vrftsjtryk

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];

}

Each countP call implicitly considers a single element in the set, lets call it A.

The countP(n-1, k-1) term comes from the case where A is in a set by itself. In this case, we just have to count how many ways there are to partition all the other elements (N-1) into (K-1) subsets, since A takes up one subset by itself.

The k*countP(n-1, k) term, then, comes from the case where A is not in a set by itself. So we figure out the number of ways of partitioning all the other (N-1) values into K subsets, and multiply by K because there are K possible subsets we could add A to.

For example, consider the set [A,B,C,D], with K=2.

The first case, countP(n-1, k-1), describes the following situation:

{A, BCD}

The second case, k*countP(n-1, k), describes the following cases:

2*({BC,D}, {BD,C}, {B,CD}) 

Or:

{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}

How do we get countP(n,k)? Assuming that we have devided previous n-1 element into a certain number of partions, and now we have the n-th element, and we try to make k partition.

we have two option for this:

either

1. we have devided the previous n-1 elements into k partions(we have countP(n-1, k) ways of doing this), and we put this n-th element into one of these partions(we have k choices). So we have k*countP(n-1, k).

or:

2. we divide previous n-1 elements into k-1 partition(we have countP(n-1, k-1); ways of doing this), and we make the n-th element a single partion to achieve a k partition(we only have 1 choice: putting it seperately). So we have countP(n-1, k-1);.

So we sum them up and get the result.

Based on This a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets. So the total number of partitions of an n-element set is the Bell number which is calculated like below:
Bell number formula
Hence if you want to convert the formula to a recursive function it will be like:
k*countP(n-1,k) + countP(n-1, k-1);