Dividing 4 balls over 4 boxes

[haushofer]

Dear all,

I've always had, for some reason, mental problems with combinatorics. Somehow I'm missing something (a vital brain part or whatever). The situation I want to analyse for myself, is the following.

I want to divide 4 indistinguishable balls over 4 boxes. In the end I want to calculate how probable every configuration is. What I do understand, is the total number of possible configuration by using the "O and lines" notation: we can denote the division between boxes by 3 lines, and the balls by O's, so a few possibilities are

$$|O|O|O|O| , or \ \ \ \ \ |OOOO|\ \ |\ \ |\ \ |, or \ \ \ \ \ |OO| \ \ |OO | \ \ | , etc.$$

I understand that there are (4-1)=3 inner lines (the divisions between boxes) and 4 O's, which in total can be rearranged in (4+4-1)! = 7! different ways. The O's can be rearranged in 4! different ways, and the lines in 3! different ways, giving me

$$\frac{7!}{4!3!}$$

different ways of dividing my 4 indistuingishable balls over 4 boxes. Now comes the silly part, which I cannot get my head around: what is the number of ways to obtain a specific configuration like

$$|OO| \ \ |OO | \ \ | \ \ \ \ \ \ \ (*)$$
?

For a specific configuration like

$$|O|O|O|O|$$

I'd say it is 4!=24, but somehow a configuration like (*) is not processable for my brain. I'm sure I'll get a DHOUGH!-moment if anybody can explain it to me. Many thanks in advance!

 

[Orodruin]

What you are after are the multinomial coefficients.

For your specific case, you would have
$$
{4 \choose 1,1,1,1} = \frac{4!}{1!1!1!1!} = 4!.
$$
For your case with two balls in two bins and zero in the others
$$
{4 \choose 2, 0, 2, 0} = \frac{4!}{2!0!2!0!} = \frac{4!}{4} = 3!
$$

 

[haushofer]

Yes, exactly, thank you very much. DHOUGH-moment indeed. But in those multinomial coefficients the k's all add up to 4. How would my calculation now change if I would divide 5 balls over the 4 boxes, like, say,
$$|OO| \ \ |OOO | \ \ |$$
? Would that simply be

$$\frac{5!}{2! 0! 3! 0!}$$
? I guess I'm confused because this is just how you would arrange 5 objects into a group of 2 and 3, and that the number of boxes just needs to be more than 2 but doesn't enter the problem.

 

[StoneTemplePython]

I'm not quite sure what you're looking to do here.

In the case of 5 balls in 4 boxes, you have a pidgeon hole -- i.e. one box must have at least 2 balls. Why not just cut to the chase and 'tape together' 2 balls, you have ${5 \choose 2}$ ways of doing this, and then repeat whatever work you did above with 4 balls?

 

[PeroK]

Dear all,

I've always had, for some reason, mental problems with combinatorics. Somehow I'm missing something (a vital brain part or whatever). The situation I want to analyse for myself, is the following.

I want to divide 4 indistinguishable balls over 4 boxes. In the end I want to calculate how probable every configuration is.

There's a difference between counting how many ways something can be done and the probability of it happening. The key factor is to establish the basic configurations that are equally likely.

For example, if you have two boxes and two balls. There are only three configurations, but the configuration with one ball in each box is twice as likely as the others.

You can count the configurations using the balls and bars method, but that won't give you the probabilities.

Instead, you can label each ball - even though eventually they will be indistinguishable. We're assuming I guess that each ball has an equal probability of going in each box. The basic configurations that are equally likely are four digit numbers, where the first digit represents the box that ball 1 goes into and so on. For example:

$3122$ represents ball 1 going into the third box, ball 2 going into the first box and balls 3 and 4 going into the second box.

All these configurations from $1111$ to $4444$ are equally likely. And there are, of course, $4^4 = 256$ of them.

If you now take any particular configuration, you need to count how many of the $256$ base equally configurations meet the criteria.

For example, if you wanted $2$ balls in the first box and $2$ balls in the second box, then you need to count all the four digit numbers composed of two $1$'s and two $2$'s.

I.e. the configurations that meet your criteria are $1122, 1212, 1221, 2112, 2121, 2211$

So, there are only $6$ configurations. This can also be calculated from the multinomial coefficients as above:

${4 \choose 2, 2, 0, 0} = 6$

That gives you a probability of $\frac{6}{256}$ for having $2$ balls in the first box and $2$ balls in the second box.

If you want the probably that there are two balls in any two boxes and no balls in the other two, then there are ${4 \choose 2} = 6$ different options for the two boxes, hence a total probability of $\frac{36}{256}$ for this.

The probability for the other configurations can be calculated similarly.

 

[Orodruin]

I'm not quite sure what you're looking to do here.

