# What are the prerequisites for combinatorics?

I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that would be useful in day to day algorithmic analysis, and come up during senior level interviews at software companies. My math knowledge is very rudimentary. I want to say it's almost at a 9th or 10th grade level. Will I need to go back and refresh on algebra, or can I jump right into combinatorics? What are the prerequisites?

-
I think using "combinatorics" in this context is slightly wrong, but your other tag "discrete-mathematics" is more accurate. – BBischof Nov 6 '10 at 16:45
You may also be interested in this question math.stackexchange.com/questions/6245/… – BBischof Nov 6 '10 at 16:46

In my opinion the "prerequisite" knowledge for Combinatorics/Discrete mathematics is primarily basic logic.

Many people would say that this falls under discrete math, but I think the main things that you will need to understand are Truth Tables, De Morgan, Induction, set theory and such. Many discrete books cover these topics, so don't be too afraid. If you really want to get another book to cover this material, the first chapter of Herstein does this very well.

As far as algorithm analysis, you will probably want to understand some basic asymptotics, big O, and recursion, all of these things can be found in most introductions to discrete math, such as the often recommended Concrete Mathematics.

If you are particularly worrying about Geometry, Trig and Calc, I wouldn't. A few things from PreCalc/Calc will be useful, but I don't thing overwhelmingly so. I don't expect you to see much Trig, and Geometry will mostly used to provide examples.

The other question I linked in the comment will also be useful probably.

-

To "strengthen your understanding of the math that is directly useful to practical computer science" I think your best bet is simply to master the material in Graham; Knuth; Patashnik. Concrete Mathematics and Rosen: Discrete mathematics and its applications.

-
Concrete Mathematics is great (well-written, lots of good stuff, one of my top five favorite math books), but just be aware that if your algebra is "almost at a 9th or 10th grade level" you will find it fairly advanced. – Mike Spivey Nov 6 '10 at 17:00

Graham et al. and Rosen are both excellent books but they are also very comprehensive. If you are looking for something that is shorter (definitely not comprehensive) and more like an "outline" you might find this small paperback useful:

Essential Discrete Mathematics for Computer Science by Todd Feil and Joan Krone, Prentice-Hall, 2003.

The chapters are somewhat independent and include pseudo-code for some algorithms.

-