Book on combinatorial identities

Question

Do you know any good book that deals extensively with identities obtained using combinatorial and/or probabilistic arguments (e.g., by solving the same combinatorial or probability problem in two different ways)?

Answer 1

Sometimes we can hear about combinatorial proofs of a problem and sometimes we hear about proofs based upon formal or symbolic methods. Combinatorial proofs typically search for bijections between known finite sets and the objects we like to count and going this way we try to get a deeper understanding about the underlying structure of these objects. On the other hand symbolic methods are based upon different types of generating functions. With the help of these functions many counting problems can be easily solved by rather simple algebraic methods using formal, finite operations and without considering limits or other analytic means.

One classic providing an enormous amount of combinatorial proofs is Richard P. Stanleys Enumerative Combinatorics Volume $1$ and $2$. You was asking for more than one proof of a structure and you will be satisfied. E.g. example $6.19$ of Volume $2$ gives you $66$ different sets of the famous Catalan Numbers $\frac{1}{n+1}\binom{2n}{n}$ at hand. You will find there many wonderful examples with combinatorial proofs.

Some other prior classic is Advanced Combinatorics $(1974)$ from Louis Comtet. This book is also a great guide through the landscape of combinatorics. It contains many particular problems with combinatorial proofs.

These two books are my recommendation for combinatorial proofs. I'd like to add some more hints to complete the (my) picture:

The book Combinatorial Identities from John Riordan ($1968$) is a wonderful classic with thousands of binomial identities which are systematically organised. But it does not typically provide combinatorial proofs. It's a great reference to search for different classes of combinatorial identities.

If you also consider to have a look at the other, formal side then H.Wilf's book Generatingfunctionology is the perfect, easily accessible starter to see the power of formal series.

A great book, presumably playing in the same league as Stanleys Enumerative Combinatorics is Analytic Combinatorics from Philippe Flajolet and Robert Sedgewick. Here you will not only find a definitive reference of symbolic methods in Combinatorics (first part of the book), but also how the great power of complex analysis can be used to get information about asymptotic behaviour, singularity analysis of generating functions and many other beautiful things.

The guiding theme for all these references is: Read it, analyse it (at least partly) and have fun :-)

Answer 2

There is an old book by Riordan called Combinatorial Identities,

a compilation by H. Gould Combinatorial Identities: a standardized set of tables,

and later manuscripts on the same subject downloadable from Gould's web page, http://www.math.wvu.edu/~gould/

Answer 3

This may not be what you are looking for, but you Gian-Carlo Rota and Kenneth Baclawski's Introduction to Probability and Random Processes is freely available for download online and is a classic introduction to probability, with an emphasis on the underlying combinatorics. You could certainly get a lot of ideas for how to generate the types of identities you are looking for, but as far as I know it does not have an encyclopedic list of such identities.

Answer 4

I am not sure, but probably the book A=B qualifies? But it's a great book anyway…

Answer 5

The Probabilistic Method by Alon and Spencer has a lot of really nice asymptotics and estimates that can be derived using probabilistic tools. Much of it is focused around Ramsey theory, random graphs and various counting problems in Linear algebra, along with some combinatorial games.

Answer 6

Proofs that Really Count by Benjamin and Quinn is very good.