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