What sort of math will help me solve programming problems?

Question

I have been looking at various programming problems and algorithms in an effort to improve my programming and problem solving skills. But, I keep running into description like this one:

"Let A = [a1,a2,...,an] be a permutation of integers 1,2,...,n. A pair of indices (i,j), 1<=i<=j<=n, is an inversion of the permutation A if ai>aj. We are given integers n>0 and k>=0. What is the number of n-element permutations containing exactly k inversions?" (SOURCE: http://www.spoj.pl/problems/PERMUT1/)

What kind of math do I need to study in order for this sort of problem description to make sense to me?

Answer 1

Discrete math. It deals with a lot of combinatorics, probability, etc, which is what you have in your problem there. ( http://en.wikipedia.org/wiki/Discrete_mathematics )

Being able to read a set equation probably doesn't hurt either.

Answer 2

Sounds like a typical permutations problem. http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Answer 3

I recommend having a look at one (or both) of the following:

Graham, Knuth Patashnik: Concrete Mathematics

Knuth: The Art of Computer Programming (Vol 1)

They are not easy reads, and you definitely want a background in high school mathematics at least, but they nicely lead from there to the sort of mathematics you describe in your question, and have lots of exercises.

Answer 4

I was in this sort of quandary about a month ago. Until I came about this post from Steve Yegge - Math for Programmers

Very informative, highly recommended read. Hopefully after the read, you'll get pointers to take it from there. All the best.