# How many different ways can you arrange 1 million beans in 3 different bowls

• Jun 8th 2010, 06:12 PM
neyamv
How many different ways can you arrange 1 million beans in 3 different bowls
How many different ways can you arrange 1 million beans in 3 different bowls? Please provide the formula to this question and the answer. Thanks
• Jun 8th 2010, 08:08 PM
undefined
Quote:

Originally Posted by neyamv
How many different ways can you arrange 1 million beans in 3 different bowls? Please provide the formula to this question and the answer. Thanks

Hi neyamv,

There is more than one way to interpret this problem. The beans could all have little ID numbers on them, which would result in there being very many ways to arrange them. Or the beans could all be indistinguishable, which is probably the problem's intent. Also, the bowls could be labeled or unlabeled. Also, it's not clear whether any of the three bowls is allowed to be empty.

Let's assume the beans are unlabeled and the bowls are labeled, and that each bowl must have at least one bean.

EDIT: Wow, I was working with another problem that had 100 instead of a million and got the numbers mixed up! However, the reasoning is still the same.. (Itwasntme) So, the following explanation is for 100 beans.

Then solutions are given by

(1,1,98)
(1,2,97)
...
(1,98,1)
(2,1,97)
...
(2,97,1)
...
(98,1,1)

If you followed what I wrote above, then you will have an idea of how to solve this problem. Say the beans are labeled A,B,C, and we fix A with 1 bean.

(1,1,98)
...
(1,98,1)

This gives 98 ways.

Then when we fix bowl A with 2 beans we get 97 ways.

Etc.

So the answer is $\sum_{i=1}^{98}i=\frac{(98)(99)}{2}=\boxed{4851\ \text{ways}}$
• Jun 8th 2010, 09:25 PM
Soroban
Hello, neyamv!

Quote:

How many different ways can you arrange 1 million beans in 3 different bowls?

I will assume that the million beans are indistinguishable.
. . But the bowls are distinct; call them $A,B,C.$

I will also assume that a bowl may empty.

Place the million beans in a row, leaving a space before, after and between them.
. . $\_\:o\:\_\:o\:\_\:o\;\_\:\hdots\:\_\:o\:\_$

Place two "dividers" in any of the 1,000,001 spaces.

. . $\begin{array}{ccc}o\:o\:|\:o\:o\:o\:o\:|\:o\:o\:\h dots\:o & \text{represents} & (2,\:4,\:999,\!994) \\ \\

|\:o\:o\:o\:o\:|\;o\;o\;o\;\hdots\;o & \text{represents} & (0,\:4,\:999,\!996) \\ \\

o\:o\:o\:||\:o\:o\:o\:\hdots\:o & \text{represents} & (3,\:0,\:999,\!997)
\end{array}$

For each of the two dividers, there are 1,000,001 choices of location.

Therefore, the answer is: . $1,\!000,\!001^2 \:=\:1,\!000,\!002,\!000,\!001$ ways.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If empty bowls are not allowed, place the million beans in a row
. . leaving spaces between them.

Then select two of the 999,999 spaces for the dividers.
. . There are: . ${999,999\choose2}$ choices.

The answer is: . $499,\!998,\!511,\!111$ ways.

• Jun 9th 2010, 02:27 PM
awkward
Quote:

Originally Posted by Soroban
Hello, neyamv!

I will assume that the million beans are indistinguishable.
. . But the bowls are distinct; call them $A,B,C.$

I will also assume that a bowl may empty.

Place the million beans in a row, leaving a space before, after and between them.
. . $\_\:o\:\_\:o\:\_\:o\;\_\:\hdots\:\_\:o\:\_$

Place two "dividers" in any of the 1,000,001 spaces.

. . $\begin{array}{ccc}o\:o\:|\:o\:o\:o\:o\:|\:o\:o\:\h dots\:o & \text{represents} & (2,\:4,\:999,\!994) \\ \\

|\:o\:o\:o\:o\:|\;o\;o\;o\;\hdots\;o & \text{represents} & (0,\:4,\:999,\!996) \\ \\

o\:o\:o\:||\:o\:o\:o\:\hdots\:o & \text{represents} & (3,\:0,\:999,\!997)
\end{array}$

For each of the two dividers, there are 1,000,001 choices of location.

Therefore, the answer is: . $1,\!000,\!001^2 \:=\:1,\!000,\!002,\!000,\!001$ ways.

[snip]

Soroban,

You seem to have counted many of the arrangements of the dividers twice-- after all, the dividers are not "distinguishable".

(By a standard formula in combinatorics, the number of arrangements of the beans should be

$\binom{n+2}{n}$

where n = 1,000,000.)
• Jun 9th 2010, 02:56 PM
undefined
Quote:

Originally Posted by Soroban
If empty bowls are not allowed, place the million beans in a row
. . leaving spaces between them.

Then select two of the 999,999 spaces for the dividers.
. . There are: . ${999,999\choose2}$ choices.

The answer is: . $499,\!998,\!511,\!111$ ways.

Didn't notice what awkward mentioned (was too busy being surprised that I could confuse a million with a hundred to look at fine detail), but there is a small correction that seems worth mentioning; I get

$\binom{999999}{2}=499998500001$

(This is also equal to $\frac{999998\cdot999998}{2}$ as per my first post.)
• Jun 9th 2010, 07:42 PM
neyamv
Thank you all for your answers. Can anyone tell me the exact formula to figure out for any amount of bowls
• Jun 9th 2010, 10:34 PM
undefined
Quote:

Originally Posted by neyamv
Thank you all for your answers. Can anyone tell me the exact formula to figure out for any amount of bowls

Which assumption did you want: bowls can be empty, or bowls can't be empty?

For the bowls can't be empty version, distributing $n$ beans among $m$ bowls, we have $\binom{n-1}{m-1}$ ways and of course $0$ whenever $m$ exceeds $n$.

For the bowls can be empty version, using $n$ and $m$ from above, the answer is $\binom{m+n-1}{n}$. For an overview of these and other counting problems, you can read this PDF file, Richard Stanley's Twelvefold Way.