Enumerating cyclical decompositions with Stirling numbers


This whole enumeration nightmare-miniseries started off with Stirling numbers of the second kind. But what about Stirling numbers of the first kind? Those things ain't gonna enumerate themselves!

The traditional formulation of the recursion for Stirling numbers of the first kind (unsigned version, since it's hard to enumerate negative numbers) goes like this:

c(n + 1, k) = n · c(n, k) + c(n, k − 1).

although it is more convenient from a programming standpoint to rewrite it as

c(n, k) = (n − 1) · c(n − 1, k) + c(n − 1, k − 1).

The Wikipedia article explains the combinatorial interpretation, which is what we will use to enumerate all the possibilities.

  • The first term says that we recursively generate the ways of decomposing n − 1 items into k cycles, then insert element n in one of n − 1 ways.

  • The second term says that we recursively generate the ways of decomposing n − 1 items into k − 1 cycles, then add a singleton cycle of just n.
function Stirling1(n, k, f) {
 if (n == 0 && k == 0) { f([]); return; }
 if (n == 0 || k == 0) { return; }

 // second term
 Stirling1(n-1, k-1, function(s) { f(s.concat([[n]])); });

 // first term
 Stirling1(n-1, k, function(s) {
  for (var i = 0; i < s.length; i++) {
   for (var j = s[i].length; j > 0; j--) {
    f(s.map(function(e, index) {
     return i == index ? e.slice(0, j).concat(n, e.slice(j)) : e;
    }));
   }
  }
 });
}

Stirling1(5, 3, function(s) { console.log(JSON.stringify(s)); });

The inner loop could just as easily gone

   for (var j = 0; j < s[i].length; j++) {

but I changed the loop control for style points. (It makes the output prettier.)

Comments (11)
  1. Al go says:

    Enough of this series.

    [I have issued a full refund to your account. -Raymond]
  2. Joshua says:

    So sad really. I don't see a good reason why Raymond can't talk about what he wants to talk about on his own blog.

  3. Womble says:

    The change to the j loop changes the bounds of the iteration. Are the references to j inside the loop modified to compensate? Or should they be (j-1)?

  4. @Womble

    msdn.microsoft.com/.../tkcsy6fe(v=vs.94).aspx

    > The slice method copies up to, but not including, the element indicated by end.

    Perhaps Raymond could have made this clearer by using (j - 1) + 1 instead of j.

  5. Womble says:

    @Maurits - oh, cool - I'm not a Javascript coder. Definitely scores style points :-)

  6. Neil says:

    Do you need to stringify s before logging it?

  7. fhe says:

    >oh, cool - I'm not a Javascript coder

    Look out the window.

  8. DWalker says:

    For those people who don't have an immediate need for this knowledge in their daily lives, or their jobs: If you are at all interested in computer programming, it is ALWAYS worthwhile to see, and ruminate on, how various mathematical concepts translate into computer code.  You may learn some techniques that you can apply to other problems.

  9. Steve D says:

    Perhaps if Al Go remembered to add a :-) his comment would make more sense?

  10. Drak says:

    @Neil: it makes it a lot more readable. If I recall correctly, just outputting an array in javascript will get you its contents separated by commas, but the contents in this case might all be 'object'. Not sure, and didn't test it, but with stringify you will always get a readable result :)

Comments are closed.

Skip to main content