Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In how many ways can I divide a pile of n identical marbles into k piles of marbles such that each pile has at least one marble? The piles are not different. I tried to use combinations with repetition and then do some sort of recursive definition but I find it too complicated. Is there a simpler way to make sense of it?


share|cite|improve this question
What do you mean by "identical"? Equal sized? If so, then it's the number of divisors of $n$: $d = n - \phi(n) = \sigma_0(n)$. – Stahl Mar 27 '13 at 19:37
Are the marbles all different? If the piles are identical, then you assume $n=kl$ for some $l>0$, right? – Dennis Gulko Mar 27 '13 at 19:39
No, by identical i meant the piles are not labeled. – Carry on Smiling Mar 27 '13 at 19:46
This may help you : – wece Mar 27 '13 at 21:18
up vote 3 down vote accepted

First you have to place a marble in each pile. Since the marbles are all the same and we aren't counting piles differently, this simply removes $k$ marbles from the original $n$. Next, we have to take the remaining $n-k$ marbles and place them into the $k$ piles in some way. This is the same as counting the ways of partitioning $n-k$ as a sum of nonnegative integers, where the number of summands of the partition is less than or equal to $k$. In particular, the number of ways to place your marbles (call it $N$) will satisfy $N\leq p(n-k)$ (here $p(m)$ is the partition function seen in the wiki link). I'm not sure if there is a known closed form for the number of partitions of a number $n - k$ into $k$ or fewer summands; perhaps someone else with more experience in that area of number theory would be able to provide a reference or formula with that information (or even just confirm or deny existence of such a formula).

share|cite|improve this answer
Here is another reference on partition functions that may interest you: – Stahl Mar 27 '13 at 20:04
Yes, sublime. I was getting to the partition thing on my own after a while. Thank you very much Stahl. – Carry on Smiling Mar 27 '13 at 20:07

You want the number of partitions of $n$ Into $k$ parts. There is no easy formula, though there is a recurrence.

share|cite|improve this answer
You have to account for the piles being nonempty, since we're fixing the amount $k$ of piles. If we sum the ways he can do it for piles of size $k = 1$ up through $n$, then we will have the number of partitions of $n$, but for any given $k$ and $n >1$, the number in question will be strictly less than $p(n)$, as $n = \underbrace{1 + \ldots + 1}_{n\textrm{ times}} = n$ (and those certainly give different numbers of piles). – Stahl Mar 27 '13 at 20:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.