In the case of 5 balls in 4 boxes, you have a pidgeon hole -- i.e. one box must have at least 2 balls. Why not just cut to the chase and 'tape together' 2 balls, you have ${5 \choose 2}$ ways of doing this, and then repeat whatever work you did above with 4 balls?

I am not completely sure of what you are trying to do here, but I strongly suspect this is going to lead to some double counting that you need to be very careful about.

 

[StoneTemplePython]

I am not completely sure of what you are trying to do here, but I strongly suspect this is going to lead to some double counting that you need to be very careful about.

Fair point -- I think there's a reduction lurking somewhere nearby but it's premature to do one as I don't fully get the goal.

 

[Orodruin]

To be honest, you should really be looking at distinguishable balls and then consider how many options you have that give you the same result if you forget that the balls are distinguishable. I believe this is the easiest way forward. Distinguishable balls can be placed in $4^4$ different ways. What the multinomial coefficient tells you is the number of ways that you can achieve a particular indistinguishable configuration and so the multinomial coefficient divided by $4^4$ will be the probability of achieving said configuration regardless of which balls are in which box.

Note that a crucial property of the multinomial coefficients is
$$
\sum_{\lvert \alpha\rvert = N} {N \choose \alpha} = k^N,
$$
where $\alpha$ is a multi-index containing $k$ integers. This ensures that the total probability is one.

 

[haushofer]

I'm not quite sure what you're looking to do here.

In the case of 5 balls in 4 boxes, you have a pidgeon hole -- i.e. one box must have at least 2 balls. Why not just cut to the chase and 'tape together' 2 balls, you have ${5 \choose 2}$ ways of doing this, and then repeat whatever work you did above with 4 balls?

I'm looking to see how, in general, k indistinguishable balls can be divided over n distinguishable boxes. Giving that each ball ending up in a box has an equal a priori probability $\frac{1}{n}$, in the end I want to derive the distribution of all configurations and show that the "equal spreading" is the most probable one.

I'm not sure about your construction here, I have to think about that.

 

[PeroK]

I'm looking to see how, in general, k indistinguishable balls can be divided over n distinguishable boxes. Giving that each ball ending up in a box has an equal a priori probability $\frac{1}{n}$, in the end I want to derive the distribution of all configurations and show that the "equal spreading" is the most probable one.

I'm not sure about your construction here, I have to think about that.

In the example of 4 balls and four boxes, the probabilities are:

$p(4, 0, 0, 0) = 4/256$
$p(3, 1, 0, 0) = 48/256$
$p(2, 2, 0, 0) = 36/256$
$p(2, 1, 1, 0) = 144/256$
$p(1, 1, 1, 1) = 24/256$

A pattern of $2, 1, 1, 0$ is, therefore, by far the most likely.

You can use these probabilities to generate the probabilities for 5 balls in 4 boxes and so on, using a tree approach. This gives:

$p(5, 0, 0, 0) = 4/1024$
$p(4, 1, 0, 0) = 60/1024$
$p(3, 2, 0, 0) = 120/1024$
$p(3, 1, 1, 0) = 240/1024$
$p(2, 2, 1, 0) = 360/1024$
$p(2, 1, 1, 1) = 240/1024$

As you increase the number of balls, these probabilities iterate according to the tree structure and each can be expressed as some combination of multinomials. But, I seem to recall that they don't simplify any further.

 

[Orodruin]

It is worth taking some time to ponder why the 2110 is much more likely than the 1111. In order to get 1111, the first three balls need to land in different boxes. If this is the case, the probability of ending up with 2110 is three times larger than getting 1111. Apart from this, you can additionally get 2110 from 2100 after three balls.

 

[Stephen Tashi]

giving me

$$\frac{7!}{4!3!}$$

different ways of dividing my 4 indistuingishable balls over 4 boxes.

- which is a total of 35 ways.

Now comes the silly part, which I cannot get my head around: what is the number of ways to obtain a specific configuration like

$$|OO| \ \ |OO | \ \ | \ \ \ \ \ \ \ (*)$$
?

There is 1 way of obtaining that configuration - unless you want to drop the assumption that the balls are indistinguishable. Any analysis you do that gives you a total of more than 35 ways is obviously considering a different problem.

 

[PeroK]

- which is a total of 35 ways.There is 1 way of obtaining that configuration - unless you want to drop the assumption that the balls are indistinguishable. Any analysis you do that gives you a total of more than 35 ways is obviously considering a different problem.

I assumed we were talking about indistinguishable in its "real-world" sense, rather than the elementary particle sense. In the sense that pound coins or red snooker balls are indistinguishable. But not in the sense that electrons are indistinguishable.

 

[Stephen Tashi]

