2
$\begingroup$

I know that the Stirling cycle numbers $\left[{n}\atop{k}\right]$ and Stirling subset numbers $\left\{{n}\atop{k}\right\}$ both satisfy recursion relations on both $n$ and $k$:

$\left[{n}\atop{k}\right]=(n-1)\left[{n-1}\atop{k}\right]+\left[{n-1}\atop{k-1}\right]$

$\left\{{n}\atop{k}\right\}=k\left\{{n-1}\atop{k}\right\}+\left\{{n-1}\atop{k-1}\right\}$

and it is a simple matter to write a program for computing them when you have a two dimensional array available to you.

Is it possible to compute these numbers if all you can use is a one dimensional array (not of course counting the approach where a one dimensional array is treated as a two dimensional array with appropriate indexing)?

  • 0
    I'm not sure how to interpret the requirement that "appropriate indexing" is outlawed. If you have a 1d array that holds a function $S(n,k)$ of two parameters, of course you must somehow place each $S(n,k)$ at some position $m$ of the array - and as soon as you do that by picking any of your favorite indexing functions, translating the recurrence relations becomes a mere technicality.2011-06-22

2 Answers 2

3

The Stirling number of the second kind can be calculated efficiently using the identity $\left\{ n\atop{k} \right\} = \frac1{k!} \sum_{j=0}^k (-1)^j \binom{k}{j} (k-j)^n.$

3

Hmm, my interpretation of "all you can use is a one dimensional array (not of course counting the approach where a one dimensional array is treated as a two dimensional array with appropriate indexing)?" would be the one where you store rows (or columns) consecutively, like {a[1,1], a[1,2] ,a[1,3], a[2,1], a[2,2], a[2,3]} to represent a 2-by-3 array...

Anyway, on to the task at hand: if you set up the necessary triangles, you find that the recursion forms an "L-shape" of sorts in the triangle; you can in fact set things up such that $\left[{n}\atop{k}\right]$ overwrites $\left[{n-1}\atop{k}\right]$, but you'll have to maintain a temporary variable to hold $\left[{n-1}\atop{k-1}\right]$.

Here for instance is Mathematica code for the Stirling cycle number (essentially, Abs[StirlingS1[n, k]]):

sCycle[n_Integer, k_Integer] := Module[{a = PadRight[{1}, k], s, v, w},     s = Boole[k <= n];     If[s == 1,         s = Boole[k > 0 || k == n];         If[0 < k < n,             Do[                 w = a[[1]]; a[[1]] = i w;                 Do[                     v = a[[j]];                     a[[j]] = w + i v;                     w = v;                 , {j, 2, Min[i, k]}];                 If[i < k, a[[i + 1]] = 1];             , {i, n - 1}];             s = a[[k]];     ];];     s ] 

(this should be easily translatable to your favorite language.)

Writing a version of this algorithm for the Stirling subset number is left as an exercise. (Or, use the formula mentioned by Fabian.)