What are some good references for learning about combinatorics and enumeration?

[CRGreathouse]

First, is this the right area to post topics on combinatorics? It seemed better than "General Math" to me, but I'm not quite sure this is right either.

OK, my question is a general one. I've been trying to calculate some things recently, and it strikes me that what I'm doing is essentially combinatorical. I haven't had any classes in the field, though, which means that at best I'm wandering in the dark. Are there any good *basic* references out there, online or otherwise? Edit: I'm mainly interested in enumeration, for what it's worth.

It seems that what I want to learn about is the Pólya enumeration theorem, but looking over what information I found (e.g. MathWorld's entry and a few other online sources) I wasn't able to properly understand it. What do I need to do to get this background?

 

[0rthodontist]

The prereqs for combinatorics at my school are discrete math and a recommendation--not a requirement--of Algebra I. It does cover Polya. How do you know that you want Polya's enumeration theorem? What is an example of what you're trying to do?

 

[CRGreathouse]

The prereqs for combinatorics at my school are discrete math and a recommendation--not a requirement--of Algebra I. It does cover Polya. How do you know that you want Polya's enumeration theorem? What is an example of what you're trying to do?

Well, I'm not in school -- I just like math. I do have a BS in it, so I have some background, but nothing in the particular area.

I'm interested in problems similar to this: Count the number of transitive and antisymmetric binary relations with n elements, assuming the elements are distinguishable. Here's a post of mine where I asked for help -- just more of the same. At that point I wasn't really thinking "combinatorics", though.

Related sequences (OEIS): A002416, A053763, A047656, A006125, A006905, A085628, A000079, A000798, A001035, A000110, A000670, A000142, A083667, A047656, A006125, A000595, A000273, A003085, A000666, A000088, A091073, A079265, A000070, A000027, A001930, A000112, A000041, A011782, A000012, A083670, A001174, A000568. To me, these are the numbers of relations (distinguishable or otherwise) with certain qualities: reflexivity, completeness, etc. and their respective combinations, as far as they make sense. I did manage to extend a few of these beyond where Sloane had them (and sent them to him, of course). Most or all also have topological explanations -- I did take an undergrad course in topology, though that's not the first thing my mind jumps to.

I see Polya's enumeration theorem mentioned sometimes when I look up things on these. I've read a few papers, but since I don't know combinatorics and its specialized cant, I get lost quickly.

Papers:

Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2, http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html
S. R. Finch, "Transitive relations, topologies and partial orders", http://algo.inria.fr/csolve/posets.pdf

 

[CRGreathouse]

I just started this PDF, since it looks like it's an introduction to the subject. Is it any good?

Renzo Sprugnoli, An Introduction to Mathematical Methods in Combinatorics, http://www.dsi.unifi.it/~resp/Handbook.pdf

 

[3trQN]

I thank you for that

 

[philiprdutton]

I took combinatorial optimization using genetic algorithms at university of tulsa. First you have realize (as I am sure you already do) that there are hundreds of kinds of problems that have already been proven to be NP complete (a computer science nomenclature).

My experience was first that I was very naive to think I could crack an NP complete problem. I chose "The Independent Set" problem of graph theory. I banged on it a long time. I eventually discovered an algorithm which was already in the literature. Of course, my algorithm just gives you a near optimal solution and it could just be one of many such solutions. Anyway, after you play with some of these problems you start to see how each one starts to exhibit certain properties. It is hard to explain. But in fact, you can analyze a problem (something you observe that is not in the literature, for example) and map it to another problem that is already predetermined to be NP complete. That is how many of the problems have joined the ranks of NP complete.

I would suggest casually playing with some of the np complete graph problems. If you do not digg in and get your ink pen dirty with some of these problems you just will not get the intuitive feel or that deeper inside look. Search for "NP complete enumeration" and you can get something perhaps to look at. There should be an authorative list of NP complete problems. Just pick on and play for awhile before looking at the literature.

 

[CRGreathouse]

I took combinatorial optimization using genetic algorithms at university of tulsa. First you have realize (as I am sure you already do) that there are hundreds of kinds of problems that have already been proven to be NP complete (a computer science nomenclature).

That sounds a lot more like my numerical analysis class than combinatorics per se. Now I'm as interested in the NP/P issues as anyone, but I've put more thought into the smaller end of the scale, to wit ZPP vs P and P vs. NC. The latter is particularly interesting in light of the multiprocessor/multicore craze these days.

Of course I must admit that I've done no proofs in this area except of the most trivial sort, but as I tend toward the computational side of number theory I keep abreast of developments in theoretical computer science since they directly influence it.