Saturday, May 26, 2012

Combinatorics

Combinatorics is usually one of the first non-introductory topics in discrete mathematics that students encounter in their mathematical studies. This also makes it one of the hardest topics to get to grips with, as it often requires a different way of thinking from other mathematical fields, such as calculus.

Combinatorics encompasses various subfields of study of discrete structures. In general, when given a problem in combinatorics, it will usually belong to one of three categories:

1) The existence problem. Given a problem, with specific characteristics and parametres, does a solution to this problem exist? For example, the dean's office at a college will want to assign time slots and classrooms to the various courses which will be taught in the semester. Such an assignment must not have two courses at the same time if the same professor is teaching them. (It is also usually desired that, if a lot of students are expected to take two courses concurrently, these courses not be assigned at the same time, if possible). Furthermore, if two courses are at the same time, they should not be assigned to the same room. Finally, if certain courses are expected to have large numbers of students, they should be assigned to large classrooms, so that everyone can have a seat. Given a list of courses, time slots and classrooms can such an arrangement be found? This is the existence problem. Sometimes there are no solutions to these problems. If, for example there is only one professor teaching both calculus and algebra, both classes needing the same single amphitheatre, and there is only one available time slot, the problem becomes impossible.

2) The counting problem. As mentioned before, some problems cannot be solved. Sometimes, on the other hand, a problem will have more than one possible solution. In our classroom assignment question, there could be several different assignments, which all work with the given parametres. The counting problem asks us to find how many different ways a problem can be solved. If there are two courses to be assigned to two different classrooms, at the same time, we can do this in two different ways; either have the first course in the first room and the second one in the second room, or vice versa.

3) The optimisation problem. Having figured out the different ways in which we can solve a given problem, we may then be interested in the best (whatever this means) solution out of the possible ones. For example, in the classroom assignment problem, we may want to pick the assignment that uses the fewest time slots, or the one that uses the fewest classrooms, or even the one with the fewest clashes between courses with common students. The optimisation problem is probably the most important one of the three, in the sense of solving applied problems, but it is often impossible to get started on, without a thorough understanding of the other two.

I will close this post by mentioning that the field of combinatorics is probably the largest one in mathematics, as it encompasses theory which is needed for almost all other mathematical fields. It would be impossible for a simple blog to present it properly, but perhaps in future posts, I may be able to present some of the more fundamental ideas.