Stirling numbers of the second kind, or Stirling partition numbers, are the
number of ways to partition a set of n objects into k non-empty subsets. They are
closely related to Bell numbers, and may be derived from them.



Stirling numbers of the second kind obey the recurrence relation:

   S2(n, 0) and S2(0, k) = 0 # for n, k > 0
   S2(n, n) = 1
   S2(n + 1, k) = k * S2(n, k) + S2(n, k - 1)



Task

 Write a routine (function, procedure, whatever) to find Stirling numbers of the second kind. There are several methods to generate Stirling numbers of the second kind. You are free to choose the most appropriate for your language. If your language has a built-in, or easily, publicly available library implementation, it is acceptable to use that.
 Using the routine, generate and show here, on this page, a table (or triangle) showing the Stirling numbers of the second kind, S2(n, k), up to S2(12, 12). it is optional to show the row / column for n == 0 and k == 0. It is optional to show places where S2(n, k) == 0 (when k > n).
 If your language supports large integers, find and show here, on this page, the maximum value of S2(n, k) where n == 100.


See also

 Wikipedia - Stirling numbers of the second kind
 OEIS:A008277 - Stirling numbers of the second kind


Related Tasks

 Stirling numbers of the first kind
 Bell numbers
 Lah numbers


Imports System.Numerics
 
Module Module1
 
    Class Sterling
        Private Shared ReadOnly COMPUTED As New Dictionary(Of String, BigInteger)
 
        Private Shared Function CacheKey(n As Integer, k As Integer) As String
            Return String.Format("{0}:{1}", n, k)
        End Function
 
        Private Shared Function Impl(n As Integer, k As Integer) As BigInteger
            If n = 0 AndAlso k = 0 Then
                Return 1
            End If
            If (n > 0 AndAlso k = 0) OrElse (n = 0 AndAlso k > 0) Then
                Return 0
            End If
            If n = k Then
                Return 1
            End If
            If k > n Then
                Return 0
            End If
 
            Return k * Sterling2(n - 1, k) + Sterling2(n - 1, k - 1)
        End Function
 
        Public Shared Function Sterling2(n As Integer, k As Integer) As BigInteger
            Dim key = CacheKey(n, k)
            If COMPUTED.ContainsKey(key) Then
                Return COMPUTED(key)
            End If
 
            Dim result = Impl(n, k)
            COMPUTED.Add(key, result)
            Return result
        End Function
    End Class
 
    Sub Main()
        Console.WriteLine("Stirling numbers of the second kind:")
        Dim max = 12
        Console.Write("n/k")
        For n = 0 To max
            Console.Write("{0,10}", n)
        Next
        Console.WriteLine()
        For n = 0 To max
            Console.Write("{0,3}", n)
            For k = 0 To n
                Console.Write("{0,10}", Sterling.Sterling2(n, k))
            Next
            Console.WriteLine()
        Next
        Console.WriteLine("The maximum value of S2(100, k) = ")
        Dim previous = BigInteger.Zero
        For k = 1 To 100
            Dim current = Sterling.Sterling2(100, k)
            If current > previous Then
                previous = current
            Else
                Console.WriteLine(previous)
                Console.WriteLine("({0} digits, k = {1})", previous.ToString().Length, k - 1)
                Exit For
            End If
        Next
    End Sub
 
End Module