How many different ways you can distribute N (distinguishable) marbles into K boxes where each box should contain at least X marbles?

242 Views Asked by At

The boxes are distinguishable. Two distributions are considered different if there is at least one marble which is contained by different boxes in the distributions.

Example: 4 marbles, 2 boxes, where each box should contain at least 2 marbles. The answer is 6.

This is a programming challenge taken from here.

1

There are 1 best solutions below

1
On BEST ANSWER

The numbers you are looking for are called Associated Stirling numbers of the second kind. You have recursions for those. The only remaining thing is that you are asked for functions, not partitions, i.e., blocks are labeled. What do you have to multiply to get it all?

BtW, i recommend you generate inverse of factorials mod the prime and not Pascal recursion to generate combinatorial numbers.