Subscribe via feed.

Balls and baskets

Posted by Chris on July 19, 2010 – 6:08 pm

n balls are thrown at k baskets. Each ball lands in a basket. How many ways are there for there to be at least one ball in each basket?

Note. The balls and baskets are distinct. However, the order that the balls are thrown/received  is unimportant.


This post is under “MathsChallenge” and has 31 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

31 Responds so far- Add one»

  1. 1. Nathan Said:

    The same as for the Maxwell-Boltzmann distribution of an ideal gas. This kind of ideal was used in constructing it.

  2. 2. Anonymous Said:

    n balls are thrown at k baskets. Each ball lands in a basket. How many ways are there for there to be at least one ball in each basket?

    if n is less than k then 0 condition for at least one ball in each basket is not met

    if n=k then k! each digit can be considered a basket

    if n> k then
    After all then first k balls are arranged then any of the k baskets are valid choices. i.e. no requirement to evenly distribute balls
    so
    k!*k^(n-k)

    e.g. for 4 balls 3 baskets (baskets ABC)
    3!*3^1=18

    1234
    ABCA
    ABCB
    ABCC

    ACBA
    ACBB
    ACBC

    BACA
    BACB
    BACC

    BCAA
    BCAB
    BCAC

    CABA
    CABB
    CABC

    CBAA
    CBAB
    CBAC

    Cam

  3. 3. Wizard of Oz Said:

    Assume that n > k.

    It all depends on whether the order of the balls landing is relevant. If not, then we can assume that the first k balls each land in a different basket so that we only have to consider the remaining n-k balls. These can all go into any basket so the answer here is k^(n-k).

    If the order does matter, then each of the above possibilities can occur in n! different ways, so the answer here would be n! * k^(n-k).

  4. 4. slavy Said:

    OK, there are many (actually 4 I think) different interpretations of the problem, and nobody so far considered any of them: both the boxes and the balls are non-distinguishable, only the balls are distinguishable, only the boxes are distinguishable, and both the balls and the boxes are distinguishable. All these four cases lead to completely different answers and solutions. Cam and Oz, assuming that the first k-balls go to different baskets means that you consider the balls non-distinguishable (exactly what “the order doesn’t matter” stays for in Oz’s post). But then, for the remaining n-k balls the order does matter and if one of them goes to basket A, and the other to basket B, you consider this different than if the first one is in basket B, and the second is in basket A. So this is a dangerous mixture of assumptions which (usually) leads to wrong answers.

    Regarding the cases – I don’t know which one exactly Chris wants. If we distinguish the balls, then we are in a pretty big trouble and the computations are very very ugly and lengthy (this is more intuition than deep analysis!).

    If we consider both the balls and the baskets non-distinguishable then the problem is equivalent to “how many ways are there to represent the number n as a sum of at least k positive integers” (here 2+1=1+2 are the same way!), or to “in how many ways we can write n-k as a sum of at most k positive integers?” (the full formulation of the last question is “with an additional zero summand”). For example, if n=k, then n-k=0 and it can be represented only as 0, which corresponds to only 1 solution – having 1 ball in each basket. If n=k+1, then 1=1+0 is again the unique solution which corresponds to: one basket with 2 balls and the remaining ones with only one in it. n-k=2 gives rise to 1+1+0 or 2+0 which is equivalent to: two baskets with 2 balls and the rest with one, or 1 basket with 3 balls and the rest with one. And so on. I haven’t computed the general formula, since it doesn’t seem very nice, either.

    The last case: if the baskets are distinguishable, but the balls not leads to an easy solution: Let us denote by a(1), a(2), a(k) the number of balls in the corresponding basket. So we have that each a(i) is greater or equal to 1, and that the sum of all the a(i)’s is exactly n. Now consider the new sequence b(i)=a(1)+a(2)+…+a(i) – the partial i-th sum of the original sequence. b is strictly monotonically increasing, and b(k)=n. Moreover, there is a bijection (one-to-one correspondence) between any increasing sequence with the above property and any ball distribution, namely a(1)=b(1) and a(i)=b(i)-b(i-1) for all i bigger than 1. But the cardinality of the second family is easy to find: since b(k)=n is fixed, then b(k-1) is less or equal to n-1, and since the sequence is monotonic, then we can take an arbitrary k-1-tuple of the first n-1 numbers and just order it. Hence the number of different outcomes in this case is simply n-1 choose k-1, or (n-1)!/(n-k)!(k-1)! (of course if n is greater or equal to k).

  5. 5. slavy Said:

    I just realized that there is a much simpler solution for the last case: (n-1 choose k-1)=(n choose k)-(n choose k-1) or out of all possibilities to put n balls into k baskets we subtract those, where all the balls are in at most k-1 baskets and at least one basket is empty…

  6. 6. slavy Said:

    … and I just realized what a big stupidity I wrote in the previous post :( Please, delete it when possible ;)

  7. 7. Wizard of Oz Said:

    Slavy, I considered the case of the baskets being non-distinguishable and the balls being firstly non-distinguishable, then distinguishable.
    My answers were k^(n-k) and n!*(k^(n-k))

    To go from non-distinguishable to distinguishable balls, simply multiply by the number of combinations of balls, which is n! That is what I did above.

    If we now consider distinguishable baskets, then we have k! combinations of these. So, I submit that we simply multiply my two answers above by k!.

    That is, k!*(k^(n-k)) and k!*n!*(k^(n-k)) respectively.

    I have an uncomfortable feeling that this is a completely wrong and over-simplified approach. But I never was much good at this combination theory stuff. So, here it is for the hell of it anyway.

  8. 8. Chris Said:

    Oh the dangers of taking problems from other sites!

    After studying the source, I conclude that the balls and baskets are distinguishable, but the order that the balls are thrown is irrelevant.

    e.g. there is only 1 way to throw n balls at 1 basket, and there are 6 ways to throw 3 balls at 2 baskets.

  9. 9. Karl Sharman Said:

    I was going to say k!^n!-1, but after reading all the above, I’m not going to say anything.

  10. 10. Wizard of Oz Said:

    Me neither. Scrub my previous answer – unless it happens to be right!

  11. 11. slavy Said:

    In this case I don’t know how simplified the answer should be made, but I think a correct (yet, still complicated) formula is: \sum_(m=0}^{k}(-1)^m(k \choose m)(k-m)^n, where I have used LaTeX notation for the formula.

  12. 12. Wizard of Oz Said:

    Something about rushing in where angels fear to tread comes to mind, nevertheless here goes:

    Again consider n > k only.

    If order is irrelevant then we can distribute the first k balls one into each basket, so we have n!/(n-k)! combinations of balls that can be selected. The baskets are distinguishable, so they can be shuffled in k! different ways. So, for the first part of the problem, i.e. one ball in each basket, we have n!*k!/(n-k)! combinations.

    We now have n-k balls left. There can be k^(n-k) arrangements of these between k baskets. But, again, the baskets can be shuffled in k! different ways. So, for this part of the problem we have k!*(k^(n-k)) combinations.

    So, the final answer (drum roll please) is:

    n!*(k!^2(n-k))/(n-k)!

    (Either drum roll or raspberry!)

  13. 13. Wizard of Oz Said:

    Definitely a raspberry. I made a complete hash of combining my two formulae.

    Let’s try again: n!*(k!^2)*(k^(n-k))/(n-k)!

  14. 14. jimimhim Said:

    n^k-n^(k-1)

  15. 15. slavy Said:

    The last two answers cannot be true because they don’t give the correct answer even for the two examples of Chris, when n=6 and k=1, or n=3 and k=2.

    I still don’t know if I have to try to simplify my formula and if this is possible (Chris?). However it leads to some nice equalities. For example, we know that if n=k the answer is k!, so if we plug this in my formula we get the:

    \sum_(m=0}^{k}(-1)^{m}(k \choose m)(k-m)^k=k!

    which I don’t think I knew before (but I have checked it up to 5 in order to be sure that my formula works). And actually, so far I don’t see other ways to prove that besides using the ball-basket problem, the general formula and the observation what the answer is when n=k.

  16. 16. Chris Said:

    Hi all. Sorry to have been absent for so long, I haven’t had any time time to spare. This one is far tougher than I had supposed, so I apologise for that. I posted in haste, just to get a new problem up. Well done all for spotting so quickly that this one is tough.

    The source site actually used the phrase, “how many ways are there for there to be at least one ball in each basket?” The solution there is recursive.

    I’m embarrassed to say that I can’t interpret slavy’s formulae (I have merely heard of LaTex and believe that it let’s you typeset proper looking maths equations).

    So here are a few numbers to permit checking.

      6 balls, 2 baskets => 62
      5 balls, 3 baskets => 150
      5 balls, 4 baskets => 240
    21 balls, 4 baskets => 4356217681200

  17. 17. slavy Said:

    OK – I will try to explain it for you :) You take alternating sums of combinations of s elements out of k, multiplied by (k-s) to the power of n. Derivation – we have n balls and k baskets, so there are k^n different possible ball distributions (each ball may go to each busket and each event is independent). But we need only those who doesn’t leave any basket empty. If we assume that the first basket is empty, then there are (k-1)^n possibilities (now for each ball we have only k-1 options). We have k baskets, so we multiply the above number by k and we have counted all the bad cases when at least one basket is empty. However, some cases have been counted more than once – for example those who put balls only in k-2 baskets – they have been counted twice (one time for the first empty basket, and one time for the second). Now we get rid of them by:(k choose 2)(k-2)^n (k chose 2 stays for the different ways to select 2 empty baskets out of k, and (k-2)^n is the number of possibilities in each of the cases) and we are sure that we are done with this case. And so on… This is the clasical “counting” argument used in most of the problems of this type (the mailman problem, etc.) The final formula is:
    k^n-k*(k-1)^n+(k choose 2)*(k-2)^n+…+((-1)^(k-1))*(k choose k-1)*1^n

  18. 18. slavy Said:

    Example: n=5, k=3:
    3^5-3*2^5+3*1^5=243-96+3=246-96=150

    n=6, k=2:
    2^6-2*1^6=64-2=62

    n=5, k=4:
    4^5-4*3^5+6*2^5-4*1^5=1024-972+192-4=1216-976=240

    The last test I don’t want to try – sorry ;)

  19. 19. slavy Said:

    If you still don’t like the explicit formula, there is another way to define the number, but this time implicitly. For given n balls and k baskets, denote the answer by a(n,k). Then we have the following recursive formula: a(n+1,k)=k*(a(n,k)+a(n,k-1))
    It is due to the fact that if the first k balls already form a legitimate ball distribution (i.e., all baskets are non-empty) then the n+1-st one can go in any of the k baskets, while if the first n balls do not form a legitimate distribution, the only chance adding one ball to give us an already admissible one is that only one of the k baskets is empty and the new ball should go there. Since, there are k different baskets here we have k choices for the empty one and no choice where the ball will go afterwords….

    This recursive formula, together with the obvious a(n,1)=1 and a(n,k)=0 if n<k will give us every number (of course after a reasonable amount of computations). The explicit expression for a(n,k) is exactly the one in my previous posts.

  20. 20. Wizard of Oz Said:

    Congratulations to slavy on getting the right answer, or at least the answer that agrees with the examples given.

    It looks to me that the first element, k^n, represents the ways that n distinguishable balls can be distributed in k indistinguishable baskets. If so, this approach contradicts post # 8 which says that both balls and baskets are distinguishable.

    That makes a big difference.

  21. 21. slavy Said:

    The baskets are distinguishable – for each ball we have exactly k different options. If the baskets were non-distinguishable than the first ball always goes to an empty basket and we have no choices there, the second goes either to an empty one, or to the same one as the first ball – 2 different options and so on. The number in this setting is significantly smaller!

  22. 22. Chris Said:

    Using slavy’s a(n,k), the source site gave:

    a(n,k) = k^n – sum(i = 1 to k-1, C(k,i) * a(n, i))
    Where C(k,i) is combinations of k things i at a time = k!/(k! * (k-i)!)

    I assume that slavy’s (k choose i) = C(k,i)

    I’ve been and am too busy to have a go myself. It sure does look hard. I posted it because the problem seems so simple.

    I believe (LOL) that slavy is on top of it though. I’ll hazard a guess that his formula at the end of post 17 is an expansion of the formula a few lines up. So, an unequivocal, well done to slavy.

    Gotta go.

  23. 23. slavy Said:

    Yes, Chris, you are right :) Of course , I assume that there is a mistype and C(k,i)=k!/(i!*(k-i)!) I don’t like their original formula, since you either give the explicit one which is of the same complexity (again there is a sum from 0 to k-1 and C(k,i) involved, but you don’t reffer to other unknown things as a(n,i) and you derive the answer directly after computation) or the simple recursive formula from my previous post which is much more condensed.

  24. 24. Wizard of Oz Said:

    I thought of going down to the local pool hall and trying out a few combinations on a table (16 balls and 6 pockets to choose from). Then I realised that I’d derived my formulae in posts 12 & 13 incorrectly. A lot of combinations would have been double-counted or worse.

    So (to invoke another ball-in-a-basket) slam dunk to slavy!

  25. 25. neo Said:

    n!/(n_k)!

  26. 26. neo Said:

    sorry..its n!/((n-k)!*k!)

  27. 27. Jamal Arkat Said:

    The following formula calculates the number of ways in which n different balls are assigned to k different baskets in a way that at least one ball is located in each basket:

    k n k-i
    ∑ k!/(i!*(k-i)!) * i * (-1)
    i=1

    It is difficult to explain the proof here. You can tast various alternatives for n and k.

  28. 28. Jamal Arkat Said:

    The following formula calculates the number of ways in which n different balls are assigned to k different baskets in a way that at least one ball is located in each basket:

    k n k-i
    ∑ k!/(i!*(k-i)!) * i * (-1)
    i=1

    It is difficult to explain the proof here. You can tast various alternatives for n and k.

  29. 29. Jamal Arkat Said:

    How can I type a mathematical formula here!!!!?

  30. 30. Chris Said:

    Hi Jamal. Sadly, this site doesn’t have special support for mathematical equations.

  31. 31. Jamal Arkat Said:

    Dear Chris
    I have typed the explicit form of the formula but it was changed when I submitted the text!

    k
    ∑ (k^n)*(k!/(i!*(k-i)!) * (-1)^(k-i)
    i=1

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0