I've also been searching for a good undergraduate book for combinatorics, which I'm teaching next fall for the first time. One book not mentioned yet is Brualdi's "Introductory Combinatorics"[1]

It looks to be at a good level for beginning undergraduates while still maintaining a reasonable level of rigor. Some of the comments at Amazon seem say that the most recent edition is an improvement over the previous ones. Anyone have any specific experiences with this book?

[1] http://www.pearsonhighered.com/educator/product/Introductory-Combinatorics/9780136020400.page