# What is combinatorics?

I've tried to search the web and in books, but I haven't found a good definition or definitive explanation of what combinatorics is.

Could anyone give me a definition/explanation of combinatorics, of what combinatorics is, and what it deals with?

References that contain an answer to the question are appreciated.

Edit: I sees that many are saying that combinatorics deal with counting, but that doesn't seem to be the correct answer, for two reasons: first of all saying that combinatorics is just about counting means, at least to me, putting it inside set theory, because it's there where you define and deal with the more wide concept of counting; another reason is that there are some branch of mathematics which usually fall under combinatorics but doesn't directly deal with counting: for instance combinatorial design doesn't explicitly deal with counting.

-
Seems related: What's Combinatorial Proof/Object/etc.?. – Srivatsan Oct 18 '11 at 15:08
Should this be CW? – JavaMan Oct 18 '11 at 16:30
"My research is in combinatorics, which seems to be the study of how many different ways you can define the word `combinatorics'." -- Ian Wanless (users.monash.edu.au/~iwanless) – Douglas S. Stones Oct 18 '11 at 21:13
The Science of Discworld books define it (from memory) as "the art of counting things without actually counting". – TRiG Oct 18 '11 at 21:35
– Pacerier Jul 12 '14 at 17:32

In The Two Cultures Of Mathematics, Tim Gowers offers a rather expansive concept:

I often use the word "combinatorics" not quite in its conventional sense, but as a general term to refer to problems that it is reasonable to attack more or less from first principles. (This is really a matter of degree rather than an absolute distinction.) Such problems need not be discrete in character or have much to do with counting. Nevertheless, there is a considerable overlap between this sort of mathematics and combinatorics as it is conventionally understood.

-
On that definition, wouldn't much of logic fall under combinatorics? – Doug Spoonwood Oct 18 '11 at 22:50
@Doug I totally agree,which is why I was a bit baffled by Gowers' "definition"-it's really more of an intuitive description then a definition. Not that's bad,mind you-but ineff was asking for a rigorous definition.I have serious doubts this qualifies-with all due respect to Professor Gowers. – Mathemagician1234 Oct 19 '11 at 4:53
@DougSpoonwood I disagree with you, for instance there're some results of model theory that I shouldn't say can be proved from first principles, infact they need a lot of set theory (two example come to my mind: compactness theorem and Löwenheim–Skolem theorem), of course all this depend on what you mean by first principles. On the other end if we consider combinatorics just as theory of counting I suppose that then it should fall under set theory, which is the theory of bijection and deal with counting. – Giorgio Mossa Oct 19 '11 at 8:41
@ineff Again,it really depends,like you said,on where you put the floor in the analysis. Gowers himself sort of begrudgingly admits this: "This is really a matter of degree rather then an absolute distinction." – Mathemagician1234 Oct 19 '11 at 17:07

According to Wikipedia:

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and studying combinatorial structures arising in an algebraic context, or applying algebraic techniques to combinatorial problems (algebraic combinatorics).

-
I had already read the definition in wikipedia but it doesn't seem to me a definitive definition. – Giorgio Mossa Oct 18 '11 at 21:47
@ineff: Having read through the answers so far, the Wikipedia ‘definition’ seems better than the others to me: Firstly, it doesn’t over-emphasize enumeration, and, secondly, it states that what is being studied are “discrete structures” (rather than “things” or “objects”). (I’m always slightly amazed at how reliable Wikipedia often is on mathematics.) – David Bevan Oct 20 '11 at 12:11
@DavidBevan I think I could agree with you, but there doesn't mean that wikipedia's definition it's good, from my point that just mean that nobody give a answer good enough. But just to be clear the reason why I don't like wikipedia's definition is that it seems to me that is too vague. – Giorgio Mossa Oct 20 '11 at 14:26
@ineff: I think the Wikipedia definition actually reflects the fact that combinatorics is an area of study that is hard to delineate precisely. – David Bevan Oct 21 '11 at 7:52

As a combinatorialist, I agree with the notion that combinatorics is roughly about "counting" things. I disagree, however, with the assertion that such things must be discrete or even countable (countable here is meant in the mathematical sense). To support this sentiment, I provide an example.

One of the ongoing projects which has emerged in my field is to count the number of $k$-point configurations in a particular space. The well know Erdos-distance problem is one example:

Erdos (1946): Given a finite set $E \subset \mathbb{R}^n$, is it true that $E$ determines at least $|E|^{\frac{2}{n} + o(1)}$ distances?

There are also continuous versions of these problems. For instance, let $C_k(E)$ denote the set of $k$-point configurations with vertices lying in $E \subset \mathbb{R}^n$. What is the minimal value $\alpha > 0$ such that $\dim_{\mathcal H}(E) > \alpha$ implies that $C_k(E)$ has positive Lebesgue measure? Here, $\dim_{\mathcal{H}} (E)$ denotes theHausdorff dimension of $E$. Essentially, we want to "count" how many triangles we can find in a sparse (fractal) subset of a plane. We do this by utilizing Hausdorff dimension. In this sense, we are still "counting" objects, though the set of objects is uncountable.