Yes, the verbal problems posed in combinatorics (at least in the English language ) have cultural traditions associated with them. For example, "How many ways can 3 letter A's and 2 letter B's be arranged to form 5 letter string? " would traditionally be interpreted to mean that the A's are "indistinguishable" - and yet it might be useful to analyze the problem as if the A's and B's are distinguishable and then divide the answer by factors that account for multi-counting them.

In other fields of study, solving concisely phrased verbal problems is usually done using only a few sentences to justify some mathematical expressions. Experts can usually do such problems and quickly agree with each other on an answer. By contrast, In combinatorics, a problem posed in a few sentences can lead to elaborate verbal discussions and experts may thrash around before they come to an agreement. Sometimes, everyone agrees on the answer and, after a pause, it's pointed out "Opps, we forgot to add 1 to the result" or some such correction.

Someone should develop a formal language for stating combinatorial problems. A problem posed in natural language would be translated into the formal language, possibly after lengthy verbal debates - but after the problem was stated in the formal language, the technique of solution would be straightforward and uncontroversial.

----
One fundamental problem with the natural language use of the adjective "indistinguishable" is that (literally) if you had two "indistinguishable" balls, you wouldn't have two balls. You would have 1 ball. They would be the same ball. So "indistinguishable" must be interpreted to mean "indistinguishable with respect to the property of...".

 

[haushofer]

- which is a total of 35 ways.There is 1 way of obtaining that configuration - unless you want to drop the assumption that the balls are indistinguishable. Any analysis you do that gives you a total of more than 35 ways is obviously considering a different problem.

Yes, I see it.

It's amazing how confusing this is to me (distinguishable vs indistinguishable). It's like my brain has a blind spot for combinatorics :D

 

[PeroK]

Yes, I see it.

It's amazing how confusing this is to me (distinguishable vs indistinguishable). It's like my brain has a blind spot for combinatorics :D

For real-world objects, they are always distinguishable as you can always in theory mark them in some way. And, treating them as fundamentally distinguishable is critical in calculating probabilities.

All you do, really, when you consider them as indistinguishable is group together certain configurations and probabilities that look the same. The classic example is tossing two coins. There is in fact no real event of "one head and one tail". That is a combination of two events that you choose to consider the same (for practical purposes).

To calculate the probabilities you must consider the coins separately, even if you group several results together. In this case to get that the probability of one head and one tail is 1/2. This is always, really, 1/4 + 1/4.

 

[haushofer]

In the example of 4 balls and four boxes, the probabilities are:

$p(4, 0, 0, 0) = 4/256$
$p(3, 1, 0, 0) = 48/256$
$p(2, 2, 0, 0) = 36/256$
$p(2, 1, 1, 0) = 144/256$
$p(1, 1, 1, 1) = 24/256$

A pattern of $2, 1, 1, 0$ is, therefore, by far the most likely.

Ok. Just to check if I got it: E.g., in your $p(3, 1, 0, 0)$ the order of the numbers doesn't matter. So first you calculate $\frac{4!}{3!1!0!0!}$, which gives you the number of ways you can divide 4 into 3+1+0+0. For the 3 balls, you have 4 choices, and for the 1 ball you remain with 3 choices, and then the two zero's are fixed. So you have to multiply $\frac{4!}{3!1!0!0!}$ with $4\times 3 \times 1$, giving you $4 \times 12=48$. The probability is then obtained by dividing this by 256. This gives us the probability that our 4 balls are divided as 3+1+0+0 in whatever order.

You can use these probabilities to generate the probabilities for 5 balls in 4 boxes and so on, using a tree approach. This gives:

$p(5, 0, 0, 0) = 4/1024$
$p(4, 1, 0, 0) = 60/1024$
$p(3, 2, 0, 0) = 120/1024$
$p(3, 1, 1, 0) = 240/1024$
$p(2, 2, 1, 0) = 360/1024$
$p(2, 1, 1, 1) = 240/1024$

As you increase the number of balls, these probabilities iterate according to the tree structure and each can be expressed as some combination of multinomials. But, I seem to recall that they don't simplify any further.

I'll work that out, thanks!

 

[haushofer]

For real-world objects, they are always distinguishable as you can always in theory mark them in some way. And, treating them as fundamentally distinguishable is critical in calculating probabilities.

All you do, really, when you consider them as indistinguishable is group together certain configurations and probabilities that look the same. The classic example is tossing two coins. There is in fact no real event of "one head and one tail". That is a combination of two events that you choose to consider the same (for practical purposes).

To calculate the probabilities you must consider the coins separately, even if you group several results together. In this case to get that the probability of one head and one tail is 1/2. This is always, really, 1/4 + 1/4.

I think this approach of first treating objects as distinguishable and only after that introduce equivalence classes can be very helpful indeed. I've never really approached these problems in this way.

 

[haushofer]

