I found Concrete Mathematics to be a bit dense and not very suited for self learners like me. Also it does not cover the basics like proofs, counting etc.

I've read good reviews of Susana Epp's Discrete Mathematics With Applications, and I liked what I read in a preview. It's expensive, though, so I'm waiting for the international edition (about 1/3 the cost), which is due out next month.