# Counting marbles.(partitions into n sumands)

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?

Regards.

-
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 : en.wikipedia.org/wiki/Partition_%28number_theory%29 – wece Mar 27 '13 at 21:18

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).
You want the number of partitions of $n$ Into $k$ parts. There is no easy formula, though there is a recurrence.
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