Undergrad How many piles given n identical rocks?

[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.

 

[PeroK]

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

 

[bob012345]

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

 

[bob012345]

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.

 

[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.

Isn't the Bell triangle, while not a formula, a helpful approach?

 

[bob012345]

Isn't the Bell triangle, while not a formula, a helpful approach?

I'll look at that. Thanks.