S(r, n), represents the number of ways that we can arrange r objects around indistinguishable circles of length n, and every circle n must have at least one object around it.
Examples:
Input: r = 9, n = 2
Output: 109584
Input: r = 6, n = 3
Output: 225
The special cases are:
- S(r, 0) = 0, trivial.
- S(r, 1) represents the circular permutation which is equal to (r – 1)!
- S(r, n) where r = n, equals 1.
- S(r, r -1) = rC2
An important identity of the Stirling numbers that S(r, n) = S(r – 1, n – 1) + (r – 1) * S(r – 1, n)
Approach: For simplicity, denote the r distinct objects by 1, 2, …, r. Consider the object “1”. In any arrangement of the objects, either
- “1” is the only object in a circle or
- “1” is mixed with others in a circle.
In case 1, there are s(r – 1, n – 1) ways to form such arrangements. In case 2, first of all, the r — 1 objects 2, 3, …, r are put in n circles in s(r — 1, n) ways; then “1” can be placed in one of the r — 1 distinct space to the “immediate right” of the corresponding r — 1 distinct objects. By multiplication principle, there are (r — 1)s(r — 1, n) ways to form such arrangements in case 2. The identity now follows from the definition of s(r, n) and addition principle.
Using the initial values S(0, 0) = 1, s(r, 0) = 0 for r > 1 and s(r, 1) = (r — 1)! for r > 1, and applying the identity we proved, we can easily get the Stirling number by computing it in a recursive way.
In the code, we have three functions that are used to generate the Stirling numbers, which are nCr(n, r), which is a function to compute what we call (n – choose – r), the number of ways we can take r objects from n objects without the importance of orderings. factorial (int n) is, unsurprisingly, used to compute the factorial of a number n. The function Stirling number(r, n) works recursively using the four base cases discussed above and then recursing using the identity we proved.
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <iostream>using namespace std;// Calculating factorial of an integer n.long long factorial(int n){ // Our base cases of factorial 0! = 1! = 1 if (n == 0) return 1; // n can't be less than 0. if (n < 0) return -1; long long res = 1; for (int i = 2; i < n + 1; ++i) res *= i; return res;}// Function to compute the number of combination// of r objects out of n objects.int nCr(int n, int r){ // r cant be more than n so we'd like the // program to crash if the user entered // wrong input. if (r > n) return -1; if (n == r) return 1; if (r == 0) return 1; // nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r) return nCr(n - 1, r - 1) + nCr(n - 1, r);}// Function to calculate the Stirling numbers.// The base cases which were discussed above are handled// to stop the recursive calls.long long stirlingNumber(int r, int n){ // n can't be more than // r, s(r, 0) = 0. if (n > r) return -1; if (n == 0) return 0; if (r == n) return 1; if (n == 1) return factorial(r - 1); if (r - n == 1) return nCr(r, 2); else return stirlingNumber(r - 1, n - 1) + (r - 1) * stirlingNumber(r - 1, n);}// Driver programint main(){ // Calculating the stirling number s(9, 2) int r = 9, n = 2; long long val = stirlingNumber(r, n); if (val == -1) cout << " No stirling number"; else cout << "The Stirling Number s(" << r << ", " << n << ") is : " << val; return 0;} |
Java
// Java program to implement// above approachimport java.io.*;class GFG {// Calculating factorial of // an integer n.static long factorial(int n){ // Our base cases of factorial // 0! = 1! = 1 if (n == 0) return 1; // n can't be less than 0. if (n < 0) return -1; long res = 1; for (int i = 2; i < n + 1; ++i) res *= i; return res;}// Function to compute the number // of combination of r objects // out of n objects.static int nCr(int n, int r){ // r cant be more than n so // we'd like the program to // crash if the user entered // wrong input. if (r > n) return -1; if (n == r) return 1; if (r == 0) return 1; return nCr(n - 1, r - 1) + nCr(n - 1, r);}// Function to calculate the Stirling // numbers. The base cases which were // discussed above are handled to stop// the recursive calls.static long stirlingNumber(int r, int n){ // n can't be more than // r, s(r, 0) = 0. if (n > r) return -1; if (n == 0) return 0; if (r == n) return 1; if (n == 1) return factorial(r - 1); if (r - n == 1) return nCr(r, 2); else return stirlingNumber(r - 1, n - 1) + (r - 1) * stirlingNumber(r - 1, n);}// Driver Codepublic static void main (String[] args) { // Calculating the stirling number s(9, 2) int r = 9, n = 2; long val = stirlingNumber(r, n); if (val == -1) System.out.println(" No stirling number"); else System.out.println( "The Stirling Number s(" + r + ", " + n + ") is : " + val);}}// This Code is Contributed by anuj_67 |
Python 3
# Python 3 program to implement above approach# Function to compute the number of combination# of r objects out of n objects.# nCr(n, n) = 1, nCr(n, 0) = 1, and these are# the base cases.def nCr(n, r): if(n == r): return 1 if(r == 0): return 1 # nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r) return nCr(n - 1, r - 1) + nCr(n - 1, r) # This function is used to calculate the # factorial of a number n. def factorial(n): res = 1 # 1 ! = 0 ! = 1 if(n <= 1): return res for i in range(1, n + 1): res *= i return res # Main function to calculate the Stirling numbers.# the base cases which were discussed above are# handled to stop the recursive call, n can't be# more than r, s(r, 0) = 0.# s(r, r) = 1. s(r, 1) = (r - 1)!.# s(r, r - 1) = nCr(r, 2)# else as we proved, s(r, n) = s(r - 1, n - 1) # + (r - 1) * s(r - 1, n) def stirlingNumber(r, n): if(r == n): return 1 if(n == 0): return 0 if(n == r -1): return nCr(r, 2) if(r - n == 1): return factorial(r - 1) return (stirlingNumber(r - 1, n - 1) + (r - 1) * stirlingNumber(r - 1, n)) r, n = 9, 2print(stirlingNumber(r, n)) |
C#
// C# program to implement// above approachusing System;class GFG {// Calculating factorial of // an integer n.static long factorial(int n){ // Our base cases of factorial // 0! = 1! = 1 if (n == 0) return 1; // n can't be less than 0. if (n < 0) return -1; long res = 1; for (int i = 2; i < n + 1; ++i) res *= i; return res;}// Function to compute the number // of combination of r objects // out of n objects.static int nCr(int n, int r){ // r cant be more than n so // we'd like the program to // crash if the user entered // wrong input. if (r > n) return -1; if (n == r) return 1; if (r == 0) return 1; return nCr(n - 1, r - 1) + nCr(n - 1, r);}// Function to calculate the Stirling // numbers. The base cases which were // discussed above are handled to stop// the recursive calls.static long stirlingNumber(int r, int n){ // n can't be more than // r, s(r, 0) = 0. if (n > r) return -1; if (n == 0) return 0; if (r == n) return 1; if (n == 1) return factorial(r - 1); if (r - n == 1) return nCr(r, 2); else return stirlingNumber(r - 1, n - 1) + (r - 1) * stirlingNumber(r - 1, n);}// Driver Codepublic static void Main () { // Calculating the stirling // number s(9, 2) int r = 9, n = 2; long val = stirlingNumber(r, n); if (val == -1) Console.WriteLine(" No stirling number"); else Console.WriteLine( "The Stirling Number s(" + r + ", " + n + ") is : " + val);}}// This code is contributed by inder_verma.. |
Javascript
<script>// js program to implement above approach// Calculating factorial of an integer n.function factorial( n){ // Our base cases of factorial 0! = 1! = 1 if (n == 0) return 1; // n can't be less than 0. if (n < 0) return -1; let res = 1; for (let i = 2; i < n + 1; ++i) res *= i; return res;}// Function to compute the number of combination// of r objects out of n objects.function nCr(n, r){ // r cant be more than n so we'd like the // program to crash if the user entered // wrong input. if (r > n) return -1; if (n == r) return 1; if (r == 0) return 1; // nCr(n, r) = nCr(n - 1, r - 1) + nCr(n - 1, r) return nCr(n - 1, r - 1) + nCr(n - 1, r);}// Function to calculate the Stirling numbers.// The base cases which were discussed above are handled// to stop the recursive calls.function stirlingNumber( r, n){ // n can't be more than // r, s(r, 0) = 0. if (n > r) return -1; if (n == 0) return 0; if (r == n) return 1; if (n == 1) return factorial(r - 1); if (r - n == 1) return nCr(r, 2); else return stirlingNumber(r - 1, n - 1) + (r - 1) * stirlingNumber(r - 1, n);}// Driver program// Calculating the stirling number s(9, 2) let r = 9, n = 2; let val = stirlingNumber(r, n); if (val == -1) document.write( " No stirling number"); else document.write( "The Stirling Number s(", r , ", " , n , ") is : " , val);</script> |
PHP
<?php// PHP program to implement above approach// Calculating factorial of an integer n.function factorial($n){ // Our base cases of factorial 0! = 1! = 1 if ($n == 0) return 1; // n can't be less than 0. if ($n < 0) return -1; $res = 1; for ($i = 2; $i < $n + 1; ++$i) $res *= $i; return $res;}// Function to compute the number of combination// of r objects out of n objects.function nCr($n, $r){ // r cant be more than n so we'd like the // program to crash if the user entered // wrong input. if ($r > $n) return -1; if ($n == $r) return 1; if ($r == 0) return 1; // nCr($n, $r) = nCr($n - 1, $r - 1) + nCr($n - 1, $r) return nCr($n - 1, $r - 1) + nCr($n - 1, $r);}// Function to calculate the Stirling numbers.// The base cases which were discussed above are handled// to stop the recursive calls.function stirlingNumber($r, $n){ // n can't be more than // r, s(r, 0) = 0. if ($n > $r) return -1; if ($n == 0) return 0; if ($r == $n) return 1; if ($n == 1) return factorial($r - 1); if ($r - $n == 1) return nCr($r, 2); else return stirlingNumber($r - 1, $n - 1) + ($r - 1) * stirlingNumber($r - 1, $n);} // Calculating the stirling number s(9, 2) $r = 9; $n = 2; $val = stirlingNumber($r, $n); if ($val == -1) echo " No stirling number"; else echo "The Stirling Number s(", $r ,", " , $n , ") is : " , $val; // This code is contributed by ANKITRAI1?> |
Output
The Stirling Number s(9, 2) is : 109584
Time Complexity : O(r * n)
Auxiliary Space : O(r * n)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
// C++ code for above approach#include <iostream>#include <vector>using namespace std;// Function to calculate factorial of an integer nlong long factorial(int n){ // Base case: 0! and 1! = 1 if (n == 0 || n == 1) return 1; // Compute the factorial using a loop long long res = 1; for (int i = 2; i <= n; ++i) { res *= i; } return res;}// Function to calculate the Stirling numbers using DP// tabulationlong long stirlingNumber(int r, int n){ // Create a 2D array to store the Stirling numbers vector<vector<long long> > dp( n + 1, vector<long long>(r + 1, 0)); // Fill in the base cases for (int i = 0; i <= n; i++) { dp[i][i] = 1; } for (int i = 1; i <= r; i++) { dp[1][i] = factorial(i - 1); } // Fill in the rest of the table using a loop for (int i = 2; i <= n; i++) { for (int j = 2; j <= r; j++) { dp[i][j] = dp[i - 1][j - 1] + (j - 1) * dp[i][j - 1]; } } // Return the computed value return dp[n][r];}// Driver Codeint main(){ // Calculating the stirling number s(9, 2) int r = 9, n = 2; long long val = stirlingNumber(r, n); if (val == -1) cout << " No stirling number"; else cout << "The Stirling Number s(" << r << ", " << n << ") is : " << val; return 0;} |
Java
import java.util.Arrays;public class StirlingNumbers { // Function to calculate factorial of an integer n public static long factorial(int n) { // Base case: 0! and 1! = 1 if (n == 0 || n == 1) { return 1; } // Compute the factorial using a loop long res = 1; for (int i = 2; i <= n; ++i) { res *= i; } return res; } // Function to calculate the Stirling numbers using DP // tabulation public static long stirlingNumber(int r, int n) { // Create a 2D array to store the Stirling numbers long[][] dp = new long[n + 1][r + 1]; // Fill in the base cases for (int i = 0; i <= n; i++) { dp[i][i] = 1; } for (int i = 1; i <= r; i++) { dp[1][i] = factorial(i - 1); } // Fill in the rest of the table using a loop for (int i = 2; i <= n; i++) { for (int j = 2; j <= r; j++) { dp[i][j] = dp[i - 1][j - 1] + (j - 1) * dp[i][j - 1]; } } // Return the computed value return dp[n][r]; } // Driver Code public static void main(String[] args) { // Calculating the Stirling number s(9, 2) int r = 9, n = 2; long val = stirlingNumber(r, n); if (val == -1) System.out.println("No Stirling number"); else System.out.println("The Stirling Number s(" + r + ", " + n + ") is : " + val); }} |
Python3
def factorial(n): # 0! and 1! = 1 if n == 0 or n == 1: return 1 # Compute the factorial using a loop res = 1 for i in range(2, n + 1): res *= i return resdef stirling_number(r, n): # Create a 2D list to store the Stirling numbers dp = [[0] * (r + 1) for _ in range(n + 1)] # Fill in the base cases for i in range(n + 1): dp[i][i] = 1 for i in range(1, r + 1): dp[1][i] = factorial(i - 1) # Fill in the rest of the table using a loop for i in range(2, n + 1): for j in range(2, r + 1): dp[i][j] = dp[i - 1][j - 1] + (j - 1) * dp[i][j - 1] # Return the computed value return dp[n][r]# Driver Codeif __name__ == "__main__": # Calculating the Stirling number s(9, 2) r = 9 n = 2 val = stirling_number(r, n) if val == -1: print("No Stirling number") else: print(f"The Stirling Number s({r}, {n}) is: {val}") |
Output
The Stirling Number s(9, 2) is : 109584
Time Complexity : O(r * n)
Auxiliary Space : O(r * n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
