How to apply generating series to solve this following enumerative problem?

Question

Background

I am a software engineer and I have been picking up combinatorics as I go along. I am going through a combinatorics book for self study and this chapter is absolutely destroying me. Sadly, I confess it makes little sense to me. I don't care if I look stupid, I want to understand how to solve these problems.

I am studying counting with repetition. That is, generalized binomial coefficients and generating functions.

Problem

Suppose that an unlimited amount of jelly beans is available in each of the five different colors: red, green, yellow, white, and black.

• How many ways are there to select from twenty jelly beans?
• How many ways are there to select twenty jelly beans if we must select at least two jelly beans of each color?

Attempted Solution

• How many ways are there to select from twenty jelly beans?

  $5^{20}$

• How many ways are there to select twenty jelly beans if we must select at least two jelly beans of each color?

I keep thinking of applying the hypergeometric distribution here, but I think this is dead wrong. The entire chapter is on series, so I am confused as to what these series are and why they are being applied to solve these problems? The above solutions (some I am too embarrassed to share) didn't pass the smell test at all :(

Answer 1

My interpretation is that you want to calculate variations like 5 red, 6 yellow, 9 black.

Then for the first problem, you typically select 4 barriers to place between 20 beans.

Before the first barrier, are the red beans, .. after the last barrier the black ones. The barriers take a position, so we have $24 \choose 4$

A barrier on the first position means you have no red beans.

The second problem would be a small variation, just remove the 10 required colored beans and repeat previous calculation with the remaining 10, so we have $14 \choose 4$

Answer 2

The point of using generating functions (or series, if you prefer that term) is to manipulate power series algebraically and/or analytically (but mostly algebraically, to avoid convergence issues), and to extract combinatorial information from the coefficients of the resulting series. For an introductory book that sure helped me when I was learning this stuff back in high-school (in my free time), you might want to have a look at the title generatingfunctionology by Herbert S. Wilf. It is available freely and legally online.

A key quote from that author is the following: "A generating function is a clothesline on which we hang up a sequence of numbers for display."

Now, to help you with those problems. Let's focus on the first one for now. Form the power series which corresponds to choosing how many black jelly beans to take. You want to take any number between 0 and 20 black beans, inclusive. This corresponds to the polynomial $(1+x+x^2+\ldots+x^{20})$. Each exponent tells how many beans you take, and the coefficients (they are all 1) tells in how many ways you can take that many beans. Of course, you can only take 20 beans of the same color in one way, they all end up identical anyways, right?

Now for every other color, do the same thing. You should now have one polynomial $(1+x+x^2+\ldots+x^{20})$ for each of the five colors considered (all polynomials in the same variable $x$).

To compute the number of ways you can generate a hand of 20 beans, we multiply all the five polynomials together (tedious, but you can make some shortcuts to skip a lot of computation once you get the hang of things). This corresponds to the act of choosing some black beans, some red beans, some yellow beans, and so on.

What do you want in the end? You want the number of ways to form a hand of 20 beans. That is the coefficient in front of the $x^{20}$ term in your final polynomial. Why is this? It is because you have formed all possible different 20-bean hands in multiplying all those polynomials together. To convince yourself of this, check that:

• the hand "20 black, no other colors" is formed by taking the $x^{20}$ term from the "black" polynomial, and the constant $x^0$ terms from the others, and multiplying them together,

• that "5 black, 10 red, 5 yellow" stems from taking $x^5$ from the "black" polynomial, $x^{10}$ from the "red", and $x^5$ from the "yellow",

• etc.

I let my computer do the labor of multiplying everything (I don't have too much time on my hands), and ended up with a polynomial having 10626 as the coefficient in front of the $x^{20}$ term. This is the answer to the first question.

Now, for the other question, you already know you choose a minimum of two beans of each color. This means we can cross off all the terms $1$ and $x$ in the "bean polynomials", as we don't consider scenarios where we choose zero or one of any color. Otherwise, the method remains the same. Computing the final polynomial, the coefficient in front of the $x^{20}$ term, our final answer, is 1001.