Today's Math Lesson: Can You Choose?

One of the famous problems in discrete mathematics is the handshake problem. Ten people are in a room together. Everybody is going to shake hands exactly once with everybody else. How many handshakes are there?

Well, a big part of doing math is to realize that the answer won't change just because we make everybody get organized instead of all milling around the room at the same time. So, one way to do the problem is to picture the people as all lined up, then have the person furthest from the door walk down the line shaking hands, then go on out the door (she shook hands with everybody once - she's done!). That person would shake hands with 9 people (not herself) before she left. The next person in line does the same, but now there are only eight people left for him to shake hands with before he leaves. The next person would have 7 people to shake hands with and so on, until the last person would have no one to shake hands with (but he has already shaken hands with everybody else as they left). So everybody got one handshake from everyone else and there were 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 = 45 handshakes in all. One way to add these up is to remember our old mathematician friend Carl Gauss, sometimes called "the greatest mathematician since antiquity".

The story (probably untrue) goes that Gauss, while misbehaving in primary school, was told by his teacher to add up the first 100 counting numbers: 1 + 2 + 3 + ... + 98 + 99 + 100. The teacher was surprised when young Carl gave him the correct answer within a few seconds. The trick he saw was that if you add the outside two numbers, 1 and 100, you get 101. You also get 101 when you add the next two numbers from the outside, 2 and 99, and the next pair as well, 3 and 98. If you keep doing this, since there are 100 numbers, you will get 50 pairs of numbers that add up to 101 and 50 X 101 is 5050, which is the correct answer.

In our example the pairs add up to 9 ( 9 and 0, 8 and 1, 7 and 2, etc.) and there are 5 pairs, so 9 X 5 = 45 handshakes.

One of the great things about mathematics is that a trick that works consistently is usually given a symbolic form to make things easier to talk about. The everyday name given to the handshake problem is "choose" (the more classy word used is combination). It works for any problem in which you have a pool of objects and you want to know how many ways that the objects can be connected to each other if ORDER DOESN'T MATTER and NO OBJECT CAN BE CONNECTED TO ITSELF OR REUSED. These rules are important. Let's give some examples. In our handshake problem, there were 10 people and we were going to connect 2 at a time. We won't count person 1 shaking hands with person 2 as a different handshake from person 2 shaking hands with person 1 (ORDER DOESN'T MATTER) and no one is going to shake hands with him/herself (NO OBJECT CAN BE CONNECTED TO ITSELF). We would say then that there are 10 choose 2 ways to shake hands and our symbol looks like this: 

Let's suppose that there are 20 people on math team (I know that's a ridiculously low number for such a popular group, but suppose its a really small school) and we want to choose 4 people at random to represent the team on the scholastic bowl competition. Suppose the twenty people are named A, B, C, and so on through T. Let's see if our rules apply. If group A,G,R,T were chosen, would we count G,A,T,R as a different group. Nope, so order doesn't matter. And would a group of 4 be made if we chose A,A,B,E. No, that would only be three people, so no name can be reused. Both rules are satisfied, so the number of different foursomes that could be selected would be "20 choose 4" which is 4845. If you want to see how to calculate the answer, you can go here.

This would not work if we wanted to choose four people from the 20 to be officers for the Math Team, because now order does matter: A,G,R,T is a different slate of officers than G,A,T,R because a different person is President in the two groups, and while I wouldn't mind A as Vice President, I sure wouldn't vote for him for President (picture Joe Biden).

In the Illinois Lotto game, there are 52 balls in the hopper (1 through 52) and 6 are selected which gives us "52 choose 6" different combinations that could be a winner. That's 20,358,520, with one winner, so your probability of winning is about 1 in 20 million. So, yeah, I guess the lottery is a tax on people who don't understand mathematics.

It turns out that chooses are a very important concept in mathematics. They show up in lots of different places. When you raise (a+1) to the 10th power and multiply it all out, the coefficients of the terms are the chooses you can get using 10 as the big number.
        a¹⁰ + 10 a⁹ + 45 a⁸ + 120 a⁷ + …    the 10 is "10 choose 1", the 45 is "10 choose 2" (remember?), the 120 is "10 choose 3", and so on. Because a quantity like a + 1 has two terms, it is called a binomial, and chooses are often also called "binomial coefficients" for that reason.                                                                                                                                                       The hardest class I had to take to get my masters degree in mathematics at Northern University was Combinatorics. A subtle change in the wording of the problem would yield an entirely different answer. And you would often get tripped up because you misread the conditions (order did matter after all). But it was also the most interesting class I took and I enjoyed it when the math team topic for the month was probability. It meant I could dust off all those things I learned from Professor Schwarz, even though I still have the 1st homework assignment which he returned to me with the notation, "If you are struggling with this, maybe you should rethink your major." I got an A- in the class. So, bite me, Dr. Schwarz. Thanks for the motivation, Dr. Schwarz.