~~Introduce with some toy problems/historical notes.~~ # Definition Let $n,k$ be natural numbers. > [!NOTE] Definition by partitions > The number of partitions of $[k]=\{ 1,2,\dots,k \}$ into $n$ non-empty parts, denoted $S(k,n)$ or $k\brace n$, is known as a Stirling number of the second of the kind (OEIS sequence [A008277](https://oeis.org/A008277)). By sorting the partitions of the set $[k]$ based on whether $\{ k \}$ is a part or not, we gain the following [[Recurrence relation for Stirling numbers of the second kind|recurrence relation]] for these numbers $S(k,n)=S(k-1,n-1)+nS(k-1,n).$ We use this to compute first few Stirling numbers in the table below. | k\n | 1 | 2 | 3 | 4 | 5 | 6 | | --- | --- | --- | --- | --- | --- | --- | | 1 | 1 | | | | | | | 2 | 1 | 1 | | | | | | 3 | 1 | 3 | 1 | | | | | 4 | 1 | 7 | 6 | 1 | | | | 5 | 1 | 15 | 25 | 10 | 1 | | | 6 | 1 | 31 | | 65 | 15 | 1 | We notice that - $S(k,k-1)= k(k-1)/2 = \binom{k}{2}$. - $S(k,2) = \frac{1}{2}(2^{k}-2) = 2^{k-1}-1$. - $S(k,k-2)=\binom{k}{3} + \frac{1}{2} \binom{k}{2}\binom{k-2}{2}$. Find bijective proof these. > [!Warning]- Spoiler > Contents # Properties **Relation to surjections**: As shown in [[Enumerating surjections between finite sets|enumerating surjections]], $S(k, n) = \frac{\#\text{Surj}(k, n)}{n!}=\frac{1}{n!}\sum_{j=0}^{n} (-1)^{n-j} j^{k} \binom{n}{j}.$ **Relation to Bell numbers**: Let $B_{k}$ be the number of partitions of $[k]$ into any number of parts then $B_{k} =\sum_{n=0}^{k} S(k,n)$and $B_{k}$ is known as a [[Bell Numbers|Bell number]] (the sum of the rows in the table above). **Relation to Stirling numbers of the first kind**: Let $(x)_{n}=x(x-1)\dots (x-n+1)$. Then $\{ 1, (x)_{1}, (x)_{2}, \dots,(x)_{k} \}$ form a basis of the vector space of (real) polynomials with degree at most $k$ (can be seen inductively). Then $S(k,n)$ are the coefficients of $x^k$ with respect to this basis: $x^{k} = \sum_{n=0}^{k} S(k,n) (x)_{n}$ This can be shown using the above recurrence and the fact that $(x)_{k+1}=(x)_{k}(x-k)$. TBC **Relation to differentiation**: $(xD)^n \;=\;\sum_{k=1}^n S(n,k)\,x^k D^k.$ # Bibliography