Determining the number of arrangements (complicated)

[elegysix]

Suppose we have K buckets of differing sizes, so that each bucket can only hold a specific number of rocks, S{k}. Suppose then we are given a specific number of rocks N, which are indistinguishable from one another, and the order of filling doesn't matter. We want to know how many arrangements of N rocks in K buckets of S{k} sizes are possible.

For example

Lets say K is 3, and the sizes are S{1,2,3} = 3, 2, and 1 respectively, and we have N=6 rocks. There is only one possible arrangement in this case because all the buckets have to be filled, and we don't care about the order of filling and the rocks are indistinguishable. ( the arrangement is {3,2,1})Now to make things more complicated, let's say N=5. Then the possible arrangements are
{3,2,0}
{3,1,1}
{2,2,1}
so the answer is 3.

I've been scratching my head trying to figure out a way to calculate the number of arrangements when things get more complicated - say when K = 7, S{1,2,3...}=(10,2,6,10,2,6,10), and N = 16. The number grows very fast with K.

I've written an algorithm that creates all the combinations and then counts them to find the total, but I'm looking for a formula to check that the algorithm is in the ballpark. I'd appreciate any advice.

thanks for your time!

 

[jedishrfu]

This problem is related to partition theory:

https://en.wikipedia.org/wiki/Partition_(number_theory)

but it seems your twist is the bucket limit.

You could try a lot of examples and see if you can tease out the formula, if one exists, especially since you have an algorithm already. However, in many cases there is no formula only an approximation like the Hardy-Ramanujan approximation in partition theory or a generating function like Euler's partition function,

Also you might some insight into your problem by looking at the Young's tableaux and how you can cast it into that form:

https://en.wikipedia.org/wiki/Young_tableau

Anyway, these articles will give you a lot to explore.

Perhaps @Mark44, @Krylov or @micromass can provide a more succinct answer.

 

[SrayD]

Not sure I follow exactly, but in N=5 example, have [3,2,0]. Thought all buckets need filled?

 

[mfb]

Not sure I follow exactly, but in N=5 example, have [3,2,0]. Thought all buckets need filled?

I didn't interpret the problem that way, but it would lead to an equivalent problem with {2,1} buckets and 2 rocks, by starting with 1 rock in every bucket. So without loss of generality, we can allow empty buckets.

It is always possible to find an expression with k-1 nested sums, but that is not better than "going through all options". There is an approach that works in O(kN):

For the first bucket, for n=0 to n=N, record how many options there are to fill it with n stones. This will be 1 from 0 to S(k) or N, whatever is smaller.
For the first L buckets, for n=0 to n=N, record how many options there are to fill them with n stones, using the previous list for the previous L-1 buckets. Go through L=2 to L=k.

 

[SrayD]

I didn't interpret the problem that way, but it would lead to an equivalent problem with {2,1} buckets and 2 rocks, by starting with 1 rock in every bucket. So without loss of generality, we can allow empty buckets.

It is always possible to find an expression with k-1 nested sums, but that is not better than "going through all options". There is an approach that works in O(kN):

For the first bucket, for n=0 to n=N, record how many options there are to fill it with n stones. This will be 1 from 0 to S(k) or N, whatever is smaller.
For the first L buckets, for n=0 to n=N, record how many options there are to fill them with n stones, using the previous list for the previous L-1 buckets. Go through L=2 to L=k.

Yeah, after reading again I agree. Can have zero.

 

[elegysix]

Empty buckets are ok.

For the first bucket, for n=0 to n=N, record how many options there are to fill it with n stones. This will be 1 from 0 to S(k) or N, whatever is smaller.
For the first L buckets, for n=0 to n=N, record how many options there are to fill them with n stones, using the previous list for the previous L-1 buckets. Go through L=2 to L=k.

This is similar to the algorithm I've got. I like the idea, I will think more on this.

The closest thing I've found to this subject is multisets, but the function ##\left(\!\!{a\choose b}\!\!\right)## isn't quite right. I have included an image which is similar to the output list of arrangements from the algorithm. In the picture, each cell would be a bucket. the red represents a rock's presence. Moving down a line indicates how the algorithm moves one rock at a time in order to go through all the arrangements. The image is not perfect because multiple rocks in the same bucket are not represented.

 

[mfb]

Multisets don't have bucket size limits. The O(kN) algorithm should be fine for all practical purposes.

 

[SrayD]

Since your looking for a formula to test your algorithm, I'd go with what jedishrfu said about partitions. Where each term in the sum of a given partition is a bucket. A particular subset of all partitions of an N will give the exact answer, but no good way to pick this out; that I know of. But, Sterling's approx will give a decent upper bound, as it calculates total number of partitions as N approaches infinity. A modification to the formula could get you closer, but not sure on what that would be in general. I'd follow link jedishrfu gave, if haven't already.