Take the 2-minute tour ×

Possible Duplicate:
What is the expression for putting $n$ indistinguishable balls into $k$ indistinguishable cells?

I think that this is quite basic, but I can't seem to get it:

Given $n>0$ identical oranges, and $k \leq n$ identical kids. In how many ways can I divide the oranges between the kids, when every kid gets at least one orange.

Notice that the kids are also identical! I.e it's not two different cases when we switch the amount of oranges between 2 kids.


share|improve this question

marked as duplicate by Gerry Myerson, joriki, Brian M. Scott, Zev Chonoles Jan 20 '12 at 16:13


are the oranges replaced after given to one kid or not? –  Bhargav Dec 21 '11 at 16:33
@168335 I'm not sure I understand what you mean by replaced.. There are $n$ oranges. after you decide to give $m$ to one of the kids, there are $n-m$ left. I hope that's answers your question –  IBS Dec 21 '11 at 16:35
This is an irrelevant comment, but you cannot distribute identical oranges, even less to identical kids. Say you want to give an orange to a kid, you grab for a first orange, but there isn't any first orange, they're all identical! Same problem with the kids. Anyway, for this kind of problem look at the Twelvefold Way. –  Marc van Leeuwen Dec 21 '11 at 18:09

1 Answer 1

I will add a discussion here, and also point you to this (Table 3.2 on page 17, 61 according to the typeset).

Define a partition of the integer $k$ into $n$ parts is a multiset of $n$ positive integers that add to $k$. We use $P(k; n)$ to denote the number of partitions of $k$ into $n$ parts. Thus $P(k; n)$ is the number of ways to distribute $k$ identical objects to $n$ identical recipients so that each gets at least one.

Please note that this $P(k; n)$ has no explicit formula. Also, this is exactly opposite to the notation. So, in your notation, it will be $P(n; k)$, the partition of $n$ oranges to $k$ kids.

share|improve this answer
