Number of unique ways of stacking n blocks

[hello95]

Hello,

I was wondering if this problem is one that is solvable, and if so, if I would be able to solve it in a reasonable amount of time.

Basically, say you have n blocks. You can arrange this blocks in stacks, so for example, if you had 3 blocks, you could make a stack of 2, and then add a stack of 1. The question is, for these n blocks, how many unique ways are there of arranging them in stacks (the order is irrelevant). I got the idea from a theorem in abstract algebra, which says that a finite abelian group is isomorphic to the direct product of cyclic groups with orders equal to some integral power of a prime. Since such a direct product would be isomorphic to a cyclic group equal to the product of all of the prime power orders, then I could find a way to represent all of the possible forms of a cyclic group of order (2^7)(5^2) by simply taking the number of ways of stacking 7 blocks and multiplying it by the number of ways of stacking 2 blocks.

Another way of looking at the problem would be, if you have n star symbols (*), how many ways would there be of grouping certain numbers of those stars together so that the sum of all of the elements in all of the groupings equaled n:

(*)(*)(*)(*), (**)(**), (*)(***), (****)

Once again, order is irrelevant.

If you know the answer, please do not post it. Ultimately I just want to know if this problem is feasible for someone with a decent knowledge (but my no means expansive) of combinatorics to attempt.

Thank you.

 

[hello95]

If any further explanation is needed, please let me know.

 

[Number Nine]

If order is irrelevant, this strikes me as being equivalent to asking for the number of partitions of n. A google search for "integer partitions" should reveal plenty of information.

 

[hello95]

Thank you! that's exactly what I was looking for.

 

[blue_raver22]

Hello,

Thank you for your question. The problem you have described is known as the "partition problem" or "integer partition problem" in mathematics. It is a well-studied problem in combinatorics and there are multiple methods for solving it. One approach is to use generating functions, which involve representing the problem as a polynomial and using mathematical techniques to find the coefficients of the polynomial. Other methods involve using recursion or dynamic programming.

The number of unique ways of stacking n blocks can also be expressed as the number of partitions of n, denoted by p(n). For small values of n, this can be calculated manually, but for larger values, it becomes more challenging. For example, p(10) = 42, p(20) = 627, and p(30) = 5604.

In general, the partition problem is considered to be a difficult problem and there is no known formula or algorithm that can solve it efficiently for all values of n. However, there are algorithms that can provide approximate solutions or bounds on the number of partitions.

I would say that this problem is feasible for someone with a decent knowledge of combinatorics to attempt, but it may require some advanced techniques and mathematical knowledge. I would recommend researching the partition problem further and exploring different methods for solving it. Good luck!