Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In his article 2 cultures Timothy Gowers states that the structure in combinatorics

is there in the form of somewhat vague general statements that allow proofs to be condensed in the mind, and therefore more easily memorized and more easily transmitted to others.

I just started to learn combinatorics, or, more generally, discrete mathematics, and would like to know if there is such a thing as a list of these general statements/ principles somewhere, preferably in the form of a (freely available) article with lots of examples.
So far my problem is that I do not know what tools exist and how to possibly apply them to problems. This results in me trying to solve problems of discrete mathematics with more or less bare hands.

To give you an idea of what I'm looking for I shall present some examples myself (please note: I came up with some of the principles myself, so they might be inaccurate. If they are, please point this out):

  • When trying to prove a certain equality combinatorically, one tries to show that both sites of the equality are the cardinality of one set. Doing so, sums are related to partitions of sets, products are related to products of sets and binomial coefficients tell you that this set has something to do with choosing elements from some other set.
  • To prove the existence of 'big' subgraphs with certain features of some graph $G$ which has certain (other) properties, it can help to look at maximal or maximum subgraphs with certain properties. For example, to show that every $k$-regular graph $G$ has as a subgraph a circle of size at least $k + 1~$ just look at a maximal path in $G$. Pick one of its endpoints, observe that the neighbours of it must all be on the path and now you're done because the part of the path up to the ultimate neighbour of your endpoint together with the edge connecting it with the endpoint is a circle that meets the required criterion

I hope you got an idea of what I am looking for: a list of principles together with examples of how and in which situations to apply these principles helping me to tackle combinatorical problems and to get a better understanding of the field as a whole.
Just to make sure you do not get me wrong: I am not expecting to get a list which enables me to solve many problems just by looking at the appropriate entry of that list and applying what's written there. This list is supposed to be like a toolbox which someone shows (lends) to me with some hints on how to possibly use these tools, so that I can go out and try them out at different problems seeing where I succeed and where I do not.

share|improve this question
add comment

1 Answer

Take a look a this article by Doron Zeilberger: http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/enu.html It might not have everything you're looking for, but it sure will be an enjoyable read!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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