I How many piles given n identical rocks?

  • I
  • Thread starter Thread starter member 428835
  • Start date Start date
  • Tags Tags
    Rocks
AI Thread Summary
The discussion focuses on techniques to determine the number of piles, denoted as p, that can be formed with n identical rocks. Participants explore the relationship between n and p, noting specific cases where p equals 1, 2, 3, and 5 for n values of 1 through 4. The stars-and-bars method is suggested for distributing rocks into piles, though confusion remains about its application. A systematic grouping approach is proposed, demonstrating how to count partitions for n=7, resulting in 15 partitions. The conversation highlights the absence of a straightforward closed formula for this problem, with references to the Bell triangle as a potential aid.
member 428835
Is there a technique to count the amount of piles ##p## that can be made given ##n## identical rocks? We know ##n=1 \implies p=1##, ##n=2 \implies p=2##, ##n=3 \implies p=3##, ##n=4 \implies p=5##, and so on. I'm kind of lost as to how we approach it. It seems we have ##n## piles that we can distribute to, and we have ##n## "ones" we can distribute to the piles where each pile can have 0 to ##n## ones. I'd think something like stars-and-bars and somehow divide out the same scenarios, but I'm a little confused.
 
Physics news on Phys.org
joshmccraney said:
Is there a technique to count the amount of piles ##p## that can be made given ##n## identical rocks? We know ##n=1 \implies p=1##, ##n=2 \implies p=2##, ##n=3 \implies p=3##, ##n=4 \implies p=5##, and so on. I'm kind of lost as to how we approach it. It seems we have ##n## piles that we can distribute to, and we have ##n## "ones" we can distribute to the piles where each pile can have 0 to ##n## ones. I'd think something like stars-and-bars and somehow divide out the same scenarios, but I'm a little confused.
These are the partition numbers:

https://oeis.org/A000041
 
  • Informative
Likes Dale and DrClaude
joshmccraney said:
Is there a technique to count the amount of piles ##p## that can be made given ##n## identical rocks? We know ##n=1 \implies p=1##, ##n=2 \implies p=2##, ##n=3 \implies p=3##, ##n=4 \implies p=5##, and so on. I'm kind of lost as to how we approach it. It seems we have ##n## piles that we can distribute to, and we have ##n## "ones" we can distribute to the piles where each pile can have 0 to ##n## ones. I'd think something like stars-and-bars and somehow divide out the same scenarios, but I'm a little confused.
If you mean a technique to actually count, I start with piles of one using here an example of ##n=7##. Then systematically group into piles of 2 and then start over with a 3 group and 1's grouping by 2's again, then 3's and so forth. In each case you are simply moving a one left and adding it except each time you start with a larger grouping you go back to all ones for the rest.

1 1 1 1 1 1 1
2 1 1 1 1 1
2 2 1 1 1
2 2 2 1
3 1 1 1 1
3 2 1 1
3 2 2
3 3 1
4 1 1 1
4 2 1
4 3
5 1 1
5 2
6 1
7

giving 15 partitions. You can turn this into an algorithm.

Also, here is a Wolfram applet;

https://www.wolframalpha.com/widgets/view.jsp?id=ca10ab4a89d9f0f6f378b89881f63ba3
 
Last edited:
  • Like
Likes member 428835
I was surprised to learn there is no straightforward closed formula for this. Or even how many ways to do k piles with n rocks. It just seems odd that one can do low n cases in one's head but can't just write down a formula like permutations.
 
bob012345 said:
I was surprised to learn there is no straightforward closed formula for this. Or even how many ways to do k piles with n rocks. It just seems odd that one can do low n cases in one's head but can't just write down a formula like permutations.
Isn't the Bell triangle, while not a formula, a helpful approach?
 
joshmccraney said:
Isn't the Bell triangle, while not a formula, a helpful approach?
I'll look at that. Thanks.
 
Back
Top