Problem Statement

Stirling numbers of the first kind, or Stirling cycle numbers, count permutations according to their number of cycles (counting fixed points as cycles of length one). They may be defined directly to be the number of permutations of n elements with k disjoint cycles. Stirling numbers of the first kind express coefficients of polynomial expansions of falling or rising factorials. Depending on the application, Stirling numbers of the first kind may be "signed" or "unsigned". Signed Stirling numbers of the first kind arise when the polynomial expansion is expressed in terms of falling factorials; unsigned when expressed in terms of rising factorials. The only substantial difference is that, for signed Stirling numbers of the first kind, values of S1(n, k) are negative when n + k is odd. Stirling numbers of the first kind follow the simple identities:

Let's start with the solution:

import sequtils, strutils

proc s1(n, k: Natural): Natural =
  if k == 0: return ord(n == 0)
  if k > n: return 0
  s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k)

echo " k        ", toSeq(0..12).mapIt(($it).align(2)).join("        ")
echo " n"
for n in 0..12:
  stdout.write ($n).align(2)
  for k in 0..n:
    stdout.write ($s1(n, k)).align(10)
  stdout.write '\n'


import tables
import bignum

var cache: Table[(Natural, Natural), Int]

proc s1(n, k: Natural): Int =
  if k == 0: return newInt(ord(n == 0))
  if k > n: return newInt(0)
  if (n, k) in cache: return cache[(n, k)]
  result = s1(n - 1, k - 1) + (n - 1) * s1(n - 1, k)
  cache[(n, k)] = result

var max = newInt(-1)
for k in 0..100:
  let s = s1(100, k)
  if s > max: max = s
  else: break

echo "Maximum Stirling number of the first kind with n = 100:"
echo max