5
$\begingroup$

I'm looking for a more generic way to apply this, but here's the problem in a nutshell. I have a number of balls that are divided up into partitions. For instance, I might have the following:

  • 5 blue balls
  • 4 green balls
  • 2 yellow balls
  • 1 red ball
  • 1 black ball

I'm trying to put them into a number of buckets, let's say 3 for this problem, although the number can vary. Each bucket must have a unique combination of balls when all is said and done, in other words, no two buckets can contain the same number of the same type of balls. All balls must be in a bucket to satisfy the conditions. An empty bucket is allowed. How many combinations are there?

Just to explain a bit more, if two buckets each had 2 blue balls and 1 green ball, that would not be acceptable. However, if one had 2 blue balls and 2 green balls, and the other had 2 blue balls and 1 green ball, that's okay. Also, one empty bucket is okay, as it is distinct.

For a very simple example, imagine 4 blue balls, 2 red balls, going into 4 buckets. There are 7 combinations, bbb|rr|b|0, bb|brr|b|0, b|bbrr|b|0, br|bbr|b|0, bbb|br|r|0, bbr|bb|r|0, and b|br|bb|r where 0 is empty, b is blue, r is red, and | is the divider between partitions.

Note that I want to understand how this works to apply it to a larger problem I'm working on, but if I can understand this, then it will make the larger problem easier.

I should add, I only need the exact number, I do not need to show every combination there is.

$\endgroup$
  • $\begingroup$ You should explain more precisely what you mean by "a unique combination of balls." Does this mean the contents of two distinct buckets cannot be identical? $\endgroup$ – kccu Dec 29 '15 at 19:11
  • $\begingroup$ Yes, that's exactly what it means. I've added an example to illustrate this, and will continue to work on the wording. $\endgroup$ – PearsonArtPhoto Dec 29 '15 at 19:13
  • $\begingroup$ Does each bucket need to be nonempty? $\endgroup$ – kccu Dec 29 '15 at 19:24
  • $\begingroup$ You caught me mid edit, adding that empty buckets are okay:-) $\endgroup$ – PearsonArtPhoto Dec 29 '15 at 19:25
  • 1
    $\begingroup$ One way to represent such problems is with partitions of multisets into distinct multisets. I strongly suspect these problems are difficult, given that counting contingency tables with fixed margins is #P-complete, even with only two rows (and $N$ columns). $\endgroup$ – hardmath Dec 29 '15 at 19:52
1
$\begingroup$

One can compute the number of all arrangements, then subtract the number of arrangements that break your rule (no two equal buckets).

The number of arrangements with equal buckets can be found by focusing on the third bucket. Because for each placement of balls in the third bucket:

a) there can be one (1) rule-breaking arrangement if the non-third bucket balls in are an even number for each color category - split them equally;

b) there can be no rule breaking arrangement if the ANY color category has an odd number of non-third bucket balls.

So, in how many ways can we put balls in the third bucket, so that there is an even remainder of balls in each color category?

$3(blue) * 3 (green) * 2(yellow) * 1 (red) * 1(black)$

So from the total number of arrangements of given balls in three undistinguishable buckets subtract 18.

q.e.d.

$\endgroup$
  • $\begingroup$ That works for the smaller problem that I posted, but it seems to be almost completely useless for anything other than the posted problem... There are 2 problems I'm trying to solve, one with 10 buckets and about 300 balls of 20 types, and another much larger problem... $\endgroup$ – PearsonArtPhoto Dec 31 '15 at 19:35
  • $\begingroup$ should be amenable to attack by either divide and conquer or by induction. $\endgroup$ – Dacian Bonta Dec 31 '15 at 20:37
  • $\begingroup$ with a dash of inclusion exclusion thrown in. $\endgroup$ – Dacian Bonta Jan 3 '16 at 1:40
  • $\begingroup$ To finish your calculation, if the buckets were labelled, we would have: $$ \binom{5+2}{2} \binom{4+2}{2} \binom{2+2}{2} \binom{1+2}{2} \binom{1+2}{2} = 17010$$ possibilities. Your $18$ cases of twin unlabelled buckets (out of three) corresponds to $3\cdot 18 = 54$ of those, so subtracting them and dividing by $3! = 6$ gives $2826$. $\endgroup$ – hardmath Jan 3 '16 at 16:59
1
$\begingroup$

I would organize the countings hierarchically, starting with the color of balls having the largest number and working downward. Expressed in terms of matrix multiplication similar to this earlier Question and Answer, the final states of two identical buckets vs. all three buckets different can be stated:

$$ \begin{bmatrix} 3 & 2 \end{bmatrix} \begin{bmatrix} 3 & 6 \\ 0 & 15 \end{bmatrix} \begin{bmatrix} 2 & 2 \\ 0 & 6 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 3 \end{bmatrix} = \begin{bmatrix} 18 & 2826 \end{bmatrix} $$