-
Out of curiosity, do you include infinite combinatorics in combinatorics, in set theory, or in both? – Brian M. Scott Oct 23 '11 at 23:18
@BrianM.Scott: Whatever you mean by infinite combinatorics, the long story short is that I tend to think of myself as a combinatorialist and number theorist, by which I mean that work usually deals with number theory and is highly combinatorial in nature. Otherwise than these distinctions, I tend not to throw labels on anything. – JavaMan Oct 24 '11 at 0:22
Infinite combinatorics would cover things like the $\Delta$-system lemma and the partition calculus (= infinitary Ramsey theory, e.g., $\kappa\to(\kappa,\omega)^2$ for regular $\kappa\ge\omega$) and the Erdős-Rado theorem). – Brian M. Scott Oct 24 '11 at 4:27

Have you looked at Section 1.1 ('How to count') in Stanley's book Enumerative Combinatorics Volume I? It doesn't give a concise answer to your question, but it does explain what combinatorialists do and thus answers your question to the extent that the answer is 'Combinatorics is what combinatorialists do'.

-

Combinatorics is one of the most fascinating and frustrating branches of mathematics.For some bizarre reason no one really seems to understand,many mathematics students find it impossibly difficult while some find it as easy as breathing. It's also pretty difficult to precisely define.

Classically, combinatorics deals with finite sets of objects and the various ways their subsets and their elements can be counted and ordered.This definition seems the most reasonable to me.However, a number of mathematicians have vehemently disagreed. In fact,I once tried to define combinatorics in one sentence on Math Overflow this way and was vilified for omitting infinite combinatorics.I personally don't consider this kind of mathematics to be combinatorics, but set theory. It's a good illustration of what the problems attempting to define combinatorial analysis are.The best definition I can give you is that it is the branch of mathematics involving the counting and ordering of subsets of sets of objects.

As for textbooks, there's fortunately quite a few good ones. I first tried to learn combinatorics from the old classic Combinatorial Analysis by Liu. Much easier,well written and more informative is the terrific Introductory Combinatorics by Richard Brauldi. More modern and equally good are the books of Milkos Bona; A Walk Through Combinatorics and An Introduction To Enumerative Combinatorics Both books are outstanding, with the former being more comprehensive and the latter focusing more on counting techniques. Lastly, there's a terrific book by one of the great Hungarian masters; Discrete Mathematics by Laszlo Lovasz. Deep and complete, it's a really good introduction by one of the best practitioners.

That should get you started. One last thing: As I said, many talented mathematics students and mathematicians don't find this their cup of potion.As a result, you may find it frustrating and at times,begin to doubt your own mathematical ability. Keep in mind combinatorics has frustrated many an otherwise great mathematician and not to let it get to you. But it's hard to doubt that the skills learned in combinatorics are vital and important to the training of anyone interested in serious problem solving.

-
Adam Smith: Not to be adversarial here, but just because you have not meet many) great mathematicians who are frustrated with combinatorics does not mean that Mathemagician1234 has not, or I have not, or that they aren't out there somewhere. Have you met all mathematicians to check? So go easy on him. :) Mathematics requires a great deal of specialization, and in my opinion even some great mathematicians aren't that able in certain areas. – Rex Butler Oct 18 '11 at 17:54
-1 I prided myself on being able to do rather difficult combinatorics problems in elementary school (though I did not know what they were called at the time), and I am no "great mathematician". If an elementary student can do combinatorics, it is a far cry from "impossibly difficult". – BlueRaja - Danny Pflughoeft Oct 18 '11 at 20:54
@Blue Raja I said "..many mathematics students FIND IT impossibly difficult,while some find it as easy as breathing." You clearly fell into the latter part of the partition of students.I think I made it clear it was a subjective thing that was different for everyone. Interestingly,the people who are exceptionally good at combinatorics generally find out very early-the reason is because these kinds of counting problems usually require no prerequisite mathematical knowledge and therefore are ideal to begin training rank beginners with in problem solving. – Mathemagician1234 Oct 18 '11 at 22:20
I have now cleared the comments Mathemagician1234 made in response to Adam, as well as the secondary comments concerning the exchange. – Zev Chonoles Oct 23 '11 at 15:41

Personally, I see "combinatorics" as the "art of counting", which implies that the underlying objects are at least countable (= discrete), but better finite. I find it natural that "graph theory" is filed under "combinatorics" (because graphs are usually discrete, and there is a lot to count about graphs).

The queen of combinatorics is generatingfunctionology.

-
+1 for an interesting read, Thanks! – K-RAN Oct 18 '11 at 21:11
+1 for a great classic. It's not strictly speaking a general combinatorics text, but it certainly has a wealth of material that would be relevant to such a course-and it IS beautifully written! – Mathemagician1234 Oct 19 '11 at 4:56

My answer would be a branch of math that helps count things.

Some of the simple counting questions are how many ways can you order things; How many ways are there to pick 12 donuts out of 3 styles at a donut shop; etc. Obviously, these are very simple counting questions and are usually covered in pre-combinatoric classes, but are part of Combinatorics.

I took a Combinatorics class last year and this was our book: Combinatorics - A Guided Tour. It was very helpful and easy to understand as long as you've had some higher math.

Hope this helps.

-