13
$\begingroup$

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)?

$\endgroup$
  • 8
    $\begingroup$ Concrete Mathematics by Graham, Knuth and Patashnik has an in depth treatment of combinatorics and discrete maths in general, with a lot of the arguments obtained by solving the same problem in different ways. $\endgroup$ – Thomas Russell Apr 6 '14 at 13:36
  • 2
    $\begingroup$ Nick Loehr's Bijective Combinatorics is probably a good book to look through. He's a professor at my school, and I've only heard excellent things about his teaching. I'm sure his book is just as good. It looks to be an advanced undergraduate or graduate level text, for what it's worth. math.vt.edu/people/nloehr/bijbook.html $\endgroup$ – ml0105 Apr 8 '14 at 21:16
  • 1
    $\begingroup$ Combinatorics Second Edition - Russell Merris is a superb book. ... Annoyingly costly though. Chapter 1 is brilliant. $\endgroup$ – Alec Teal Apr 11 '14 at 14:11
15
+50
$\begingroup$

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 :-)

$\endgroup$
7
$\begingroup$

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/

$\endgroup$
  • $\begingroup$ From what I've seen, these only list combinatorial identities. There are no (combinatorial) proofs. $\endgroup$ – digital-Ink Apr 8 '14 at 21:34
  • $\begingroup$ The book of Riordan is OK. I would have hope for more examples with direct combinatorial arguments, yet the methods presented are interesting and worth studying. $\endgroup$ – digital-Ink Apr 10 '14 at 18:24
  • $\begingroup$ For methods of proof see any compendium of solved combinatorics problems, such as Lovasz' Combinatorial Problems and Exercises, or training manuals for competitions, or a Schaum's outline in combinatorics, or a textbook with a lot of sufficiently hard solved exercises. Every such source I have seen has a chapter or more on combinatorial identities, using generating functions and/or bijective proofs. A long list of textbooks: math.stackexchange.com/questions/15201/… $\endgroup$ – zyx Apr 13 '14 at 22:29
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It's a great book, but it's the very opposite of combinatorial proofs: it describes very general algorithms to prove combinatorial identities mechanically by computer. $\endgroup$ – ShreevatsaR Apr 12 '14 at 9:14
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.