Stirling Numbers In C++

Fascinating figures are unique combinatorial entities that prompt a multitude of enumeration challenges. From a precise mathematical perspective, the Stirling numbers of the first and second categories are distinguishable entities. Yet, they each possess their own accessible variations. These numerical variants come in two forms to enumerate diverse combinatorial arrangements effectively, offering solutions to both partition and permutation dilemmas.

Stirling Numbers of Type 1:

The Stirling numbers of the first kind, denoted as c(n,k), indicate the count of arrangements where n elements are organized into k cycles specifically. Put differently, these numbers signify the total permutations possible for n objects, ensuring there are exactly k cycles within the permutations.

Stirling Numbers of Type 2:

The count of possible partitions of n elements into k non-empty, unsorted sets is referred to as the second-kind stirring number, symbolized as S(n,k). These numbers arise when items are grouped without regard to their internal order.

Recursive formulae:

Calculate Stirling numbers of the first kind c(n,k) by utilizing the following recursive relation:

c(n,k)=(n−1)⋅c(n−1,k)+c(n−1,k−1)

With their base cases:

c(n,n)=1,c(n,0)=0

Calculate Stirling numbers of the first kind, denoted as S(n,k), using the following recursive relation:

S(n,k)=k⋅S(n−1,k)+S(n−1,k−1)

With their base cases:

S(0,0)=1,S(n,0)=0 for n>0

Application of Stirling Numbers:

Several applications of stirling numbers in C++ are as follows:

• ✅ Stirling numbers are utilized in partitions, permutations, and combinatorics problems.
• ✅ First-kind numbers can be stirled to facilitate the analysis of permutations with cycles.
• ✅ When grouping or subsetting things, second-kind stirring numbers are commonly used.

Example Code for First Type:

Let's consider an example to demonstrate the Stirling Numbers in C++.

#include <iostream>
#include <vector>
using namespace std;

// Function to compute Stirling numbers of the first kind c(n, k)
int stirlingFirstKind(int n, int k) {
    // Create a 2D vector to store the dynamic programming table
    vector<vector<int>> c(n + 1, vector<int>(k + 1, 0));

    // Base cases: c(n, n) = 1 and c(n, 0) = 0 for n > 0
    for (int i = 0; i <= n; i++) {
        c[i][0] = 0;  // c(n, 0) = 0 for n > 0
        c[i][i] = 1;  // c(n, n) = 1
    }

    // Fill the DP table using the recursive relation
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            c[i][j] = (i - 1) * c[i - 1][j] + c[i - 1][j - 1];
        }
    }

    return c[n][k];
}

int main() {
    int n = 5, k = 2;
    cout << "Stirling number of the first kind c(" << n << ", " << k << ") is: "
         << stirlingFirstKind(n, k) << endl;
    return 0;
}

Output:

Stirling number of the first kind c(5, 2) is: 50

Explanation:

• ✅ Dynamic Programming Table: Value of C in C(i,j) is stored in a 2D table, i.e., Ci.
• ✅ Base case: The table is initialized with C(0,0) = 1, and then values are filled using the recursive relation.
• ✅ Complexity: It is efficient for n and k within small to medium ranges since the time complexity of this implementation is O(n⋅k).

Example Code for Second Type:

Let's consider an example to demonstrate the Stirling Numbers in C++.

#include <iostream>
#include <vector>
using namespace std;

// Function to compute Stirling numbers of the second kind S(n, k)
int stirlingSecondKind(int n, int k) {
    // Create a 2D vector to store the dynamic programming table
    vector<vector<int>> S(n + 1, vector<int>(k + 1, 0));

    // Base case: S(0, 0) = 1
    S[0][0] = 1;

    // Fill the DP table using the recursive relation
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            S[i][j] = j * S[i - 1][j] + S[i - 1][j - 1];
        }
    }

    return S[n][k];
}

int main() {
    int n = 5, k = 3;
    cout << "Stirling number of the second kind S(" << n << ", " << k << ") is: "
         << stirlingSecondKind(n, k) << endl;
    return 0;
}

Output:

Stirling number of the second kind S(5, 3) is: 25

Explanation:

• ✅ Dynamic Programming Table: S in S(i,j) is stored in a 2D table called Si.
• ✅ Base case: The table is initialized with S(0,0) = 1, and future values are filled in using the recursive relation.
• ✅ Complexity: For small to medium values of n and k, this implementation's temporal complexity is O(n⋅k), which makes it efficient.

Conclusion:

In summary, Stirling numbers (both first and second kind) are commonly encountered in the resolution of combinatorial issues related to permutations, partitions, and cycles. These numbers come in two forms: one for organizing elements into cycles and the other for dividing items into non-empty subsets. These values are calculated in diverse computer science and mathematical scenarios using recursive equations and dynamic programming to ensure effective execution, as demonstrated in C++ instances. Various areas such as combinatorial enumeration, probability, and graph theory in the realm of mathematical exploration heavily rely on Stirling numbers due to their significance in discrete mathematics.