Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik.
http://en.wikipedia.org/wiki/Concrete_Mathematics
I agree that this book does not make a standard combinatorics course, although it has chapters on binomial coefficients, special numbers, and generating functions. At least it's a very accessible additional source. It definitely does not require a solid background in algebra or calculus.