Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.