Number of ways to arrange n identical stones into piles

1.2k Views Asked by At

Given, there are $n$ stones which are identical. How many ways can the stones be arranged into piles.
Suppose if $n=4$, we can make one pile with $4$ stones or $2$ piles with $3,1$ or $2,2$ or $3$ piles with $1,1,2$ or $4$ piles with $1,1,1,1$. Therefore total $5$ ways.
Is there a recurrence relation for this problem?

2

There are 2 best solutions below

0
On

You are describing the partition function. There is a vast literature on it.

2
On

You’re talking about the number of partitions of a positive integer $n$. This MathWorld link may also be helpful. There are recurrences, but they’re not particularly nice.