The maximum number of states to keep track of for this is the number of partitions of the three buckets, i.e. [3],[2&1],[1&1&1]. Note the first of these states disappears with the distribution of the first $5$ blue balls, since they cannot be uniformly placed. If (as in the Comment posted to the other Answer) there were ten buckets, we would have $42$ potential states (the number of integer partitions of $10$). This would accordingly enlarge the sizes of the transition matrices appearing in the matrix multiplication.

A description in words of the present computation of (only the three) distinct bucket outcomes follows.


If the (in this case) five blue balls are distributed into the three (unlabelled) buckets, it will result either in three distinguished buckets or in a pair of equal buckets and a third bucket distinguished from the other two. This is the inevitable result of any of the possible distributions of five balls into three buckets:

 [1&1&1]    [2&1]    after placing blue balls
 -------   -------  

            5+0+0  
  4+1+0  
  3+2+0  
            3+1+1  
            2+2+1  

Note that there are two ways to get three distinguished buckets and three ways to get a pair of identical buckets plus a third bucket that differs.

We then apply successive colors of balls to the previously established partitions of buckets. If a pair of buckets are distinguished, they will remain so no matter how the subsequent colors are distributed, and finally we are interested only in those arrangements in which all the buckets have been differentiated.

In the two cases above where the five blue balls already distinguish the three buckets, the remaining colors may be independently distributed into these three buckets as if they were labelled (as indeed they have been labelled by the blue ball placement).

In other words the distribution of a new color into three buckets that are individually distinguished already follows the (relatively) easy stars-and-bars computation, and given the two ways to get three distinguished buckets, we can finish out those countings by multiplying (principle of independent choices):

$$ 2 \times \binom{6}{2} \times \binom{4}{2} \times \binom{3}{2} \times \binom{3}{2} = 1620 $$

While two buckets remain undistinguished (identical so far), we have additional bookkeeping to do, to keep track of the point when they become distinguished. Here the four green balls can be applied in ways that either preserve the equality of the two "twin" buckets, or that distinguish them.

Maintaining their equality requires distributing an even number of the green balls into the twin buckets and splitting those balls equally between them. So if an odd number of green balls are shared by the twin buckets, or if an even number are divided between them unequally, we get down to all three buckets distinguished:

   For each twin bucket case [2&1] after placing blue balls:  

 [1&1&1]    [2&1]     after placing green balls  
 -------   ------

            0+0;4  
  1+0;3  
  2+0;2  
            1+1;2  
  3+0;1  
  2+1;1  
  4+0;0  
  3+1;0   
            2+2;0  

As this illustrates, the $3$ twin bucket cases after blue balls are placed become $3\times 6=18$ cases of three distinguished buckets and $3\times 3=9$ cases preserving the identical twin buckets after green balls are placed.

We dispose of the current three distinguished bucket cases as before, using the stars-and-bars + independent choice computations:

$$ 18 \times \binom{4}{2} \times \binom{3}{2} \times \binom{3}{2} = 972 $$

This leaves us our next task of placing the yellow balls in the nine cases that twin buckets are still preserved.

    For each twin bucket case [2&1] after placing green balls  

 [1&1&1]    [2&1]    after placing yellow balls  
 -------   -------  

            0+0;2  
  1+0;1  
            1+1;0  
  2+0;0  

We thus get $9\times 2 = 18$ cases where the three buckets have become distinguished and $9\times 2 = 18$ cases where a pair of twin buckets remains. The former yields eventually this number of arrangements, by placing the final two colors:

$$ 18 \times \binom{3}{2} \times \binom{3}{2} = 162 $$

The $18$ cases where twin buckets remain after placing yellow balls result as follows when the red ball is placed:

    For each twin bucket case [2&1] after placing yellow balls  

 [1&1&1]    [2&1]    after placing red ball   
 -------   -------  

            0+0;1  
  1+0;0  

Thus we get an additional $18$ cases where the buckets are all three distinguished, and also $18$ cases where twin buckets persist. The former gives us eventually:

$$ 18 \times \binom{3}{2} = 54 $$

and the $18$ cases where twin buckets persist after placing the red ball force us to use the placement of the final black ball to break their symmetry.

That adds a final $18$ outcomes (with all bucket counts differing).

So the total number of ways to place these colored balls in the three buckets so that no two buckets are alike is:

$$ 1620 + 972 + 162 + 54 + 18 = 2826 $$

$\endgroup$
  • $\begingroup$ @PearsonArtPhoto: If you want to post or gmail me the details of the ten bucket problem, I'd be happy to estimate how big of a computation it would be. $\endgroup$ – hardmath Jan 2 '16 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.