Question

Twenty indistinguishable balls are placed in 10 indistinguishable bins so that at least one ball is placed in a bin. How many ways can this be completed?

Answer 1

lets place a ball each first in each bin
no. of ways = 1 (all are indistinguishable)
then we have 10 balls and 10 bins
each ball has ten options to go..
hence no. of ways = 10^10

someone please verify..

Answer 2

@shubhamsrg I think that's right.

We have 10 remaining balls, and 10 bins. For the first ball, we can pick any one of 10 bins. For the next ball, we can still pick any one of 10 bins, and the same for the next ball and so on.

Or 10x10x10... each ball having ten places to go, so 10^10

Answer 3

Hmmm... but putting all 10 remaining balls in one bin is the same as putting all 10 in any other bin, I think we forgot to consider that...

Answer 4

ohh,,bins are also indistinguishable! hmm..

Answer 5

Yeah our answer is too large. Putting all 10 into one is the same for all 10 bins. Same with putting 9 into one bin, and one into another bin

Answer 6

I think we need to use the combinations formula, it's similar to this: http://math.stackexchange.com/questions/58753/unique-ways-to-keep-n-balls-into-k-boxes
^ good explanation of it here

So it looks like we need to use \[\left(\begin{matrix}N-1 \\ K-1\end{matrix}\right)\]

where N is the number of balls, K is the number of bins.

Answer 7

Oh but that link also seems to be for distinguishable bins...

Answer 8

here is what i thought:

if each bin gets a1 ,a2...a10 balls, we know
a1 + a2 +... a10 =10
where each>= 0

no. of such combinations = 19C9

my query is, what do we divide it with owing to the symmetry ?

Answer 9

I think in this case we can actually just add up the possibilities since the bins are indistinguishable. Therefore each of these arrangements has only 1 possibility:

10 in one bin
9 in one, 1 in another
8 in one, 2 in another
8 in one, 1 in another, 1 in another
7, 3
7, 2, 1
7, 1, 1, 1
6, 4
6, 3, 1
6, 2, 2
6, 2, 1, 1
6, 1, 1, 1, 1
5, 5
5, 4, 1
5, 3, 2
5, 3, 1, 1
5, 2, 2, 1
5, 2, 1, 1, 1
5, 1, 1, 1, 1, 1
4, 4, 2
4, 4, 1, 1
4, 3, 3
4, 3, 2, 1
4, 3, 1, 1, 1
4, 2, 2, 1, 1
4, 2, 1, 1, 1, 1
4, 1, 1, 1, 1, 1, 1
3, 3, 3, 1
3, 3, 2, 1, 1
3, 3, 1, 1, 1, 1
3, 2, 2, 2, 1
3, 2, 2, 1, 1, 1
3, 2, 1, 1, 1, 1, 1
3, 1, 1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2
2, 2, 2, 2, 1, 1
2, 2, 2, 1, 1, 1, 1
2, 2, 1, 1, 1, 1, 1, 1
2, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1


I think these are all the possibilities... unless i've missed some.

Answer 10

I regret writing them out one by one. I thought there would be a lot less than that when I started :/

Answer 11

Idk how we'd account for the symmetry to get from 19C9 to the total # combinations, which appears to be 40.

Answer 12

hmm,,you worked quite hard for this solution! :D
nice job !

Answer 13

I think I missed two though... somehow i stumbled onto this: http://en.wikipedia.org/wiki/Composition_(number_theory)
It mentions partitions of the number 5, which looks exactly like what i did up above... so i looked up partitions of 10, and wolfram alpha gives them all:

http://www.wolframalpha.com/input/?i=integer+partitions+of+10

Answer 14

So it seems this problem is more of a number theory problem, which I don't think I've ever studied.

From that link, the total number of partitions for 10 is 42, I got 40 so i must have missed 2.

Answer 15

hmm..nice..i'd have given you 2 medals if i could! :D

Answer 16

haha :)

I found the two I missed by comparing my numbers to wolframalpha's list:
3, 3, 2, 2
and
4, 2, 2, 2

So @ArkGoLucky the answer is 42, as you can see here: http://www.wolframalpha.com/input/?i=integer+partitions+of+10