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.

Comments

Popular posts from this blog

VFD control with Arduino using RS485 link

4xiDraw: Another pen plotter

One Arduino controlling two brushless DC motors