4
$\begingroup$

Suppose $N>m$, denote the number of ways to be $W(N,m)$

First method

Take $m$ balls out of $N$, put one ball at each bucket. Then every ball of the left the $N-m$ balls can be freely put into $m$ bucket. Thus we have: $W(N,m)=m^{N-m}$.

Second method

When we are going to put $N$-th ball, we are facing two possibilities:

  1. the previous $N-1$ balls have already satisfies the condition we required, i.e. each of $m$ buckets has at least one ball. Therefore, we can put the $N$-th ball into any bucket.

  2. the previous $N-1$ balls have made $m-1$ buckets satisfies the condition, we are left with one empty bucket, the $N$-th ball must be put into that empty bucket. However, that empty bucket may be any one of the $m$ buckets.

Therefore, we have the recursion formula:

$$ W(N,m) = m W(N-1,m) + m W(N-1,m-1) $$

It is obvious that the two methods are not identical, which one has flaws? I would like to know which part of the reasoning is wrong and I would also want to hear about the case when the balls are distinct.

$\endgroup$
  • $\begingroup$ Why would there be an empty bucket for the N-th ball ? $\endgroup$ – Astyx Nov 5 '16 at 14:44
  • $\begingroup$ That is a possible situation before putting $N$-th ball $\endgroup$ – fizis Nov 5 '16 at 14:47
  • $\begingroup$ But then there could also be 2 empty buckets, or 3 empty buckets ... couldn't there ? $\endgroup$ – Astyx Nov 5 '16 at 14:49
  • $\begingroup$ @Astyx you can't fill two empty buckets with a single ball. $\endgroup$ – fizis Nov 5 '16 at 14:52
7
$\begingroup$

First put $1$ ball into each of $m$ buckets.

Then you are left with $N-m$ balls.

Use stars and bars method. Arrange the remaining balls in a row. Add $m-1$ dividers. Compute number of ways to arrange the balls and dividers.

Number of ways is given by =$$\binom {(N-m)+(m-1)}{m-1}=\binom{N-1}{m-1}$$

$\endgroup$
  • $\begingroup$ you mean first is wrong? $\endgroup$ – fizis Nov 5 '16 at 15:04
  • $\begingroup$ That would appear to be the case. Try it for a small number, e.g. $N=5, m=3$ and see. $\endgroup$ – hypergeometric Nov 5 '16 at 15:07
  • 2
    $\begingroup$ Yes both methods are wrong $\endgroup$ – Astyx Nov 5 '16 at 15:10
  • $\begingroup$ @Astyx Do you really mean that? Does any one survive if the balls are distinct? If you can write a detailed answer about that, it would be great. $\endgroup$ – fizis Nov 5 '16 at 15:12
  • $\begingroup$ @fizis: If the balls are distinct, then the number of possible arrangements would be a Stirling number of the second kind. $\endgroup$ – Edward Nov 5 '16 at 15:21
3
$\begingroup$

hypergeometric has given a good analysis of the problem for indistinguishable balls.

When the balls are distinct, we can number them $1$ through $N$. If we number the buckets $1$ through $m$, each assignment of balls to buckets with at least one ball in each bucket can be thought of as a function from the set $[N]=\{1,\ldots,N\}$ onto the set $[m]=\{1,\ldots,m\}$. That is, we’re counting the surjections from $[N]$ to $[m]$.

The Stirling numbers of the second kind are the key ingredient here: the Stirling number ${N\brace m}$ is the number of partitions of $[N]$ into $m$ non-empty parts. There are $m!$ ways to assign each of the parts to one of the $m$ numbers in $[m]$, so there are $m!{N\brace m}$ surjections from $[N]$ to $[m]$ and hence the same number of allowable assignments of the labelled balls to the labelled buckets. It turns out that

$$m!{N\brace m}=\sum_{k=0}^m(-1)^{m-k}\binom{m}kk^N\;,$$

a result that can also be obtained directly using the inclusion-exclusion principle. There is no really nice closed form for this number, though the Stirling numbers themselves do satisfy a fairly nice recurrence:

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}\;,$$

with ${0\brace 0}=1$ and ${n\brace 0}={0\brace n}=0$ for $n>0$.

$\endgroup$
  • $\begingroup$ How can we have the summation formula from the recursion formula? $\endgroup$ – fizis Nov 6 '16 at 3:05
  • $\begingroup$ @fizis: That isn't how I would get it; the inclusion-exclusion argument is definitely the way to go. $\endgroup$ – Brian M. Scott Nov 6 '16 at 3:21
  • $\begingroup$ Alright, I will look into it. $\endgroup$ – fizis Nov 6 '16 at 3:33
  • 1
    $\begingroup$ Thank you - very kind of you :) Nice answer, extending this to distinct balls. (+1) $\endgroup$ – hypergeometric Nov 6 '16 at 16:41
0
$\begingroup$

The mistake comes form the fact that the two possibilities of the second method are not disjoint.

For instance when putting the 6-th ball in a set of three buckets, if you have $(1,2,2)$ you can get $(2,2,2)$, or $(1,3,2)$ or $(1,2,3)$.

If you had $(0, 3, 2)$ you need to get $(1,3,2)$ which is a way that has already been counted in the previous case.

$\endgroup$
  • $\begingroup$ you mean second is wrong? $\endgroup$ – fizis Nov 5 '16 at 15:04
  • $\begingroup$ Yes, this is what I mean $\endgroup$ – Astyx Nov 5 '16 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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