Given $m$ balls and $n$ baskets, in how many ways can we distribute the $m$ balls to the $n$ baskets when given that $n > m$ (the number of baskets is greater than the number of balls)?

So I said, that it does not differ if $n>m$ the solution is still ${n+m-1 \choose n-1}$, is that correct? I merely considered it as the number of solutions $x_1 + x_2 + ... + x_n = m$ when $0 \leq x_i$. Is that correct?

Also, as an addition:

In addition to the question, what if there can be only a maximum of one ball in each basket?

So I said, it is still the same $x_1 + x_2 + ... + x_n = m$ but this time $0 \leq x_i \leq 1$ and it is still the same solution. Is that correct?

  • $\begingroup$ For at most one ball per basket, yes, it is $0\le x_i\le 1$, but the formula that gives the count is (naturally) different. $\endgroup$ – André Nicolas May 14 '13 at 10:25
  • $\begingroup$ Oh, how do we look at it then? $\endgroup$ – TheNotMe May 14 '13 at 10:26

We assume the usual convention: the balls are indistinguishable, and the baskets are distinguishable.

For your first question, yes, it is precisely the formula you are familiar with.

When we are restricted to at most one ball per basket, then yes, we are counting the solutions of $x_1+x_2+\cdots+x_n=m$ with the restriction that for any $i$ we have $x_i=0$ or $x_i=1$.

But to me the easiest way to think of it is that we are choosing the $m$ baskets that will be lucky and get a ball. Or if you wish choosing the $i$ such that $x_i=1$. Or else think of it as forming an $n$-letter "word" made up of $m$ $1$'s and the rest $0$'s.

Whichever way one views it, this can be done in $\dbinom{n}{m}$ ways.


since there are not any restriction of putting any number of balls in a basket. so after putting every ball every basket will be available.

so for 1st ball there are n ways for 2nd ball n ways.....and for mth ball there are still n ways. so answer will be: $$n\times n\times n\times n\times ........m \,times$$ $$n^m$$

  • $\begingroup$ any changes is highly appreciated $\endgroup$ – iostream007 May 14 '13 at 10:31
  • $\begingroup$ Your answer is correct if we think of the balls as distinguishable (each has an ID number) and the baskets as distinguishable. The convention in this sort of problem is that the balls, unless the contrary is stated, are indistinguishable, while the baskets, unless the contrary is stated, are distinguishable! $\endgroup$ – André Nicolas May 14 '13 at 10:58
  • $\begingroup$ @AndréNicolas thanks for your suggestion $\endgroup$ – iostream007 May 14 '13 at 11:17

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.