### Sterling numbers of the second order

I am sure once in a while you may have faced the problem of distributing n elements into k different groups. It does not seem rocket science but, do you know in how many different ways it can be done? Of course it is not a new problem a all, and here is where the Stirling numbers (of the second kind) come in handy: they tell you the ways of dividing n elements into k groups.

For the Code Jam problem "Square Fields" large dataset the numbers may seem discouraging as the number of alternatives for 15 elements are:

S2(15,1)=1

S2(15,2)=16383

S2(15,3)=2375101

S2(15,4)=42355950

S2(15,5)=210766920

S2(15,6)=420693273

S2(15,7)=408741333

S2(15,8)=216627840

S2(15,9)=67128490

S2(15,10)=12662650

S2(15,11)=1479478

S2(15,12)=106470

S2(15,13)=4550

S2(15,14)=105

But for the small dataset combinations are just a few after all:

S2(7,1)=1

S2(7,2)=63

S2(7,3)=301

S2(7,4)=350

S2(7,5)=140

S2(7,6)=21

So brute force would have worked nicely for the small dataset case but not so for the large one.

## 0 Comments:

Post a Comment

<< Home