2
$\begingroup$

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 :(

$\endgroup$
6
  • $\begingroup$ If you select at least two beans of each color, you may as well set those 10 beans aside at the outset, so you're really just picking 10 more beans, no? $\endgroup$ Dec 2, 2015 at 20:05
  • $\begingroup$ So we have 5!5! + whatever is left, right? Because we have (5*5) (4*4) (3*3) (2 *2) (1*1) ways to select 10 beans, yes? $\endgroup$
    – GeekyOmega
    Dec 2, 2015 at 20:08
  • $\begingroup$ To be clear, when you pick $n$ beans, do you care about the order in which they were selected or not? $\endgroup$ Dec 2, 2015 at 20:10
  • $\begingroup$ I don't believe so because it asks about "how many ways". However, given my background in combinatorics and counting the different ways something can happen, the problem above has completely destroyed me. I think you have sniffed out exactly why I don't understand what is going on. $\endgroup$
    – GeekyOmega
    Dec 2, 2015 at 20:13
  • 1
    $\begingroup$ IMO, the fact that there is an unlimited amount of jelly beans available implies that the beans of each color are identical, in which case the order does not matter, in which case $5^{20}$ is the wrong answer for the first part of the question. $\endgroup$ Dec 2, 2015 at 20:34

2 Answers 2

1
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ I discussed this with a coworker and we have a debate. He contends it should be $24 \choose 20$ because that is the number of ways to select $m = 20 $ objects from a collection of $n = 5$ different objects where $n+m -1 \choose m$. His approach makes no sense to me because we only have 20 beans and you enumerate the different possibilities that can exist for them. $\endgroup$
    – GeekyOmega
    Dec 2, 2015 at 21:07
  • 1
    $\begingroup$ ${24 \choose 20} = {24 \choose 4}$ $\endgroup$
    – Pieter21
    Dec 2, 2015 at 22:00
  • $\begingroup$ Okay, that just did not happen. I'm going to ask you let me off the hook in that I'm seriously sleep depraved. I'm surprised my colleagues didn't catch this either though. Maybe we all need to take a break. That being said, your approach is easier to understand. :) $\endgroup$
    – GeekyOmega
    Dec 2, 2015 at 22:06
  • 2
    $\begingroup$ Small note: This solution doesn't use generating series to obtain the desired answers, contrary to what the title wants. I have a (rather lengthy) solution of my own in preparation, where I use generating functions as specified, but I feel that the concept of generating functions must be properly explained as well, so I'll see when I can get it up. In the meantime, I refer anyone interested in reading up the topic on his own to the (freely and online available) book generatingfunctionology by Herbert S. Wilf. $\endgroup$
    – MonadBoy
    Dec 3, 2015 at 11:54
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Please point out if anything seems unclear / off with this post, as it is so large. $\endgroup$
    – MonadBoy
    Dec 3, 2015 at 12:26
  • $\begingroup$ This post was beautiful and concise. I am impressed you read this text in high school. Thank you for your time. It was well invested. $\endgroup$
    – GeekyOmega
    Dec 3, 2015 at 14:24
  • $\begingroup$ Well, I'd credit the author of that book, in all modesty. It is very readable :) $\endgroup$
    – MonadBoy
    Dec 3, 2015 at 14:47
  • 1
    $\begingroup$ I suppose I should mention that you don't have to explicitly multiply all those polynomials (which is very cumbersome), as you can use the geometric series $1/(1-x)=1+x+x^2+\ldots$ instead of the "bean polynomials", multiply those together (the terms of exponent $21$ or greater cannot end up in $x^{20}$ terms anyway, so they don't change the end result), and compute the $x^{20}$ coefficient of the power series $1/(1-x)^5$. That however needs deeper knowledge of how the series $1/(1-x)$ acts on other power series upon multiplication (or maybe calculus...). Something to look forward to, I guess. $\endgroup$
    – MonadBoy
    Dec 3, 2015 at 14:54
  • $\begingroup$ That's fantastic. Is there any way I can PM you on stackoverflow or ask for your email address if I have any other questions similar to above or to ask for good tips like the one you just suggested (and good literature). I actually had a very solid math background but let it rot through neglect. Trying to pick it up again to be solid again. I never touched the subject above though and I forgot all my series knowledge. $\endgroup$
    – GeekyOmega
    Dec 3, 2015 at 15:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .