# Determining the number of arrangements (complicated)

• I
• elegysix
In summary, the problem at hand involves finding the number of arrangements of N rocks in K buckets of S{k} sizes, where the order of filling does not matter and the rocks are indistinguishable. This problem is related to partition theory and Young's tableaux. While there is no known formula for this problem, an algorithm can be used to find the total number of arrangements in O(kN) time. Additionally, the Hardy-Ramanujan approximation in partition theory and Euler's partition function can provide insight into this problem.
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}

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.

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.

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

SrayD said:
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.

mfb said:
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.

Empty buckets are ok.

mfb said:
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.

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

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.

## 1. How do you determine the number of arrangements for a given set of objects?

The number of arrangements for a given set of objects can be determined by using the formula n!/(n-r)!, where n is the total number of objects and r is the number of objects in each arrangement. This formula is often used in combination with permutation or combination formulas, depending on the specific requirements of the arrangement.

## 2. What is the difference between an arrangement and a permutation?

An arrangement is a specific ordering of a set of objects, while a permutation is a specific selection of a set of objects. In other words, an arrangement considers the order in which the objects are placed, while a permutation considers the specific objects chosen for the arrangement.

## 3. How do you incorporate repetition into determining the number of arrangements?

If repetition is allowed in the arrangement, the formula n^r is used, where n is the number of objects and r is the number of objects in each arrangement. This formula is commonly used in situations where objects can be repeated, such as in a combination lock or a password.

## 4. What is the significance of determining the number of arrangements in scientific research?

Determining the number of arrangements is important in scientific research as it allows for the prediction and analysis of potential outcomes. By understanding the different arrangements and their probabilities, researchers can make informed decisions and draw conclusions about their experiments or data.

## 5. Are there any real-life applications of determining the number of arrangements?

Yes, there are many real-life applications of determining the number of arrangements. Some examples include designing experiments, predicting outcomes in games or sports, and analyzing data in fields such as genetics and statistics. It is also used in various industries such as computer science, finance, and engineering to optimize processes and systems.

• General Math
Replies
6
Views
1K
• General Math
Replies
2
Views
1K
• General Math
Replies
2
Views
1K
• General Math
Replies
7
Views
2K
• General Math
Replies
7
Views
1K
• General Math
Replies
3
Views
993
• General Math
Replies
1
Views
1K
• Programming and Computer Science
Replies
1
Views
1K
• Calculus
Replies
11
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K