To explain my original motivation for this problem: I want to understand quantitatively the idea that equilibrium, e.g. maximum entropy, coincides with the most probable configuration of a box of gas. To model this system I take molecules as balls and my box as a line of boxes, i.e. a 1-dimensional line. The indistinguishability of the balls then refers to the kind of statistics used in quantum mechanics.

 

[PeroK]

Ok. Just to check if I got it: E.g., in your $p(3, 1, 0, 0)$ the order of the numbers doesn't matter. So first you calculate $\frac{4!}{3!1!0!0!}$, which gives you the number of ways you can divide 4 into 3+1+0+0. For the 3 balls, you have 4 choices, and for the 1 ball you remain with 3 choices, and then the two zero's are fixed. So you have to multiply $\frac{4!}{3!1!0!0!}$ with $4\times 3 \times 1$, giving you $4 \times 12=48$. The probability is then obtained by dividing this by 256. This gives us the probability that our 4 balls are divided as 3+1+0+0 in whatever order.

I'll work that out, thanks!

Yes. $(3, 1, 0, 0)$ represents $12$ different configurations of which boxes contain the balls. And, each of these configurations has $4$ sub-configurations, defined by which ball is on its own.

Another way to look at it, and I find this useful is to define $3-1-0-0$ as the configuration with $3$ balls in the first box and $1$ ball in the second box. As opposed to $(3, 1, 0, 0)$ being $3$ balls in any box and $1$ in any other box:

$p(3, 1, 0, 0) = 12p(3-1-0-0)$

Then, let $B1, B2, B3 - B4 - 0 - 0$ be the configuration where balls $1, 2$ and $3$ are in the first box and ball $4$ is in the seond box. We have:

$p(3-1-0-0) = 4p(B1, B2, B3 - B4 - 0 - 0)$

And:

$p(3, 1, 0, 0) = 48p(B1, B2, B3 - B4 - 0 - 0)$

The critical thing here is that $B1, B2, B3 - B4 - 0 - 0$ is one of the fundamental equally-likely outcomes, with probability $1/256$.

 

[PeroK]

To explain my original motivation for this problem: I want to understand quantitatively the idea that equilibrium, e.g. maximum entropy, coincides with the most probable configuration of a box of gas. To model this system I take molecules as balls and my box as a line of boxes, i.e. a 1-dimensional line. The indistinguishability of the balls then refers to the kind of statistics used in quantum mechanics.

If the particles are fundamentally indistiguishable, then that is a different ball game! You can't use the calculations I've given because you cannot - even theoretically - mark each particle to distinguish it from the others.

 

[haushofer]

If the particles are fundamentally indistiguishable, then that is a different ball game! You can't use the calculations I've given because you cannot - even theoretically - mark each particle to distinguish it from the others.

I know; that's why you have a total amount of 256 configurations, while in my OP I mentioned 35. Of course, in classical thermodynamics (as opposed to quantum) the molecules can be distinguished (labeled), so I want to understand that situation (i.e. your calculations) as wel :)

Anyway, many thanks everybody. I'll work stuff out, and if I have any more questions, I'll be back!

 

[Stephen Tashi]

To explain my original motivation for this problem: I want to understand quantitatively the idea that equilibrium, e.g. maximum entropy, coincides with the most probable configuration of a box of gas.

A fundamental problem with that goal is that "maximum entropy" is concept that is defined for probability distributions, not a concept that applies to a particular configuration. It's human nature to think that one particular situation (e.g. a particular set of data) is more random tor disorderly than another. People have invented ways to quantify this opinion.

I think what you mean is that you want to understand why the maximum entropy distribution on one probability space implies certain outcomes on a different probability space are most probabie.

Probability spaces for a sequence of "identical" experiments are defined as probability measures on cartesian products. For example, if we take R = [H, T} as the set used in a coint toss experiments, the probability space for a sequence of 3 coin tosses is the set of 3-tuples RxRxR. If we consider the experiment: "Put a ball in one of the 4 boxes" with possible outcomes R = {B1,B2,B3,B4} then the probability space of repeating this experiment 4 times is defined on S = RxRxRxR. If you assume each box has an equal probability of being chosen on each of the 4 sub-experiments, then you have assumed the maximum entropy probability distribution on S.

Using that maximum entropy distribution, you can compute the probability of various configurations - such (in your notation) "/00/ /00/ /". - or, in terms of "occupancy numbers" (2,0,2,0). Such configurations are defined on a different probability space than those of the original experiment. The probability space O for the occupancy numbers can be defined in terms of the sets in S by lumping some subsets of S together and regarding it as a single configuration. It is a well-defined question to ask what the most probable occupancy numbers are under the assumption that the probability distribution on the underlying set S has maximum entropy.

The maximum entropy distribution on S = RxRxRxR does not lead to the maximum entropy distribution that can be defined on O, the set of occupancy numbers. The maximum entropy distribution on O would be to assign each distinct set of occupancy numbers a probability of 1/35.