DevBlogs
October 6th, 2014

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

Topics
Code

## Author

Raymond has been involved in the evolution of Windows for more than 30 years. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie-jeebies. The Web site spawned a book, coincidentally also titled The Old New Thing (Addison Wesley 2007). He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.