This is a guide on how we can generate Stirling numbers using Python programming language.

**Stirling Number S(n,k) :**

A Stirling Number of the second kind, **S(n, k)**, is the number of ways of splitting “**n**” items in “**k”** non-empty sets.

The formula used for calculating Stirling Number is:

S(n, k) = k* S(n-1, k) + S(n-1, k-1)

**Example 1:**

If you want to split a group of 3 items into 2 groups where** {A, B, C}** are the elements, and **{Group 1}** and **{Group 2}** are two groups, you can split them are follows:

**{Group 1} {Group 2}**

**A, B C**

**A B, C**

**B A, C**

So, the number of ways of splitting 3 items into 2 groups = 3.

Therefore, the Stirling number , **S(3, 2) = 3**

**Example 2: **

If you want to split a group of 5 elements into 2 groups where **{A,B,C,D,E}** are the items and **{Group 1}** and **{Group 2}** are two groups, it can be done in a total of 7 ways. So,

**S(4, 2) = 7**

**Code:**

This is the code that I have written to generate Stirling Numbers.

# Stirling Algorithm # Cod3d by EXTR3ME # https://extr3metech.wordpress.com def stirling(n,k): n1=n k1=k if n<=0: return 1 elif k<=0: return 0 elif (n==0 and k==0): return -1 elif n!=0 and n==k: return 1 elif n<k: return 0 else: temp1=stirling(n1-1,k1) temp1=k1*temp1 return (k1*(stirling(n1-1,k1)))+stirling(n1-1,k1-1) print stirling(1,1) # Output = 1 print stirling(5,2) # Output = 15 print stirling(5,3) # Output = 25 print stirling(5,4) # Output = 10 print stirling(5,5) # Output = 1 print stirling(20,15) # Output = 452329200 #print stirling(30,10) # End of Code

**Note:** When the values of n and k are large , it will take longer to calculate. For example, I have hashed out print stirling(30, 10) , as it can take a while to calculate. You can always unhash it and test how long it takes to calculate in your computer. Feel free to leave any comments or feedback.

Hope this helps. You can always subscribe to my blog to get more updates! Happy Coding!

**ΞXΤЯ3МΞ**

Hi – I think there may be as easy way to speed it up. As this function is defined recursively, the function call make two functions calls which then make two and so on. The slowing is exponential. Here are some example times:

stirling(5,5) = 1. Calculated in 0.00000215 secs.

stirling(10,5) = 42525. Calculated in 0.00313711 secs.

stirling(15,10) = 12662650. Calculated in 0.04619098 secs.

stirling(20,15) = 452329200. Calculated in 0.25143695 secs.

stirling(25,20) = 6220194750. Calculated in 0.90307903 secs.

stirling(30,25) = 49402080000. Calculated in 2.50413704 secs.

stirling(30,24) = 2157580085700. Calculated in 18.38733101 secs.

stirling(30,23) = 71823880393200. Calculated in 121.74350500 secs.

You can create a decorator is cache or “memoize” the result of any function call, and the speed up is dramatic:

memoized stirling(5,5) = 1. Calculated in 0.00000286 secs.

memoized stirling(10,5) = 42525. Calculated in 0.00005388 secs.

memoized stirling(15,10) = 12662650. Calculated in 0.00004387 secs.

memoized stirling(20,15) = 452329200. Calculated in 0.00005889 secs.

memoized stirling(25,20) = 6220194750. Calculated in 0.00005698 secs.

memoized stirling(30,25) = 49402080000. Calculated in 0.00004697 secs.

memoized stirling(30,24) = 2157580085700. Calculated in 0.00005603 secs.

memoized stirling(30,23) = 71823880393200. Calculated in 0.00003886 secs.

The way I did this was to make a decorator function:

def memoize(func):

S = {}

def wrappingfunction(*args):

if args not in S:

S[args] = func(*args)

return S[args]

return wrappingfunction

and then did

@memoize

def stirling(n,k):

I have not tried it with other functions, but I think that the form the memoize decorator above is probably generally enough to be used in many different situations.

best wishes,

-Mark

Hi Mark, thanks a lot for visiting my blog and taking your time and effort to post the optimized code. I just checked it out and the performance is a whole lot better using the Memoization technique. I will be creating a post on Stirling Number Generation and others using this technique in the future. And once again, thank you for visiting my blog! 🙂

ΞXΤЯ3МΞ

The follow test gives an incorrect answer (according to http://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind):

>>> stirling(4, 2)

7

(should be 11)

Looking at the explicit formula from https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind you can also make it much faster by not doing it recursively:

from math import factorial

def binom(a,b):

return factorial(a) / (factorial(b)*factorial(a-b))

def stirling_fast(n,k):

if n<=0 or n!=0 and n==k:

return 1

elif k<=0 or n<k:

return 0

elif n==0 and k==0:

return -1

else:

s = sum((-1)**(k-j)*binom(k,j)*j**n for j in range(k+1))

return s / factorial(k)

@csl,

Thats great! Thanks a lot for sharing!

Regards,

ΞXΤЯ3МΞ