Take the 2-minute tour ×
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.

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.

share|improve this question
1  
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. –  Bananarama 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
add comment

2 Answers

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|improve this answer
    
Here is another reference on partition functions that may interest you: dlmf.nist.gov/26.9 –  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. –  Bananarama Mar 27 '13 at 20:07
add comment

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

share|improve this answer
2  
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
add comment

Your Answer

 
discard

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.