Combinatorics

No one seems to enjoy me talking about stuff that I ate, so instead I shall endeavor to talk about something much more interesting: math. In a recent post, or more specifically, the comments on a recent post, the topic of combinatorics came up, and since that is an area of math that most people aren't probably familiar with, I think it stands to reason that it might be of interest.

So what is combinatorics? It is counting. That seems pretty easy, right? Well, no, it isn't, but it's kind of a fun area of math in that it is like little puzzles that require you to think outside the boxes (this is a pun that will be made clear by a later example). Combinatorics problems are often involve figuring out the number of ways one can group things together or order them or some such thing, and they often seem easy at first, difficult in the middle, and then not so bad at all in the end. I only had one class that dealt with the field specifically, but it often comes up as part of more complex problems in other areas.

Let's take a look at a problem I was thinking about while making the ten kilometer walk back to town today after some scheduling issues.

Let's say we have n balls that are all identical and we have m boxes in which to put the balls. How many ways can we do that? This problem should illustrate combinatorical thinking pretty well.

We could say that for each ball, there are m possible boxes, so we would have m^n ways, which makes sense in light of the first rule of counting, which is that instances that don't affect each other (this is my way of thinking but hand-waving as a professor of mine would say), that is things counted by and, mean multiplication. What I mean here is that we could put the first ball into any of m boxes, and then the second into any of those, so we would have m x m ways of putting two balls into m boxes; extending to n balls would yield m^n. However, if you are clever, you will have noticed a little issue here. That is, overcounting.

Overcounting is one of the problems we always have to watch out for in combinatorics. Here, all the balls are identical, so it doesn't make any sense to think of each ball individually like that. What we are concerned with is how many balls are in each box, which we have overcounted here in that multiple outcomes from our previous approach will be counted separately even though they are identical. Drat.

So, what do we do? This is the stage where the problem seems to be much harder than we anticipated. I have an at least partial solution, but if you want to work it out for yourself, enjoy this picture of some flowers (if the computer starts cooperating).



How about to count this, we count something else? This is the kind of outside the box (it is clear now?) thinking that we often need. So, let's draw a picture, in the abstract sense that mathematicians like. Seriously, draw a picture of n balls all in a line. If we put a vertical line on each end of our line of balls, we can picture boxes here as represented by two lines (each line represents a side of the box, as it were). With just these two lines, we have represented only the left side of the first box and the right side of the last box. If we only have one box, we are already done, but it's not really necessary to draw a picture to figure out how to put balls into one box, is it? Each additional line we add between balls represents simultaneously the right side of the i-th box and the left side of the (i+1)-th box. So now we are just counting how many ways we can put lines in between dots, which seems much more manageable, but is really the same problem. This is the part where the problem seems not so bad again.

Here, however, I propose we make a little caveat to simplify our math. Let us say that while the balls are identical, the boxes are not, so that we are not concerned with instances where we are putting the same number of balls into two boxes and calling them separate instances. That is, we are saying that they are indeed separate instances and we can tell the differences, so we are not overcounting again. One more caveat is that we don't want any empty boxes. Actually, this isn't such a big deal, but it is simpler this way and if we want, we can extend the problem to include empty boxes without much hassle, but simple cases -> complex cases is the general mathematical trend, so I propose we follow it.

Back to the problem at hand, then. How many ways can we place the lines here? First, how many lines do we have? Since each box will have precisely one right side (and one left side), and the last right side is already accounted for, we should have m-1 sides to worry about. And how many places are there to put it? If we number each space, we should see that there is a space to the right (or left) of each ball, except, again, the last, which we already accounted for, so there should be n-1 places. Then it is a simple matter of choosing among m-1 things, n-1 things at a time, or C((m-1), (n-1)) for those people who remember those combination things from algebra II. That is, (m-1)!/(n-1)!(m-n-2)!, if I recall and am applying my algebra correctly. It's important to note that we are using combinations as opposed to permutations, because we are concerned only with where we place the lines, not the order in which we place them. For anyone that wants a discussion of P versus C, I might get to that with another post. If all this is going over your head, don't worry too much about it. It's actually pretty easy, but there might be some notation things going on.

Now, regarding extensions...I proposed leaving no boxes empty because doing so would mean counting instances where two lines are placed in the same spot, which isn't as immediately obvious as a straight-up combination is, but is manageable, and you can probably figure out a way around it. I'm not going to push myself too hard as I am tired today from walking 20 kilometers in the sun. The other caveat deals with a particularly annoying aspect of overcounting, where our current system of lines and dots may turn out not to be sufficient for telling when boxes need to contain different numbers of balls to be considered different. This is the joy of mathematics, though; there is always more to do. Somebody said it was really the only infinite field of study, and that is right, I think. Eventually, theoretically, we could know all the physical laws of the universe, all the things that have happened and how and why, even, but there is always a new math problem sitting on the edge of what we just figured out. It is a beautiful frustration.