I am interested in specific examples and applications of enumerative combinatorics in Computer Science -- concrete problems in this field that make explicit use of the concepts and ideas from combinatorics. Are there any good references that you can point me to (books, lectures, ...)?
A little treasure is the 30 years old Mathematics for the Analysis of Algorithms by D.E. Knuth and D.H. Greene.
From the preface: ... Much of the material is drawn from the starred sections of The Art of Computer Programming, Volume 3.
Analysis of algorithms, as a discipline, relies heavily on both computer science and mathematics. This report is a mathematical look at the synthesis - emphasizing the mathematical perspective, but using motivation and examples from computer science.
It covers binomial identities, recurrence relations, operator methods and asymptotic analysis, ...
Many years ago when I studied computer science I was fascinated about the cool Cookie Monster, used to analyse hashing and introduced in section 3.1. In fact nearly each section from this book we've studied in a combinatorics seminar had this wow - effect.
A very attractive book, with a virtuous teaching and excellent references on this topic is "Combinatorial Enumerative" (in Spanish), written by the mathematician of Costa Rica, Eduardo Piza Volio, Editorial of the University of Costa Rica (2003). I attached bibliography in which there are other references.
Maybe you can help this book:
Enumerative Combinatorics by Richard P. Stanley Download as pdf
Other interesting books:
Combinatorics by RUSSELL MERRIS, California State University, Hayward Download as pdf
A trick that I've been employing on several occasions is ternary number base enumeration:
The emphasis is on enumeration rather than counting if I understand the question correctly. The perfect match would be the combstruct package that is included with Maple. This software is a companion to the book Analytical Combinatorics by Flajolet and Sedgewick, which is the canonical text and basically provides a map of future computer science research for decades to come. Highly recommended. Computer science has a particular focus on trees and combstruct really shines here, providing total enumeration as well as generating functions and functional equations. The landmark paper by Flajolet et al. on random mapping statistics (which are closely related to the labeled tree function) is discussed at this MSE link. The Maple package is used the following MSE combstruct link, I and this MSE combstruct link, II. The book Analytical Combinatorics is unprecedented in that it pioneered the use of complex variable methods to treat generating functions that arise from species theory and the folklore theorem of combinatorial enumeration (providing instant translation from species equations to generating functions), thereby putting an emphasis on unifying combinatorial methods with complex variable techniques. Another relevant early text is the book Graphical Enumeration by Harary and Palmer which contains many results on labeled and unlabeled trees as well as accessible presentations of the Polya Enumeration Theorem and of Power Group Enumeration. Finally a classic contender for the enumeration of unlabeled trees is the NAUTY package by McKay, which was used at this MSE NAUTY link. (Use Pruefer codes for labeled trees.)