This is a collection of quotes by various authors, trying, succeeding and occasionally failing to define it. They are listed in chronological order. Some of the early quotes are barely comprehensible, later quotes are somewhat defensive and most recent are rather upbeat. Read them all! - IP
P.S. If you are curious about my own views on this, read it in this blog post.
So there arise two kinds of variation: complexion and situs. [In modern terminology, "complexion" are combinations and "situs" are permutations. -- IP] And viewed in themselves, both complexion and situs belong to metaphysics, or to the science of wholeand parts. If we look at their variability, however, that is, at the quantity of variation, we must turn to numbers and to arithmetic. I am inclined to think that the science of complexions pertains more to pure arithmetic, and that of situs to an arithmetic of figure.
It is easy to perceive that the prodigious variety which appears both in the works of nature and in the actions of men, and which constitutes the greatest part of the beauty of the universe, is owing to the multitude of different ways in which its several parts are mixed with, or placed near, each other. But, because the number of causes that concur in producing a given event, or effect, is oftentimes so immensely great, and the causes themselves are so different one from another, that it is extremely difficult to reckon up all the different ways in which they may be arranged, or combined together, it often happens that men, even of the best understandings and the greatest circumspection, ale guilty of that fault in reasoning which the writers on logick call the insufficient, or imperfect enumeration of parts, or cases: insomuch that I will venture to assert, that this is the chief, and almost the only, source of the vast number of erroneous opinions, and those too very often in matters of great importance, which we are apt to form on all the subjects we reflect upon, whether they relate to the knowledge of nature, or the merits and motives of human actions. It must therefore be acknowledged, that that art which affords a cure to this weakness, or defect, of our understandings, and teaches us so to enumerate all the possible ways in which a given number of things may be mixed and combined together, that we may be certain that we have not omitted any one arrangement of them that can lead to the object of our inquiry, deserves to be considered as most eminently ufeful and worthy of our highest esteem and attention. And this is the business of the art, or doctrine of combinations.
The Combinatorial Analysis is a branch of mathematics which teaches us to ascertain and exhibit all the possible ways in which a given number of things may be associated and mixed together; so that we may be certain that we have not missed any collection or arrangement of these things, that has not been enumerated. [..]
Besides its uses in mathematical investigations, it not only enables us to form our ideas of the elegant compositions of design, but to contemplate the prodigious variety which constitutes the beauties of nature, and which arises from the combinations of objects, by their number, forms, colour, and positions. It has a relation to every species of useful knowledge upon which the mind of man can be employed. [..]
It is to be regretted, that in this country, where genius abounds, and where the combinatorial analysis began to dawn (as well as other useful branches of the mathematical sciences), that it is only partially known. [..] To foreigners alone we owe the subsequent improvements and advancement of this branch of mathematical science.
We have continually to make our choice among different courses of action open to us, and upon the discretion with which we make it, in little matters and in great, depends our prosperity and our happiness. Of this discretion a higher philosophy treats, and it is not to be supposed that Arithmetic has anything to do with it; but it is the province of Arithmetic, under given circumstances, to measure the choice which we have to exercise, or to determine precisely the number of courses open to us.
Major Percy A. MacMahon, Combinatory Analysis: A Review of the Present State of Knowledge, in Proc. LMS (1896).
As your retiring President has the opportunity of making a few remarks upon some special topic, I will now pass on to that subject which may possibly be of some interest to those here to-night. It is the combinatory analysis, and my selection is influenced by the belief that this subject is not at present upon a proper footing. Its importance is not fully recognised, because much that properly belongs to it appears under other headings in all recent attempts to organize and arrange the various departments of mathematical science. [..]
The combinatory analysis in my opinion holds the ground between the theory of numbers and algebra, and is the proper passage between the realms of discontinuous and continuous quantity. It would appear advisable [..] to consider the theory of partitions an important part of combinatory analysis. [..]
The subject of combinatory analysis has for forty years been much neglected; may I urge that both the beauty of the methods of research available and the value of the results achieved indicate that it is well worthy the attention of mathematicians?
In conclusion, I will quote tho words of the greatest living English master of pure mathematics—Sylvester—words, which, I believe, are as applicable to tho combinatory analysis as a whole as to that particular branch—the theory of partitions — in connexion with which they were spoken:
Let us subjugate a collection of objects taking into account their qualities and differences each from another, then we are lead, in our mathematical perspective, to the study of integers and their connecting operations, that is, we are lead to Number Theory.
If we, however, disregard the qualities of each individual object and only account for the difference between two objects insofar that they are different, then we are lead to investigations which are concerned with the position, the order, the choosing of these objects. This branch of mathematics is called Combinatorics.
What are now considered the substantial parts of combinatoric have been developed outside of the German Combinatorial School. Associated with the early development are the great names of Pascal, Leibnitz, Wallis, James Bernoulli and De Moivre. [..]
While combinatoric is not now made the subject of lectures in our universities, it is nevertheless of importance. The student acquires much of it during the pursuit of other branches. It is touched upon in the study of ordinary algebra, of determinants, of substitution and group theory, of the theory of numbers, and of the theory of probability.
The Combinatorial Analysis, as it was understood up to the end of the 18th century, was of limited scope and restricted application. [..] Writers on the subject seemed to recognize fully that it was in need of cultivation, that it was of much service in facilitating algebraical operations of all kinds, and that it was the fundamental method of investigation in the theory of Probabilities.
The combinatory analysis as considered in this work occupies the ground between algebra, properly so called, and the higher arithmetic. The methods employed are distinctly algebraical and not arithmetical. The essential connecting link between algebra and arithmetic is found in the circumstance that a particular case of algebraic multiplication involves arithmetical addition. [..] This link was forged by Euler for use in the theory of partitions of numbers. It is used here for the most general theory of combinations of which the partition of numbers is a particular case.
The theory of the partition of numbers belongs partly to algebra and partly to the higher arithmetic. The former aspect is treated here. It is remarkable that in the international organization of the subject-matter of mathematics "Partitions" is considered to be a part of the Theory of Numbers which is an alternative name for the Higher Arithmetic, whereas it is essentially a subdivision of Combinatory Analysis which is not considered to be within the purview of the Theory of Numbers. The fact is that up to the point of determining the real and enumerating Generating Functions the theory is essentially algebraical [..]
Combinatory Analysis is well known even to students of elementary algebra, where it figures under the title of Permutations and Combinations; while in theory of equation the subject is intimately connected with symmetric functions. The formal statement of the objects of this branch of mathematics is that it includes the formation, enumeration, and other properties of the different groups of a finite number of elements which are arranged according to prescribed laws. By its subject-matter combinatory analysis is related to some of the most ancient problems which have exercised human ingenuity.
One of the four grand divisions of what may be called properly static mathematics is the theory of configurations. It includes the construction out of given elements of compound forms under certain given conditions or restrictions [..] These constructions vary from the mere permutation of a linear series of elements up to the complicated trees of chemical combinations studied by Cayley, and in general to all sorts of problems in what has been happily denominated tactics by Cayley, or syntactics by Cournot. [..]
The study of configurations usually begins with combinatory analysis. By this is usually meant the study of arrangements along a line of a collection of objects, either as individuals or in groups; arrangements at the nodes of a lattice, combinations of arrangements. Such problems arise not only as matters of tactic, curious problems or puzzles, but in the determination of the number of such arrangements needed in solving problems in the theory of probabilities.
For some reason which is not at present clear, the theory of the combinations of different sets of similar possibilities (which can conveniently be represented as the distributions of balls in boxes) is of utmost importance in many branches of science. [..] The subject is therefore of great importance in applied as well as in pure mathematics, and might very well prove another example of the extraordinary way in which abstract mathematics leads the way in applied science.
The term "combinatorial analysis" hardly admits of exact definition, and is not used in the International Schedule of pure mathematics. Broadly speaking, it has come to mean the discussion of problems which involve selections from, or arrangements of, a finite number of objects; or combinations of these two operations. For the purpose of this article it will be convenient to use Sylvester's term "tactic" as a synonym for "combinatorial analysis."
Combinatorial Analysis, though a well-recognized part of mathematics, seems to have a poorly defined range and position. Leibniz, in his "ars combinatoria", was the originator of the subject, apparently in the sense of Netto (Lehrbuch der Combinatorik, Leipzig, 1901) as the consideration of the placing, ordering, or choice of a number of things together. This sense appears also in the title, Choice and Chance (W.A. Whitworth, fifth edition, London, 1901), of one of the few books in English on the subject. This superb title also suggests the close relation of the subject to the theory of probability. P.A. MacMahon, in the most ambitious treatise on the subject (Combinatory Analysis, London, vol. I, 1915, vol. II, 1916), says merely that it occupies the ground between algebra and the higher arithmetic, meaning by the latter, as he later explains, what is now called the Theory of Numbers.
A current American dictionary (Funk and Wagnalls New Standard, 1943) defines "combinatoric" – a convenient single word which appears now and then in the present text-as "a department of mathematics treating of the formation, enumeration, and properties of partitions, variations, combinations, and permutations of a finite number of elements under various conditions".
The term "combinatorial analysis" itself, seems best explained by the following quotation from Augustus DeMorgan (Differential and Integral Calculus, London, 1842, p. 335): "the combinatorial analysis mainly consists in the analysis of complicated developments by means of a priori consideration and collection of the different combinations of terms which can enter the coefficients".
No one of these statements is satisfactory in providing a safe and sure guide to what is and what is not combinatorial. The authors of the three textbooks could be properly vague because their texts showed what they meant. The dictionary, in describing the contents of such texts, allows no room for new applications of combinatorial technique (such as appear in the last half of Chapter 6 of the present text in the enumeration of trees, networks, and linear graphs). DeMorgan's statement is admirable but half-hearted; in present language, it recognizes that coefficients of generating functions may be determined by solution of combinatorial problems, but ignores the reverse possibility that combinatorial problems may be solved by determining coefficients of generating functions.
Since the subject seems to have new growing ends, and definition is apt to be restrictive, this lack of conceptual precision may be all for the best. So far as the present book is concerned, anything enumerative is combinatorial; that is, the main emphasis throughout is on finding the number of ways there are of doing some well-defined operation.
This is the only modern book on combinatorial analysis. It will be extremely useful to anyone who wishes to make a systematic study of the subject, as well as to the many mathematicians and mathematical practitioners who are sometimes faced with particular problems involving a count of the number of ways in which some well defined operation can be carried out. Techniques developed in this book are of increasing importance in the study of modern statistics, computing devices, communications engineering and in the recent applications of graph theory to chemistry and problems in the social sciences. [..]
In the two-volume treatise by MacMahon [Combinatory analysis, University Press, Cambridge, 1915–16] many enumeration problems were claimed to be solved when, in fact, they were merely reformulated. In this book such an approach is avoided. Explicit formulae are the order of the day and in many cases the formulae are accompanied by short tables. Nevertheless, the author is usually satisfied with an explicit formula, even though it may be comparatively unmanageable for large values of the arguments. Very little is said about asymptotic developments for such cases. There are many problems usually considered combinatorial in nature in which the question is not primarily "in how many ways can this be done'' but rather "can this be done in at least one way?'' These include important problems of finite geometries, difference sets and related combinatorial designs. Such problems are not treated here.
These omissions are indications of the size of the subject rather than of the shortcomings of the book. In fact, the author has admirably succeeded in marshalling many interesting facts that were not nearly so accessible before. He has infused pattern and order into his subject and will thereby, we hope, attract more mathematicians to this fascinating field.
Some mathematicians feel that combinatorial analysis is not a branch of mathematics but rather a collection of clever but unrelated tricks. This book successfully refutes that viewpoint.
The subject is, without doubt, one of the hardest in which to write an effective exposition. The reason for this is the fact that so much of the material occurs in an isolated fashion in so many different applications both to pure and applied mathematics and to other fields. Combinatorial analysis is a subject in which many of the fundamental results are frequently rediscovered by people in different fields, from first principles. [..]
This book is an excellent introduction to a field of study which so far as the author is concerned covers anything enumerative. The author’s main emphasis throughout is on finding the number of ways there are of doing some well defined operation. [original emphasis]
Combinatorial Mathematics, or “Combinatorics”, regarded as originating in the Ars Combinatoria of Leibniz, has to do with problems of arrangement, operation, and selection within a finite or discrete system-such as the aggregate of all possible states of a digital computer. Until recently, preoccupation with continuous mathematics has inhibited the growth of discrete mathematics. But now it is realized that combinatorial methods can be developed to attack profitably, in modern science and technology, a vast variety of “problems of organized comp1exity” – an apt designation of Warren Weaver. In 1947 Hermann Weyl wrote as follows (rearranged slightly for quotation here):
The modern era has uncovered for combinatorics a wide range of fascinating new problems. These have arisen in abstract algebra, topology, the foundations of mathematics, graph theory, game theory, linear programming, and in many other areas. Combinatorics has always been diversified. During our day this diversification has increased manyfold. Nor are its many and varied problems successfully attacked in terms of a unified theory. Much of what we have said up to now applies with equal force to the theory of numbers. In fact, combinatorics and number theory are sister disciplines. They share a certain intersection of common knowledge, and each genuinely enriches the other.
Combinatorial mathematics cuts across the many subdivisions of mathematics, and this makes a formal definition difficult. But by and large it is concerned with the study of the arrangement of elements into sets. The elements are usually finite in number, and the arrangement is restricted by certain boundary conditions imposed by the particular problem under investigation. Two general types of problems appear throughout the literature. In the first the existence of the prescribed configuration is in doubt, and the study attempts to settle this issue. These we call existence problems. In the second the existence of the configuration is known, and the study attempts to determine the number of configurations or the classification of these configurations according to types. These we call enumeration problems. This monograph stresses existence problems, but many enumeration problems appear from time to time.
It may be remarked that the second category of problems is nothing more than a refinement or obvious extension of the first. This is the case. But in practice if the existence of a configuration requires intensive study, then almost nothing can be said about the corresponding enumeration problem. On the other hand, if the enumeration problem is tractable, the corresponding existence problem is usually trivial.
Though the author equates combinatorial mathematics with combinatorial analysis, his book is addressed to the "new'' combinatorial analysis, whose emphasis lies in the existence rather than the enumerative side of the subject. Indeed, this is the area of his own work.
The field of combinatorial analysis has been shockingly and incredibly neglected of late; too many mathematicians, blinded by their own overspecialized work, regard it with an air of snobbish condescension which betrays a lurking fear of anything that may "rock the boat." Yet, the need for more systematic understanding of combinatorial phenomena is now making itself clearly felt in all branches of mathematics, and even more so in the natural sciences. From the physics of elementary particles to genetics, from communication theory to computing, the need is increasing for the study of discrete structures. In view of this situation, one may predict with fair probability that the next decades will witness an explosion of combinatorial activity not unlike the development of topology since the beginning of this century. In the words of the author, "we believe that the greatest truths of combinatorial analysis are yet to be revealed."
The first issue of this Journal may afford an opportunity to meditate upon the scope, the methods, and the applications of Combinatorial Theory.
This first issue could also be regarded as celebrating the tercentenary of the theory the name of which first appeared in the title of Leibniz's Dissertatio de Arte Combinatoria printed in 1666. Leibniz had great projects and entertained high hopes about the future of his Combinatorial Art. This Art should deal, according to one of his notes posthumously printed, with "the same and the different, the similar and the dissimilar, the absolute and the relative." These words may leave to combinatorial theory a wide enough scope, but they scarcely describe it too clearly. I am afraid that it is impossible to give a satisfactory definition of "Combinatorial Theory" and to trace out a sharp boundary of its subject matter, but mathematicians readily recognize what is of "combinatorial character."
To delimit the methods for solving combinatorial problems seems not only impossible, but may be also undesirable. Yet we have to mention here a favorite tool of combinatorial mathematics: the generating functions. Their name is due to Laplace, but they were already extensively and efficiently used by Euler, and their use was foreshadowed by certain passages of De Moivre.
Leibniz claimed "applications to the whole sphere of sciences" of his Combinatorial Art. We find very little concrete achievement in his Dissertatio on which such a claim could be based, yet it is probably more equitable to regard his words as a prophecy and not as a statement of facts. At any rate, there is a practically unlimited variety of subjects in which combinatorial considerations play a role. Without any pretension to system, I wish to mention a few with which l came into contact through my own work: probability, graph theory, organic chemistry, crystallography, statistical mechanics, propositional logic, switching circuits.
I have failed, I am afraid, in defining the scope or the methods or the applications of Combinatorial Theory, but there is little doubt that this theory was greatly developed in all respects in the last decades and it is to be hoped that this Journal will be a stepping stone to further progress.
Combinatorialists use recurrence, generating functions, and such transformations as the Vandermonde convolution; others, to my horror, use contour integrals, differential equations, and other resources of mathematical analysis.
Combinatorial analysis is a rather fragmentary subject: it has few general techniques and few unifying principles. From time to time, mathematicians (for example, MacMahon) have sought to bring some sort of order and structure to the subject by writing textbooks. This is what Mr. Riordan, one of the world's leading combinatorialists, now sets out to do with combinatorial identities. [..]
Combinatorial theory is the name now given to a subject formerly called "combinatorial analysis" or "combinatorics", though these terms are still used by many people. Like many branches of Mathematics, its boundaries are not clearly defined, but the central problem may be considered that of arranging objects according to specified rules and finding out in how many ways this may be done. If the specified rules are very simple, then the chief emphasis is on the enumeration of the number of ways in which the arrangement may be made. If the rules are subtle or complicated, the chief problem is whether or not such arrangements exist, and to find methods for constructing the arrangements. An intermediate area is the relationship between related choices, and a typical theorem will assert that the maximum for one kind of choice is equal to the minimum for another kind.
Combinatorial analysis, or – as it coming to be called, combinatorial theory – is both the oldest and one of the least developed branches of mathematics. [..] Combinatorial problems are found nowadays in increasing numbers in every branch of science, even in those where mathematics is rarely used.
Combinatorial theory has been slowed in its theoretical development by the very success of the few men who have solved some of the outstanding combinatorial problems of their day, for, just as the man of action feel little need to philosophize, so the successful problem-solver in mathematics feels little need for designing theories, that would unify, ant therefore enable the less-talented worker to solve, problems of comparable and similar difficulty. But the sheer number and the rapidly increasing complexity of combinatorial problems has made the situation no longer tolerable. It is doubtful that one man alone can solve any of the major combinatorial problems of our day.
Though combinatorics has been successfully applied to many branches of mathematics these can not be compared neither in importance nor in depth to the applications of analysis in number theory or algebra to topology, but I hope that time and the ingenuity of the younger generation will change this.
Combinatorial analysis, or combinatorial theory, as it has come to be called, is currently enjoying an outburst of activity. This can be partly attributed to the abundance of new and highly relevant problems brought to the fore by advances in discrete applied mathematics, and partly to the fact that only lately has the field ceased to be the private preserve of mathematical acrobats, and attempts have been made to develop coherent theories, thereby bringing it closer to the mainstream of mathematics.
Nowadays, combinatorial analysis (or “combinatorics”) is the focus of much attention; yet, nowhere in the literature does there seem to be a satisfactory definition of this science and its many ramifications.
We wish to offer here a definition of combinatorics, which depends on the very precise concept of ‘‘configuration.” A configuration arises every time objects are distributed according to certain predetermined constraints.
Just as arithmetic deals with integers (with the standard operations), algebra deals with operations in general, analysis deals with functions, geometry deals with rigid shapes, and topology deals with continuity, so does combinatorics deal with configurations. Combinatorics counts, enumerates, examines, and investigates the existence of configurations with certain specified properties. With combinatorics, one looks for their intrinsic properties, and studies transformations of one configuration into another, as well as “subconfigurations” of a given configuration.
The preoccupations of combinatorics are exactly the same as those of the other branches of modern mathematics. Nevertheless, it is surprising that this particular discipline has developed on the edge of, or away from, the mainstream of modern mathematics. The elementary theorems of the subject have been forgotten and rediscovered several times. [..] It is important to rectify this.
[Berge's book] begins boldly by proposing a definition of combinatoire (combinatorial mathematics): it is the study of configurations (for which a precise definition is possible). The definition given for configuration is: an application of a set of objects in an abstract finite set provided with a known structure; the term application (which needs no translation from French to English) is taken as understood, it seems to mean a functional association of the objects with the elements of the abstract set, that is, a mapping of the object set into the abstract set. The precision is a little illusory since, as the author recognizes, many combinatorial problems are concerned with configurations subject to given constraints, and the character and range of constraints are too varied for exact description.
It is difficult to find a definition of combinatorics that is both concise and complete, unless we are satisfied with the statement “Combinatorics is what combinatorialists do.”
For a long time the aim of combinatorial analysis was to count the different ways of arranging objects under given circumstances. Hence, many of the traditional problems of analysis or geometry which are concerned at a certain moment with finite structures, have a combinatorial character. Today, combinatorial analysis is also relevant to problems of existence, estimation and structuration, like all other parts of mathematics, but exclusively for finite sets.
Most mathematicians of this day, confronted with an argument requiring combinatorial thinking, react with one of two stock phrases: (a) “This is a purely combinatorial argument,” (b) “This is a difficult combinatorial argument.” Hypnotic repetition of either of these slogans is likely to have the same balming effect on the speaker: freed from all scruples, he will pass the buck and unload the work onto someone else’s shoulders.
While the end result of this oft-repeated vignette is an overwhelming variety of problems for specialists in the art, the impression grows that among mathematicians, especially “pure” mathematicians, total ignorance of combinatorial theory is as proudly flaunted as-in bygone days-an aristocrat’s ignorance of his country’s vernacular.
It is tempting to react to this rejection, which in the past has succeeded in finessing combinatorialists into the mathematical proletariat, by a ringing ça ira. This might well take the form of a concerted attack on one of the currently fashionable branches of mathematics. The barrage of definitions and the superstructure of grammatical gamesmanship removed, little more than a few puny combinatorial facts would be left, which would then be dealt an embarrassingly easy coup de grace by the application of standard combinatorial techniques. Fortunately, this course will not be followed, for a sound reason: combinatorialists have better fish to fry.
The author starts with the question: what is combinatorics? He succeeds in answering it no better than others, but a more sincere attempt is made. Six aspects are listed: study of a known configuration; search for an unknown one; exact enumeration of configurations; taking a census of configurations; and optimization.
The current resurgence of combinatorics (also known as combinatorial analysis and combinatorial theory) is by now recognized by all mathematicians. Scoffers regard combinatorics as a chaotic realm of binomial coefficients, graphs, and lattices, with a mixed bag of ad hoc tricks and techniques for investigating them. In reality, there has been a tremendous unifying drive to combinatorics in recent years. We now have a broad and sophisticated understanding of such standard combinatorial concepts as inversion, composition, generating functions, finite differences, and incidence relations.
Another criticism of combinatorics is that it "lacks abstraction." The implication is that combinatorics is lacking in depth and all its results follow from trivial, though possible elaborate, manipulations. This argument is extremely misleading and unfair. It is precisely the "lack of abstraction," i.e., the concrete visualization of the concepts involved, which helps to make combinatorics so appealing to its adherents. On the other hand, the "depth" of the subject is rapidly increasing as it increasingly draws upon more and more techniques and concepts from other branches of mathematics, such as group representation theory, statistical mechanics, harmonic analysis, homological algebra, and algebraic topology, to say nothing of the increasing sophistication of various new purely combinatorial techniques.
In combinatorial mathematics [..] there is now such vigorous activity on so many fronts that an overview of the whole battlefield would show only smoke: is the permanent function really fundamental or just a gadget? same for the Möbius function; is the four color problem a dead end or is its fallout stimulating the whole subject? in what ways will the blossoming study of computer algorithms reshape combinatorics itself? The issues are, of course, not posed in these stark terms, but instead, all areas are being advanced simultaneously, to the despair of those who seek unifying threads.
The history of mathematics shows that a theory almost always originates in efforts to solve a specific problem (for example, the duplication of the cube
in Greek mathematics). It may happen that these efforts are fruitless, and we have our first category of problems:
(I) Stillborn problems (examples: the determination of Fermat primes, or the irrationality of Euler's constant).
A second possibility is that the problem is solved but does not lead to progress on any other problem. This gives a second class:
(II) Problems without issue (this class includes many problems arising from "combinatorics").
A more favorable situation is one in which an examination of the techniques used to solve the original problem enables one to apply them (perhaps by
making them considerably more complicated) to other similar or more difficult problems, without necessarily feeling that one really understands
why they work. We may call these
(III) Problems that beget a method (analytic number theory and the theory of finite groups provide many examples).
In a few rather rare cases the study of the problem ultimately (and perhaps only after a long time) reveals the existence of unsuspected underlying
structures that not only illuminate the original question but also provide powerful general methods for elucidating a host of other problems in other
areas; thus we have
(IV) Problems that belong to an active and fertile general theory (the theory of Lie groups and algebraic topology are typical examples at the
present time).
It is difficult to imagine that Combinatorial Theory, which today is one of the most rapidly developing and highly popular parts of Mathematics, was only a short thirty years ago a nearly forgotten throwback to the last century. Relegated to a misty corner of the mathematical edifice the once proud Ars Combinatoria was practiced almost clandestinely and only by a vanishingly small group of mathematicians, who appeared to their contemporaries as dedicated though somewhat misguided eccentrics.
Even a sleepy observer of the contemporary mathematical scene cannot but be struck by the spectacular growth of combinatorial studies in the very recent past. As little as, say, twenty years ago enthusiasm for work in this field was still regarded as a sign of mild eccentricity, and the problems investigated by combinatorialists were nowhere near the centre of the mathematical stage. Thus the late J. H. C. Whitehead probably did no more than express a tacit consensus when he described the theory of graphs as 'the slums of topology'. Nous avons changé tout cela-decisively and rapidly. [..]
[Combinatorics] is obviously no longer to be shrugged off as being merely of marginal significance-its presence is too strongly felt and its influence too pervasive for the continuation of Whitehead's dismissive stance. Indeed, every one of a score of outstanding mathematicians who have contributed crucial ideas to the recent development of combinatorics could assert with rightful pride: exegi monumentum. Voices have even been heard insisting on the fundamental role of combinatorics for the entire body of mathematical knowledge. Claims as far-reaching as these seem to me excessive; but it is symptomatic of the current prestige of the subject that they should be made at all. [..]
As I see it, combinatorics is a range of linked studies which have something in common and yet diverge widely in their objectives, their methods, and the degree of coherence they have attained. Most are concerned with criteria for the existence of certain 'patterns' or 'arrangements' or 'configurations', where these terms need to be interpreted in a very broad sense. Further, in many problems, the emphasis is on quantitative aspects: we seek to determine or estimate the number of objects of a specified kind or to characterize the patterns which are, in some way, extremal. Now the expert can live a happy and useful life without the aid of my fumbling attempts at elucidation while the mathematician unfamiliar with combinatorial problems will not derive from them any perceptible enlightenment. By the shades of Euclid and Aristotle! I have evidently not supplied much of a definition-but is there a better one?
It is now generally recognized that the field of combinatorics has, over the past years, evolved into a fully-fledged branch of discrete mathematics whose potential with respect to computers and the natural sciences is only beginning to be realized. Still, two points seem to bother most authors: The apparent difficulty in defining the scope of combinatorics and the fact that combinatorics seems to consist of a vast variety of more or less unrelated methods and results. As to the scope of the field, there appears to be a growing consensus that combinatorics should be divided into three large parts:
Having vegetated on the fringes of mathematical science for centuries, combinatorics has now burgeoned into one of the fastest growing branches of mathematics – undoubtedly so if we consider the number of publications in this field, its applications in other branches of mathematics and in other sciences, and also the interest of scientists, economists and engineers in combinatorial structures. The mathematical world was attracted by the successes of algebra and analysis and only in recent years has it become clear, due largely to problems arising from economics, statistics, electrical engineering and other applied sciences, that combinatorics, the study of finite sets and finite structures, has its own problems and principles. These are independent of those in algebra and analysis but match them in difficulty, practical and theoretical interest and beauty.
Yet the opinion of many first-class mathematicians about combinatorics is still in the pejorative. While accepting its interest and difficulty, they deny its depth. It is often forcefully stated that combinatorics is a collection of problems which may be interesting in themselves but are not linked and do not constitute a theory. It is easy to obtain new results in combinatorics or graph theory because there are few techniques to learn, and this results in a fast-growing number of publications.
The above accusations are clearly characteristic of any field of science at an early stage of its development – at the stage of collecting data. As long as the main questions have not been formulated and the abstractions to a general level have not been carried through, there is no way to distinguish between interesting and less interesting results – except on an aesthetic basis, which is, of course, too subjective. Those techniques whose absence has been disapproved of above await their discoverers. So underdevelopment is not a case against, but rather for, directing young scientists toward a given field.
In my opinion, combinatorics is now growing out of this early stage. There are techniques to learn: enumeration techniques, matroid theory, the probabilistic method, linear programming, block design constructions, etc. There are branches which consist of theorems forming a hierarchy and which contain central structure theorems forming the backbone of study: connectivity of graphs (network flows) or factors of graphs, just to pick two examples from graph theory. There are notions abstracted from many nontrivial results, which unify large parts of the theory, such as matroids or the concept of good characterization. My feeling is that it is no longer possible to obtain significant results without the knowledge of these facts, concepts and techniques. (Of course, exceptions may occur, since the field is destined to cover such a large part of the world of mathematics that entirely new problems may still arise.)
Perhaps combinatorics is no longer deemed to be the slum of topology but it still has a remarkable polarising effect on mathematicians. The practitioners of combinatorics tend to idolise it as the only truly interesting branch of mathematics, while people not active in combinatorics are likely to have no respect for it and dismiss it as a collection of scattered results and trivial artificial problems. This highly unsatisfactory situation cannot be blamed entirely on the youth of the subject, though it is certainly one of the reasons. Those of us who work in combinatorics are also at fault, for most of our journals do publish more than their fair share of below par papers. Furthermore, as combinatorics fails to command the respect of the majority of the mathematical community, some combinatorialists feel entitled to disregard the huge developments in the main branches of mathematics.
There are signs that these lean years for combinatorics will soon be over. This is the hope expressed by Lovász in the Preface of Combinatorial problems and exercises. "Having vegetated [..]" [This book] will certainly help to establish the respectability and worth of the subject.
La combinatoire est en gros l’étude des géométries finies. Une partie est consacrée à la construction et à l’étude qualitative des configurations finies (graphes, plans projectifs, matroides, et plus récemment immeubles....). D’un autre côté, on s’occupe à compter les objets d’une certaine espèce, le plus souvent au moyen de séries génératrices; inversement, et cette préoccupation est plus récente, on s’efforce d’interpréter des identités entre polynômes et séries de puissances en introduisant les structures finies que comptent les coefficients.
La partie la plus vénérable de la combinatoire s’occupe des propriétés des permutations (avec ou sans répétitions) et des fonctions symétriques; les tableaux de Young y jouent un rôle prédominant. Il s’agit d’un retour aux traditions de l’Algèbre du siècle dernier, mais enrichi par tout l’arsenal des notions modernes. On met l’accent sur les méthodes constructives et algorithmiques; les points de contact avec le reste des Mathématiques sont nombreux, et en particulier avec la théorie des groupes, la géométrie algébrique, la topologie des classes caractéristiques, et aussi la physique mathématique. De plus, les problèmes et les méthodes de l’informatique théorique jouent un rôle croissant.
What is combinatorics? You could say that combinatorics is that part of mathematics that concerns itself with finite systems. But this is not entirely true: the theory of finite groups, rings and fields does not belong to combinatorics. It is with combinatorics as it is with asymptotics. You would like to define asymptotics as the theory of limits, but large parts of the differential– and integration-calculus do not belong to asymptotics.
For a long time combinatorics consisted only of puzzles and games. Before the 1960s there was probably no course in combinatorics.
Combinatorics is mainly about counting. The nice thing about counting is that you learn something about the thing that you are counting. While counting, you notice that your knowledge about the subject is not sufficiently precise, and so counting becomes an educational activity. When two sets have the same number of elements, you try to understand why that is the case by establishing some natural bijection between the two.
The progress of mathematics can be viewed as a movement from the infinite to the finite. At the start, the possibilities of a theory, for example, the theory of enumeration appear to be boundless. Rules for the enumeration of sets subject to various conditions, or combinatorial objects as they are often called, appear to obey an indefinite variety of and seem to lead to a welter of generating functions. We are at first led to suspect that the class of objects with a common property that may be enumerated is indeed infinite and unclassifiable.
As cases file upon cases, however, patterns begin to emerge. Freakish instances are quietly discarded; impossible problems are recognized as such, and what is left organizes itself along a few general criteria. We would like these criteria to eventually boil down to one, but by and large we must be content with a small finite number.
Combinatorics can be classified into three types: enumerative, existential, and constructive. Enumerative combinatorics deals with the counting of combinatorial objects. Existential combinatorics studies the existence or nonexistence of combinatorial configurations. Constructive combinatorics deals with methods for actually finding specific configurations (as opposed to merely demonstrating their existence theoretically). [..] In constructive combinatorics, the problem is usually one of finding a solution efficiently, [..] using a reasonable length of time.
Combinatorics is an honest subject. No adèles, no sigma-algebras. You count balls in a box, and you either have the right number or you haven’t. You get the feeling that the result you have discovered is forever, because it’s concrete. Other branches of mathematics are not so clear-cut. Functional analysis of infinite-dimensional spaces is never fully convincing: you don’t get a feeling of having done an honest day’s work. Don’t get the wrong idea—combinatorics is not just putting balls into boxes. Counting finite sets can be a highbrow undertaking, with sophisticated techniques.
Much combinatorics of our day came out of an extraordinary coincidence. Disparate problems in combinatorics. ranging from problems in statistical mechanics to the problem of coloring a map, seem to bear no common features. However, they do have at least one common feature: their solution can be reduced to the problem of finding the roots of some polynomial or analytic function. The minimum number of colors required to properly color a map is given by the roots of a polynomial, called the chromatic polynomial; its value at N tells you in how many ways you can color the map with N colors. Similarly, the singularities of some complicated analytic function tell you the temperature at which a phase transition occurs in matter. The great insight, which is a long way from being understood, was to realize that the roots of the polynomials and analytic functions arising in a lot of combinatorial problems are the Betti numbers of certain surfaces related to the problem, Roughly speaking, the Betti numbers of a surface describe the number of different ways you can go around it. We arc now trying to understand how this extraordinary coincidence comes about, If we do, we will have found a notable unification in mathematics.
It has been said that combinatorics has too many theorems, matched with very few theories; Stanley's book belies this assertion.
What new things will come from mathematics? I want to mention two of them. The first new thing is a very old one and has been on the backburner of mathematics — it is combinatorics.
One of the main reasons for the fast development of Combinatorics during the recent years is certainly the widely used application of combinatorial methods in the study and the development of efficient algorithms. It is therefore somewhat surprising that many results proved by applying some of the modern combinatorial techniques, including Topological methods, Algebraic methods, and Probabilistic methods, merely supply existence proofs and do not yield efficient (deterministic or randomized) algorithms for the corresponding problems.
There are people who feel that a combinatorial result should be given a "purely combinatorial" proof, but I am not one of them. For me the most interesting parts of combinatorics have always been those overlapping other areas of mathematics.
Combinatorics belongs to those areas of mathematics having experienced a most impressive growth in recent years. This growth has been fuelled in large part by the increasing importance of computers, the needs of computer science and demands from applications where discrete models play more and more important roles. But also more classical branches of mathematics have come to recognize that combinatorial structures are essential components of many mathematical theories.
Does the heart of mathematics lie in the building of structures or in the solving of individual problems? Not an either – or question, to be sure, but one that is particularly effective in splitting the ranks of combinatorialists. Use of algebraic structure to explain discrete phenomena will be central to some, to others grotesque. A clever argument is beautiful to the problem-solver, a curiosity to a structuralist. The very term "combinatorial methods", has to this author, an oxymoronic character. It is the brilliant proofs, those that expand and/or transcend known technologies, which express the soul of the subject.
Combinatorics is special. Most mathematical topics which can be covered in a lecture course build towards a single, well-defined goal, such as the Prime Number Theorem. Even if such a clear goal doesn’t exist, there is a sharp focus (e.g. finite groups). By contrast, combinatorics appears to be a collection of unrelated puzzles chosen at random. Two factors contribute to this. First, combinatorics is broad rather than deep. Second, it is about techniques rather than results.
Combinatorics could be described as the art of arranging objects according to specified rules. We want to know, first, whether a particular arrangement is possible at all, and if so, in how many different ways it can be done. If the rules are simple, the existence of an arrangement is clear, and we concentrate on the counting problem. But for more involved rules, it may not be clear whether the arrangement is possible at all.
The field normally classified as algebra really consists of two quite separate fields. Let us call them Algebra One and Algebra Two for want of a better language. Algebra One is the algebra whose bottom lines are algebraic geometry or algebraic number theory. Algebra One has by far a better pedigree than Algebra Two, and has reached a high degree of sophistication and breadth. Commutative algebra, homological algebra, and the more recent speculations with categories and topoi are exquisite products of Algebra One.
Algebra Two has had a more accidented history. [..] In the beginning Algebra Two was largely cultivated by invariant theorists. Their objective was to develop a notation suitable to describe geometric phenomena which is independent of the choice of a coordinate system. In pursuing this objective, the invariant theorists of the nineteenth century were led to develop explicit algorithms and combinatorial methods. The first combinatorialists, MacMahon, Hammond, Brioschi, Trudi, Sylvester, were invariant theorists. One of the first papers in graph theory, in which the Petersen graph is introduced, was motivated by a problem in invariant theory. Clifford's ideal for invariant theory was to reduce the computation of invariants to the theory of graphs. [..]
Algebra Two has recently come of age. In the last twenty years or so, it has blossomed and acquired a name of its own: algebraic combinatorics. Algebraic combinatorics, after a tortuous history, has at last found its own bottom line, together with a firm place in the mathematics of our time.
A recent newcomer to the the center stage of modern mathematics is the area called combinatorics. Although combinatorial mathematics has been pursued since time immemorial, and at a reasonable scientific level at least since Leonhard Euler (1707–1783), the subject has come into its own only in the last few decades. The reasons for the spectacular growth of combinatorics come both from within mathematics itself and from the outside.
Beginning with the outside influences, it can be said that the recent development of combinatorics is somewhat of a cinderella story. It used to be looked down on by “mainstream” mathematicians as being somehow less respectable than other areas, in spite of many services rendered to both pure and applied mathematics. Then along came the prince of computer science with its many mathematical problems and needs — and it was combinatorics that best fitted the glass slipper held out.
The developments within mathematics that have contributed to the current strong standing of combinatorics are more difficult to pinpoint. One is that, after an era where the fashion in mathematics was to seek generality and abstraction, there is now much appreciation of and emphasis on the concrete and “hard” problems. Another is that it has been gradually more and more realized that combinatorics has all sorts of deep connections with the mainstream areas of mathematics, such as (to name the most important ones) algebra, geometry, probability and topology.
[..] Fortunately, the problems and results of combinatorics are usually quite easy to state and explain, even to the layman. Its accessibility is one of its many appealing aspects.
First, what is combinatorics? I have never been able to find a satisfactory answer to this question. The term "combinatorics" seems to refer to discrete or finite aspects of mathematics, rather than those involving continuity. This definition won't do. There are combinatorial aspects of all mathematical subjects, especially analysis, and continuous aspects are perfectly acceptable in combinatorics. Furthermore, there fields that can be and are called combinatorial topology, combinatorial geometry, and algebraic combinatorics; logic and probability are highly combinatorial subjects.
Yet, there is a perfectly good definition of the subject, or rather of the concept of a combinatorial argument. Combinatorics is the area of mathematics that is concerned with, relates to, employs, or studies combinatorial arguments. So what is a combinatorial argument? [..] A combinatorial argument is the one that consists predominately of ingenuity or detailed reasoning rather than knowledge of existing mathematics. This is in contrast with knowledge-based argument, which relies heavily on piecing together known results. [..]
Combinatorics will survive as long as mathematics does. Some of it, particularly Algebraic Combinatorics, has already developed into an ordinary legitimate branch of mathematics with a close relationship to the study of group representations. Others will be (and have been) incorporated into applied fields like Operations Research or Theoretical Computer Science. But the real world will still create new variations of problems, which will still require new methods and new ideas, and these will qualify as combinatorics in all respects. [..]
There is one other direction in which combinatorics can develop in importance both within mathematics and without, and that is in expanding the notion of mathematics as a kind of aesthetics, as an art form. [..] Mathematics, and, more specifically, combinatorics, is full of intellectually beautiful arguments and structures. These constructs are an important part of the appeal of mathematics to mathematicians. They represent an important aesthetic resource of mankind, yet they lie hidden to almost everyone outside mathematics, and to many within it. That mathematics is a realm of magnificent aesthetic joys was one of the best kept secrets of the 20th century.
Combinatorics appears to many to consist of a large number of isolated problems and results, and therefore to be at a disadvantage in this respect. Each result individually may well require enormous ingenuity, but ingenious people exist, especially in Hungary, and future generations of combinatorialists will not have the time or inclination to read and admire more than a tiny fraction of their output.
Let me attempt to answer this criticism. It is certainly rare in combinatorics for somebody to and a very general statement which suddenly places a large number of existing results in their proper context. It is also true that many of the results proved by combinatorialists are somewhat isolated and will be completely forgotten (but this does not distinguish combinatorics from any other branch of mathematics). However, it is not true that there is no structure at all to the subject. The reason it appears to many mathematicians as though combinatorics is just a miscellaneous collection of individual problems and results is that the organizing principles are less explicit.
Henry Whitehead reportedly said, “Combinatorics is the slums of topology”. This prejudice, the view that combinatorics is quite different from ‘real mathematics’, was not uncommon in the twentieth century, among popular expositors as well as professionals. In his biography of Srinivasa Ramanujan, Robert Kanigel describes Percy MacMahon in these terms:
While many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, without relying on many deep, well developed tools, the modern theory has already grown out of this early stage. [..] Most of the new significant results obtained in the area are inevitably based on the knowledge of these well developed concepts and techniques, and while there is, of course, still a lot of room for pure ingenuity in Discrete Mathematics, much of the progress is obtained by relying on the fast growing accumulated body of knowledge. [..]
It seems safe to predict that in the future there will be additional incorporation of methods from other mathematical areas in Combinatorics. However, such methods often provide non-constructive proof techniques, and the conversion of these to algorithmic ones may well be one of the main future challenges of the area. Another interesting recent development is the increased appearance of Computer aided proofs in Combinatorics, starting with the proof of the Four Color Theorem, and including automatic methods for the discovery and proof of hypergeometric identities. A successful incorporation of such proofs in the area, without losing its special beauty and appeal, is another challenge. These challenges, the fundamental nature of the area, its tight connection to other disciplines, and the many fascinating specific open problems studied in it, ensure that Discrete Mathematics will keep playing an essential role in the general development of science in the future as well.
Combinatorics could be described as the study of arrangements of objects according to specified rules. We want to know, first, whether a particular arrangement is possible at all, and, if so, in how many different ways it can be done. Algebraic and even probabilistic methods play an increasingly important role in answering these questions. If we have two sets of arrangements with the same cardinality, we might want to construct a natural bijection between them. We might also want to have an algorithm for constructing a particular arrangement or all arrangements, as well as for computing numerical characteristics of them; in particular, we can consider optimization problems related to such arrangements. Finally, we might be interested in an even deeper study, by investigating the structural properties of the arrangements. Methods from areas such as group theory and topology are useful here, by enabling us to study symmetries of the arrangements, as well as topological properties of certain spaces associated with them, which translate into combinatorial properties.
EVERYTHING IS COMBINATORICS. Classify Lie Algebras? It is just root systems and Dynkin Diagrams. Finite Groups? The Monster is a Combinatorial Design. Even when it is not obviously combinatorics, it could be made so. If it is too hard for us, then we need a computer! But computer science is all Discrete Math, alias combinatorics. In a way Logic is too. But Logic is so low-level, like machine language. It is much more fun and gratifying to work in Maple, and do higher-level combinatorics.
Enumerative problems arise spontaneously in various fields of mathematics, computer science, and physics. Among the most generous suppliers of such problems, let us cite discrete probability theory, the analysis of the complexity of algorithms, and the discrete models of statistical physics, like the famous Ising model. More generally, counting the objects that occur in one’s work seems to answer a natural curiosity. It helps to understand the objects, for instance to appreciate how restrictive are the conditions that define them. It also forces us to get some understanding of the structure of the objects: an enumerative result never comes for free, but only after one has elucidated, at least partly, what the objects really are.
It is impossible to define combinatorics, but an approximate description would go like this. We are given the job of arranging certain objects or items according to a specified pattern. Some of the questions that arise include:
Combinatorics must always have been fun. But when and how did it become a serious subject? I see several main steps in this development:
RPS: Right now, I think it’s a very good, extremely active subject. But I think to do really high-level research now, particularly in algebraic and enumerative combinatorics, which I worked in, you have to know more than you used to. Back when I was a graduate student, you could use the simplest results from other areas like topology. Take the Euler characteristic. You could interpret that combinatorially and come up with all kinds of interesting results. Now, the topological combinatorics gets into some of the deeper more recent aspects of topology. Combinatorial representation theory is a huge subject now, probably one of the main areas of combinatorics. At the beginning, the very simplest representation theory – groups acting on sets – was enough to get all kinds of neat things. Now you have to be into all the latest algebras, like affine Hecke algebras, quivers, and very sophisticated, mainstream stuff that people are working on. You have to know more now than you used to.
There are various ways in which one can try to define combinatorics. None is satisfactory on its own, but together they give some idea of what the subject is like. A first definition is that combinatorics is about counting things. [..]
Combinatorics is sometimes called “discrete mathematics” because it is concerned with “discrete” as opposed to “continuous” structures. Roughly speaking, an object is discrete if it consists of points that are isolated from each other and continuous if you can move from one point to another without making sudden jumps. [..] There is a close affinity between combinatorics and theoretical computer science (which deals with the quintessentially discrete structure of sequences of 0s and 1s), and combinatorics is sometimes contrasted with analysis, though in fact there are several connections between the two.
A third definition is that combinatorics is concerned with mathematical structures that have “few constraints.” This idea helps to explain why number theory, despite the fact that it studies (among other things) the distinctly discrete set of all positive integers, is not considered a branch of combinatorics.
Although combinatorics is probably as old as the human ability to count, the field has experienced tremendous growth during the last fifty years and has matured into a thriving area with its own set of problems, approaches, and methodology.
It is hard to give a rigorous definition of combinatorics. Instead, let us start with a few examples to illustrate what the area is about. [...] The examples above suggest that combinatorics is a basic mathematical discipline that plays a crucial role in the development of many other mathematical areas.
Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics.
We may loosely describe [combinatorics] as the branch of mathematics concerned with selecting, arranging, constructing, classifying, and counting or listing things. [..]
Much of combinatorics originated in recreational pastimes [..] But in recent years the subject has developed in depth and variety and has increasingly become a part of mainstream mathematics. Prestigious mathematical awards such as the Fields Medal and the Abel Prize have been given for groundbreaking contributions to the subject, while a number of spectacular combinatorial advances have been reported in the national and international media.
Undoubtedly part of the reason for the subject's recent importance has arisen from the growth of computer science and the increasing use of algorithmic methods for solving real-world practical problems. These have led to combinatorial applications in a wide range of subject areas, both within and outside mathematics, including network analysis, coding theory, probability, virology, experimental design, scheduling, and operations research.
Click here to return to Igor Pak Home Page.
Last updated: 4/17/2017.