Beauty and the Beholder

I had the good fortune of running into Bib Ladder on a recent trip to Vancouver. We had been talking for about 15 minutes when I happened to mention a beautiful mathematical result I had seen recently. My comment elicited the following conversation.

``Now, professor, that waitress over there is beautiful, I've heard some beautiful music in my lifetime, seen some beautiful scenery around these parts, but mathematics doesn't spring to mind with the word beautiful.''

I laughed and replied, ``Mathematicians have a strong sense of what is meant by beauty in mathematics. In fact, I am going to show you a very beautiful mathematical result within a poker context. Several months ago someone posed the following question on rec.gambling.poker: If 26 cards are randomly drawn from a standard 52-card deck, what is the probability the 26 cards do not contain a four-of-a-kind of some rank?

Now if someone started working on the problem, I suspect they would start by looking at the different kinds of patterns arising because of trying to avoid having quads among the 26 cards. They would count how many choices there are for each pattern and so on. That kind of approach leads quickly to a fair number of cases, but it certainly will produce a solution as long as you keep track of all the cases. All in all, the approach will work in spite of being a messy way to solve it.

So to solve the problem posed on RGP. We know the total number of ways of choosing 26 cards is C(52,26). All we need to do is count the number of choices which do not contain any quads and divide by C(52,26). Do you agree, Bib?''

``Yeah, that's all we need to know.''

``Now comes the magical moment, Bib. Let f(x) be the polynomial given by

You might complain that the expression is not really an answer because the coefficients are not explicitly displayed. This leads to the realm of what it means to answer a question. For me the encoding of the answer in the form of f(x) is a perfectly acceptable answer. It is concise, easy to write, easy to remember and, more importantly, easy to expand if we actually want one of the coefficients. It takes just a few seconds to ask a program like MAPLE to expand f(x). So, Bib, let's get the probability originally asked for on RGP. First, C(52,26) = 495,918,532,948,104. The coefficient of x²⁶ in f(x)is 213,751,778,697,216 giving us a probability of .431 that there are no quads among the 26 chosen cards.

I hope you see why I believe it is a beautiful solution.''

``Well, professor, there is a certain elegance in what you have written, but I have no understanding of why it works as you say it does.''

``Alright, I'll explain it carefully. First, notice there are 13 factors in the product making up f(x). What relevance does 13 have for a deck of cards, Bib?''

Bib thought a moment and then responded, ``That's the number of ranks in a deck.''

``That's right, Bib. Each factor corresponds to a rank. Now let's consider the factor 1 + 4x + 6x² + 4x³ itself. The first term is 1, which is the same as x to the zero power. The number of ways we can choose zero cards of a given rank is one; that is, don't choose any of them. The number of ways we can choose one card of a given rank is four and that is the coefficient of x. The number of ways we can choose two cards of a given rank is six and that is the coefficient of x². Finally, there are four ways of choosing three cards of a given rank and that is the coefficient of x³. So the factor itself, which corresponds to a rank, encodes the information of how many ways we can choose cards of a given rank. The exponent of x represents the number of chosen cards of that rank, and the coefficient of xⁱ represents the number of ways of choosing i cards of that rank. So you see, Bib, f(x) is not being pulled out of the blue. Everything has meaning.''

``Yeah, I'm beginning to realize it isn't black magic.''

``The last step in understanding why f(x) does what I claim is to think about what it means to multiply 13 factors. Most people miss this step because of the way we are taught to multiply. For example, suppose you were asked to find the product (2 + 3 + 2)(3 + 1)(2 + 1 + 3). All of us would perform the additions first and get , but in doing so we overlook another way of thinking about a product; namely, doing the products first and then adding. If we take the product that way, we get 2 times 3 times 2, followed by 2 times 3 times 1, and so on until we perform the addition at the end after taking 18 separate products. In other words, we take all possible choices of one term from each of the three factors, multiply and then add. For the preceding numerical example the latter method is much more laborious. But for our polynomial f(x), the second method explains why it is counting what I claim it is counting.

We choose one term from each of the 13 factors. When you take the product of the 13 terms, you add exponents and multiply coefficients. Adding exponents amounts to keeping track of how many cards you have chosen because each individual exponent measures how many cards of that rank you have chosen. Multiplying coefficients measures the number of ways you can choose that particular pattern of ranks because each individual coefficient is the number of ways of choosing that many cards of the given rank. Finally, you add all coefficients with the same exponent to give you the final coefficient of each power of x; that is, the total number of ways of choosing the particular number of cards. It is easy to see there are no four-of-a-kinds because the basic factor allows us to choose only zero, one, two or three of the given rank.''

``Well, professor, I'll have to think about it some but I have a glimmer of understanding what individual pieces mean.''

``The polynomial f(x) is an example of what is called a generating function. A variation of the question asked on RGP is to ask for the probability of randomly choosing i cards from the deck so that neither the i cards nor the 52-i cards left over have quads in them (this was asked on RGP when i = 26). The only difference now is that we cannot allow zero cards to be chosen of any rank. So the generating function which works for this example is (4x + 6x² + 4x³)¹³. The coefficient of x²⁶ is 114,781,763,690,496 giving a probability of .231 for randomly splitting the deck into two sets of 26 cards and having neither set contain quads.

Finally, as another example, the generating function for the number of ways of choosing i cards from a 52-card deck so that there are no quads or trips would be (1+4x+6x²)¹³. These three examples of generating functions may allow you to handle similar problems.''

``This has been a deep conversation, professor. I've got to hit the road now but I'll see you for the Harvest Classic in November.''