## 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.

July 19th, 2010 at 7:52 pm

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

July 19th, 2010 at 9:12 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?

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

July 19th, 2010 at 10:34 pm

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).

July 20th, 2010 at 3:03 am

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).

July 20th, 2010 at 3:15 am

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…

July 20th, 2010 at 3:19 am

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

July 20th, 2010 at 3:54 am

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.

July 20th, 2010 at 4:30 am

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.

July 20th, 2010 at 4:38 am

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

July 20th, 2010 at 4:44 am

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

July 20th, 2010 at 4:57 am

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.

July 20th, 2010 at 2:11 pm

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!)

July 20th, 2010 at 3:15 pm

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)!

July 20th, 2010 at 4:22 pm

n^k-n^(k-1)

July 21st, 2010 at 12:58 am

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.

July 21st, 2010 at 4:06 am

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

July 21st, 2010 at 5:00 am

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

July 21st, 2010 at 5:19 am

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

July 22nd, 2010 at 1:20 am

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.

July 22nd, 2010 at 3:52 am

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.

July 22nd, 2010 at 3:58 am

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!

July 22nd, 2010 at 4:07 am

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.

July 22nd, 2010 at 4:40 am

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.

July 22nd, 2010 at 9:27 pm

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!

July 30th, 2010 at 11:21 pm

n!/(n_k)!

July 30th, 2010 at 11:26 pm

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

December 21st, 2010 at 2:20 pm

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.

December 21st, 2010 at 2:30 pm

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.

December 21st, 2010 at 2:31 pm

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

December 21st, 2010 at 3:54 pm

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

December 22nd, 2010 at 9:05 am

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