Register to reply

Number of ways to place n balls into m boxes

by KFC
Tags: balls, boxes, number
Share this thread:
KFC
#1
Sep11-10, 03:03 AM
P: 369
Let's consider a simple case with 2 balls and 3 boxes. Assuming all balls are the same and empty box is allowed. In addition, each box can take any number of ball. How many ways are there to place the balls into the boxes?

Here is my way to solve the problem. For the first ball, there are 3 ways to do so. For the second ball, still 3 ways. So total 9 ways to place 2 balls into 3 boxes. For the general way, my conclusion is [tex]m^n[/tex]

But the answer is

2 0 0
0 2 0
0 0 2
1 0 1
0 1 1
1 1 0

There are only six ways. So what's wrong with my analysis? And what's the correct expression for this case?
Phys.Org News Partner Mathematics news on Phys.org
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
JSuarez
#2
Sep11-10, 12:42 PM
P: 402
You are overcounting. When you say:

For the first ball, there are 3 ways to do so. For the second ball, still 3 ways.
You are distinguishing the balls. The correct way of counting this type of problems, with repetition but without order is like this (the two 0's separate the three boxes):

1100, 0110, 0011, 1010, 1001, 0101

In the general case, this is counting the number of lenght n binary sequences with exactly k 0's and there is a well-known expression for this.
JeSuisConf
#3
Sep14-10, 12:49 PM
P: 34
You're looking for the number of multinomial coefficients. It's given explicitly on wikipedia.

Anyways, the answer you're looking for is [tex]{m+n-1} \choose {n}[/tex] where [tex]m[/tex] is the number of boxes and [tex]n[/tex] is the number of balls.

Little ant
#4
Sep14-10, 02:04 PM
P: 21
Number of ways to place n balls into m boxes

we can colocated the first ball at box 1, box 2 or box 3. Then you can put the second ball at box 1 box 2 or box 3, so, for one ball, you have 3 options, and are 2 ball. to generalize, if you have n balls, and m positions for each ball, the posibles combinations are equal to product m.n and you can verify than 2.3=6
KFC
#5
Sep16-10, 08:40 AM
P: 369
Quote Quote by Little ant View Post
we can colocated the first ball at box 1, box 2 or box 3. Then you can put the second ball at box 1 box 2 or box 3, so, for one ball, you have 3 options, and are 2 ball. to generalize, if you have n balls, and m positions for each ball, the posibles combinations are equal to product m.n and you can verify than 2.3=6
Thanks for your reply. But base on your reasoning, if I have 3 boxes and 4 balls, there are 3*4 = 12 ways to place the balls? But the answer if 15
Little ant
#6
Sep16-10, 09:01 PM
P: 21
answer is (m+n-1) just like somebody sad.
n*(m-1)
Little ant
#7
Sep16-10, 09:02 PM
P: 21
answer is (m+n-1) just like somebody sad.
. n*(m-1)
Little ant
#8
Sep16-10, 09:03 PM
P: 21
answer is (m+n-1)/n*(m-1) just like somebody sad.
.
KFC
#9
Sep17-10, 05:42 AM
P: 369
Quote Quote by Little ant View Post
answer is (m+n-1)/n*(m-1) just like somebody sad.
.
Yes. I know the answer. Just find it hard to understand how to get this. For the case when there are N boxes and M balls and no empty box is allowed, it is easy to get the result by considering the way to pick up N from M+1. But for the case allowing empty box, I don't know how to deduce that formular


Register to reply

Related Discussions
Counting balls in boxes Precalculus Mathematics Homework 4
Balls and Boxes Complicated Problem Set Theory, Logic, Probability, Statistics 1
Ways to place molecules Introductory Physics Homework 1
Balls in Boxes, Probability Question Set Theory, Logic, Probability, Statistics 7
Balls in boxes ( probability ) Fun, Photos & Games 11