# Stirling Numbers of the Second Kind

Stirling numbers of the second kind $S(k,n)$ measure the amount of ways in which $k$ objects can be divided into $n$ groups. (The groups can't be empty).

They obey the recurrence relation:

\begin{equation}
\left\{\begin{array}{c}k+1\\n\end{array}\right\} = n\left\{\begin{array}{c}k\\n\end{array}\right\} + \left\{\begin{array}{c}k\\n-1\end{array}\right\}
\end{equation}

The recurrence relation is explained by adding the combinations corresponding to two cases. If the $k+1$st object is added to one of the $n$ existing subsets with $k$ objects, then that corresponds to:

\begin{equation}
n\left\{\begin{array}{c}k\\n\end{array}\right\} = 1
\end{equation}

Possbilities. If the $k+1$st object is in a set by itself (a singleton), then the remaining objects are distributed over $n-1$ set. The combinations arising from this are:

\begin{equation}
\left\{\begin{array}{c}k\\n-1\end{array}\right\} = 1
\end{equation}

Furthermore, the following holds:

\begin{equation}
\left\{\begin{array}{c}0\\0\end{array}\right\} = 1
\end{equation}

\begin{equation}
\left\{\begin{array}{c}k\\0\end{array}\right\} = \left\{\begin{array}{c}0\\n\end{array}\right\} = 0
\end{equation}

And $S(k,n) = 0$ if $n>k$.

There is also an explicit formula:

\begin{equation}
S(k,n) = \frac{1}{n!}\sum_{i=1}^n (-1)^{n-j} {n \choose j}j^k
\end{equation}


```python
from time import time 


def timeit(func):
    """
    basic timer wrapper 
    """
    t0 = time() 
    def wrappingfunction(*args):
        return func(*args) 
    print('This took %1.10fs' % (time()-t0))
    return wrappingfunction


def memoize(func):
    """
    memoizing wrapper to speed up recursion by keeping track of previously calculated values.
    """
    S = {}
    def wrappingfunction(*args):
        if args not in S:
            S[args] = func(*args)
        return S[args]
    return wrappingfunction


@timeit
@memoize
def stirling(k,n):
    """
    calculate stirling numbers of the second kind
    """
    if n > k:
        return 0
    
    elif n == k:
        return 1
    
    elif n == 0 and k != 0:
        return 0
        
    else:
        return n*stirling(k-1,n)+stirling(k-1,n-1)
    

N = 14
for k in range(N):
    print('\t'.join(['%i' % stirling(k,n) for n in range(N)]))
        
```

    This took 0.0000009537s
    1	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	1	0	0	0	0	0	0	0	0	0	0	0	0
    0	1	1	0	0	0	0	0	0	0	0	0	0	0
    0	1	3	1	0	0	0	0	0	0	0	0	0	0
    0	1	7	6	1	0	0	0	0	0	0	0	0	0
    0	1	15	25	10	1	0	0	0	0	0	0	0	0
    0	1	31	90	65	15	1	0	0	0	0	0	0	0
    0	1	63	301	350	140	21	1	0	0	0	0	0	0
    0	1	127	966	1701	1050	266	28	1	0	0	0	0	0
    0	1	255	3025	7770	6951	2646	462	36	1	0	0	0	0
    0	1	511	9330	34105	42525	22827	5880	750	45	1	0	0	0
    0	1	1023	28501	145750	246730	179487	63987	11880	1155	55	1	0	0
    0	1	2047	86526	611501	1379400	1323652	627396	159027	22275	1705	66	1	0
    0	1	4095	261625	2532530	7508501	9321312	5715424	1899612	359502	39325	2431	78	1



```python
# explicit formula

import numpy as np

def factorial(x):
    if x == 0:
        return 1
    else:
        res = 1
        for i in range(1,x+1):
            res *= i
        return res
    
def binomial(n,k):
    return factorial(n)/(factorial(k)*factorial(n-k))

def stirling_2(k,n):
    return (1/factorial(n))*np.sum([(-1)**(n-j)*binomial(n,j)*j**k for j in range(n+1)])


N = 14
for k in range(N):
    print('\t'.join(['%i' % stirling_2(k,n) for n in range(N)]))
```

    1	0	0	0	0	0	0	0	0	0	0	0	0	0
    0	1	0	0	0	0	0	0	0	0	0	0	0	0
    0	1	1	0	0	0	0	0	0	0	0	0	0	0
    0	1	3	1	0	0	0	0	0	0	0	0	0	0
    0	1	7	6	1	0	0	0	0	0	0	0	0	0
    0	1	15	25	10	1	0	0	0	0	0	0	0	0
    0	1	31	90	65	15	1	0	0	0	0	0	0	0
    0	1	63	301	350	140	21	1	0	0	0	0	0	0
    0	1	127	966	1701	1050	266	28	1	0	0	0	0	0
    0	1	255	3025	7770	6951	2646	462	36	1	0	0	0	0
    0	1	511	9330	34105	42525	22827	5880	750	45	0	0	0	0
    0	1	1023	28501	145750	246730	179487	63987	11880	1155	54	1	0	0
    0	1	2047	86526	611501	1379400	1323652	627396	159027	22275	1704	66	1	0
    0	1	4095	261625	2532530	7508501	9321312	5715424	1899612	359502	39325	2431	78	0


d1c6819b31a0783455a9be2d22152e1c5c3ee289
ipynb
Jupyter Notebook
Combinatorics - Stirling Numbers of the Second Kind.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Combinatorics - Stirling Numbers of the Second Kind.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Combinatorics - Stirling Numbers of the Second Kind.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Qwen/Qwen-72B
1. YES
2. YES