# Computing Stirling cycle and subset numbers with minimal storage

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)?

-
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. – Alon Amit Jun 22 '11 at 6:20

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.)

-

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.$$

-