A “Stirling number of the second kind” is the number of ways to group/partition n items into k subsets. For example, the number of ways to group n=4 items into k=2 subsets is 7. Suppose the 4 items are a, b, c, d. Then S(4,2) = 7 and the seven groupings are: (a | bcd), (b | acd), (c | abd), (d | abc), (ab |cd), (ac | bd), and (ad | bc).

The value of S(n,k) gets astronomically large, very quickly. For example, S(100, 3) =

85,896,253,455,335,221,205,584,888,180,155,511,368,666,317,646

How did I compute this? I wrote a C# function. First, I got one of many math definitions for S(n,k) from Wikipedia:

To code a function that computes S(n,k) because the answers can be so big, I needed to use the C# BigInteger data type which is not visible by default to a C# program. The type lives in namespace System.Numerics. If you examine the equation above you can see you need a Factorial function (outside the summation), an integer Power function (used in two places), and a Choose function. The Choose(n,k) function returns the number of ways to choose k items from n items, where order does not matter. For example, Choose(4,2) = 6 because there are six ways to select 2 items from 4 items. Suppose the four items are q, r, s, t. Then the six ways are (q r), (q s), (q t), (r s), (r t), and (s t).

So, here’s Factorial:

static BigInteger Factorial(int n)
{
  if (n == 0) return 1;
  BigInteger ans = 1;
  for (int i = 1; i <= n; ++i)
    ans *= i;
  return ans;
}

Here’s a Power:

static BigInteger Power(int m, int p)
{
  // m raised to the pth power
  BigInteger result = 1;
  for (int i = 0; i < p; ++i)
    result = result * m;
  return result;
}

And here’s a Choose:

static BigInteger Choose(int n, int k)
{
  if (n < 0 || k < 0)
    throw new Exception("Negative argument in Choose");
  if (n < k) return 0; // special
  if (n == k) return 1; // short-circuit

  int delta, iMax;

  if (k < n - k) // ex: Choose(100,3)
  {
    delta = n - k;
    iMax = k;
  }
  else           // ex: Choose(100,97)
  {
    delta = k;
    iMax = n - k;
  }

  BigInteger ans = delta + 1;
  for (int i = 2; i <= iMax; ++i)
    ans = (ans * (delta + i)) / i;

  return ans;
}

The Choose function is not at all obvious, but that’s another topic. Putting it all together, here’s a C# method that computes S(n,k):

static BigInteger Stirling(int n, int k)
{
  BigInteger sum = 0;

  for (int j = 0; j <= k; ++j)
  {
    BigInteger a = Power(-1, k - j);
    BigInteger b = Choose(k, j);
    BigInteger c = Power(j, n);
    sum += a * b * c;
  }

  return sum / Factorial(k);
}

I called the function as

int n = 100;
in k = 3;
Console.WriteLine(Stirling(n, k));

All in all, an interesting function.