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)?
 A: 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.$$
A: 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.)
