6
$\begingroup$

I want to know that if Balls in Bins and Stars n Bars problems in combinatorics are similar?

Can we reduce one into other? How? How can they be mapped to each other?

$\endgroup$
  • $\begingroup$ Balls in bins is a general class of problems. For a finer classification see Wikipedia, The Twelvefold Way. Stars and Bars is helpful in solving some of these. $\endgroup$ – André Nicolas Dec 31 '14 at 23:39
6
$\begingroup$

They are similar concepts in the sense that they both help you visualize and derive some combinatorial theorems. In some cases one is more suitable than the other.

Think for example a stars and bars representation: $$ \star \star \star |\star\star || \star $$ You can think of that as having $6$ balls divided into $4$ bins: the first bin has $3$ balls, the second $2$, the third is empty and the fourth has $1$ ball. In that sense, the two representations are similar.

At the same time, however, the previous stars and bars representation also induces a labeling on the bins -- it is the first bin that has three balls, and it is the third bin that is empty -- while the balls are unlabeled. If we want to find in how many ways we can partition the $6$ balls into the $4$ bins, we would have to clarify whether the balls are indistinguishable and the bins are labeled (i.e. whether the partition $3,2,0,1$ as above is different than $2,0,1,3$). If yes, then the stars and bars representation comes handy for this problem.

$\endgroup$
0
$\begingroup$

The "balls in bins" problem is a "word" problem. Let $\Lambda$ be our alphabet. So we have a finite set of characters. For example, take the capital letters of the English alphabet as an example. We are constructing strings or "words" from these letters. So if we have an $n$ digit string, how many possibilities do we have?

There are $26$ capital letters and $n$ spaces. So the first space has $26$ options, the second space has $26$ options, etc. Each space is chosen independently of the other spaces, so by rule of product we multiply, to get $26^{n}$ as our count.

With the balls in bins analogy, the "bins" are the slots for the letters and the balls are our characters. So we could have red and blue balls, and $10$ slots. Each slot can have either a red or blue ball, giving us two options per slot. By rule of product, we multiply, as each bin gets a ball independently of the others. This gives us $2^{n}$.

Notice with "balls in bins" that ordering matters. So $RBR \neq BRB$ if you have red and blue balls. With stars and bars, ordering isn't so important. This is the "doughnuts" problem. I send you to the store to get a dozen doughnuts. I need three glazed doughnuts, five chocolate frosted doughnuts, and four eclairs. Do you care if the cashier puts in glazed, frosted, eclair, eclair vs. glazed, glazed, frosted, eclair? Not really. This is an important difference for stars and bars vs. balls in bins.

Personally, I don't like the visual of "stars and bars." I think the Diophantine equation is a nicer way to reason this out. So we have $n$ distinct items (in the case of the doughnuts example above, $n = 3$). We need $k$ items. How many ways are there to get $k$ items using only the $n$ distinct products. So we have:

$x_{1} + x_{2} + x_{3} + ... + x_{n} = k$

Now suppose I don't care how many of each type of doughnut you get, just that you get a dozen doughnuts. Our equation is:

$x_{1} + x_{2} + x_{3} = 12$

We can derive the stars and bars formula using a generating function. So we use a formal geometric series to count, where the exponent of $x$ indexes. So $x^{0}$ says get none of that kind, $x^{1}$ says to get $1$, etc.

Now for glazed doughnuts, our generating function is:

$$f(x) = \sum_{i=1}^{\infty} x^{i} = \frac{1}{1-x}$$

We have no restrictions on eclairs or frosted doughnuts, so $f(x)$ describes the number of ways to get those as well. So the number of ways to choose a dozen doughnuts can be described with $(f(x))^{3} = \frac{1}{(1-x)^{3}}$. We want a dozen doughnuts, so we care about the coefficient of $x^{12}$, which gives us the number of ways of ordering a dozen doughnuts. We can either manually expand out the product or we can use an identity.

Note that:

$$\frac{1}{(1-x)^{r}} = \sum_{i=0}^{\infty} \binom{i + r - 1}{i} x^{i}$$

And so our count for $x^{12}$ is $\binom{12 + 3 - 1}{12}$.

Notice how the generating function gives us a clean way to set it up and model the situation, which makes it easier to see combinatorially what is going on.

$\endgroup$

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.