Tukukkk

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; 

} 

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}

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

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

we have two option for this:

either we have devided n-1 elements into k partion, and we put this additional element into an existed partion(by putting it into an existed one, we don't add the count of partion);

or, we divide previous n-1 elements into k-1 partition, and we make the additional element a single partion to achieve a k partition.

1. if we put it into one partiton of the existed k partion, since we have got countP(n-1, k) partitions, we have k choices that we can put this additional element into , that is k*countP(n-1, k).




2. if we put it as a single partition, we can only make k-1 partion with the previous n-1 elements, which is countP(n-1, k-1);

So we sum them up and get the result.