3

Here is the question:

There is an endless supply of red, orange, yellow, green, blue, and violet Legos. The Legos are packaged into buckets of 100 Legos each. One possible color distribution, for example, is a bucket of 50 red, 10 yellow, 10 green, 10 orange, 10 blue, and 10 violet Legos. As a marketing gimmick, there is a guarantee that no two buckets have the same color distribution. What is the maximum number of buckets that can be produced for this to be true?

Here is my question about the solution:

I have seen this solved as: m plus n minus one factorial over m factorial multiplied by n minus one factorial

Where m is the number of Legos (or objects) in a given bucket and n represents the number of unique distinctions between these Legos, in this case, colors.

How does someone arrive at the conclusion that n needs to have 1 subtracted from it?

Why does total number of unique colors need to be added to the total number of Legos in a bucket for the top part of the equation?

I've seen people explain this concept of "put everything in it's own cell and count the dividers between the cells and add that to the total number of objects in a given container" but why would I care about the number of dividers when they aren't counted as part of the countable objects in the bucket? Why not count the number of possible colors and add that instead of subtracting one?

I'm so frustrated and confused. Thanks for any help anyone can offer.

Klaus Müller
  • 53

1 Answers1

3

That is Stars and Bars. Overall it’s like this; you have $100$ legos, arrange them in a line. Then say you have $5$ sticks. You place these sticks randomly between the legos. Replace all the legos to the left of the first stick with red legos, all the legos between the first and second stick with orange legos, and so on until you replace all the legos to the right of the last stick with violet legos. Now you have $100$ legos consisting of $6$ colors. Since each unique sticks placements give you a unique color combination, we can count the number of color combinations by counting the number of sticks placements.

Between the legos there are $100-1$ gaps. Choose $6-1$ gaps to place the sticks: $\binom{100-1}{6-1}$

Just for clarity: if you have $n$ groups, you only need $n-1$ sticks to separate them

Thomas Andrews
  • 177,126
acat3
  • 11,897
  • Ok, I see it now - physically having it in front of me and realizing I'm counting the unique combos, not the unique objects is where I was missing the point. Thanks so much. I was getting so irritated over the partition issue! – Klaus Müller Sep 19 '21 at 05:19
  • 2
    My answer is only valid if we require all colors to be present in the packaging. If you allow the packaging to have less than $6$ colors then it’s $\binom{m+n-1}{n-1}$. Reasoning is similar, you have $m+n-1$ legos, choose $n-1$ legos to be the stick, then color the legos as in the answer. This will allow the sticks to be next to each other i.e. some colors will have zero legos in the packaging. – acat3 Sep 19 '21 at 05:26
  • And I'm grateful you said that because it could be 100 red in a bucket or 100 violet in a bucket, or 99 red/1 violet in a bucket - but your statement about the combinations versus unique items was worth more than it's weight in gold, and for that, we thank you! – Klaus Müller Sep 19 '21 at 05:44
  • 2
    @KlausMüller Another nice Stars and Bars article is this one. The enumeration of the number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_k = n$ is $\displaystyle \binom{n + [k-1]}{k-1}.$ An alternative approach to the conclusion in this answer is that if $x_1, \cdots x_k$ must all be $\geq 1$, then you can set $y_i = x_i - 1 ~: ~i \in {1,2,\cdots,k}.$ ...see next comment – user2661923 Sep 19 '21 at 05:53
  • 1
    @KlausMüller Then, there is a one-to-one correspondence between each positive integer solution of $x_1 + \cdots + x_k = n$ and each non-negative integer solution of $y_1 + \cdots + y_k = (n-k)$. This 2nd equation will have $\displaystyle \binom{[n-k] + [k-1]}{[k-1]} = \binom{n-1}{k-1}$ solutions. – user2661923 Sep 19 '21 at 05:56
  • Alternatively, plot cumulative distribution of color # $0,…,n-1$. Notice that you’ll get North - East lattice path from $(0,0)$ to $(m, n-1)$. The number of unique path is $\binom{n+m-1}{m-1}$ – acat3 Sep 19 '21 at 06:00