Combinatorics

“So there arise two kinds of variation: complexion [combinations] and situs [permutations]. And viewed in themselves, both complexion and situs belong to metaphysics, or to the science of whole and 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.” (Gottfried Leibniz, “Dissertatio de arte combinatoria” [“Dissertation on the Art of Combinations”], Leipzig, 1666)

“Even the wisest and most prudent people often suffer from what Logicians call insufficient enumeration of cases.” (Jacob Bernoulli , 1692)

“[This subject] has a relation to almost every species of useful knowledge that the mind of man can be employed upon.” (Jacob Bernoulli, “Ars Conjectandi”[“The Art of Conjecturing”], 1713)

“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 logic 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 useful and worthy of our highest esteem and attention. And this is the business of the art, or doctrine of combinations.” (Jakob Bernoulli, “Ars Conjectandi” [“The Art of Conjecturing”], 1713)

"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, color, and positions. It has a relation to every species of useful knowledge upon which the mind of man can be employed." (Peter Nicholson, "Essays on the Combinatorial Analysis", 1818)

"Partitions constitute the sphere in which analysis lives, moves, and has its being; and no power of language can exaggerate or paint too forcibly the importance of this till recently almost neglected, but vast, subtle, and universally permeating, element of algebraical thought and expression." (James J Sylvester, "On the Partition of Numbers", 1857)


"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." (William A Whitworth, "Choice and Chance", 1870)


"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." (Percy A MacMahon, "Combinatory Analysis: A Review of the Present State of Knowledge", Proceedings of the London Mathematical Society Vol. s1-28 No. 1, 1896)


"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." (Eugen Netto, "Lehrbuch der Combinatorik", 1901)


"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." (Percy A MacMahon, "Combinatorial Analysis", Encyclopædia Britannica 11th Ed., 1911)


"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 [..]" (Percy A MacMahon, "Combinatory Analysis", Vol. 1, 1915)


"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’." (George B Mathews, "Tactic", Science Progress in the Twentieth Century Vol. 16 No. 61, 1921)


“It is an investigative and inventive art. When ideas are combined in all possible ways, the new combinations start the mind thinking along novel channels and one is led to discover fresh truths and arguments.” (Martin Gardner, “Logic Machines and Diagrams”, 1958) 

"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 manifold. 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." (Herbert J Ryser, "Combinatorial Mathematics", 1963)


"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." (Marshall Hall, "Combinatorial Theory", 1969)


"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." (Gian-Carlo Rota, "Discrete Thoughts", 1969)


"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." (Paul Erdős, "On the application of combinatorial analysis", Proceedings of the International Congress of Mathematicians Nice, 1970)


"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." (Gian-Carlo Rota, "Combinatorial theory, old and new", Proceedings of the International Congress of Mathematicians Nice, 1970)


"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." (Louis Comtet, "Advanced Combinatorics", 1974)


"Broadly speaking combinatorial analysis is now taught in two parts which I will label: The first classical, the second important. Classical combinatorics is concerned with counting problems. [...] As a mathematician, I like classical combinatorics. It is full of interesting devices: permutations, combinations, generating functions, amusing identities, etc. Relevant, it is not, except as a possible supplement to a basic course in probability. [...] Classical combinatorics is sometimes useful in preventing people from using an exhaustive procedure on the computer such as listing all combinations or examining all the cases. [...] The part of combinatorial analysis which I have labeled ‘important’ is concerned with selecting the best combination out of all the combinations. This is what linear programming is all about." (George B Dantzig, "On the relation of operations research to mathematics", [panel talk before AMS], 1971)


"Every hard problem in mathematics has something to do with combinatorics." (Lennart Carleson, cca. 1974)


“Combinatorial analysis, or combinatorics, is the study of how things can be arranged. In slightly less general terms, combinatorial analysis embodies the study of the ways in which elements can be grouped into sets subject to various specified rules, and the properties of those groupings. […] Combinatorial analysis often asks for the total number of different ways that certain things can be combined according to certain rules.” (Martin Gardner, "Aha! Insight", 1978)
“Every branch of mathematics has its combinatorial aspects […] There is combinatorial arithmetic, combinatorial topology, combinatorial logic, combinatorial set theory-even combinatorial linguistics, as we shall see in the section on word play. Combinatorics is particularly important in probability theory where it is essential to enumerate all possible combinations of things before a probability formula can be found.”  (Martin Gardner, "Aha! Insight", 1978)

"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:
- Enumeration, including generating functions, inversion, and calculus of finite differences;
- Order Theory, including finite sets and lattices, matroids, and existence results such as Hall's and Ramsey's;
- Configurations, including designs, permutation groups, and coding theory." (Martin Aigner, "Combinatorial Theory", 1979)


"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." (László Lovász, "Combinatorial Problems and Exercises", 1979)


"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." (Gian-Carlo Rota, [Preface to Combinatorial Enumeration by I.P. Goulden and D.M. Jackson], 1983)


"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." (George Pólya, Robert E Tarjan & Donald R Woods, "Notes on Introductory Combinatorics", 1983)


"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 are now trying to understand how this extraordinary coincidence comes about. If we do, we will have found a notable unification in mathematics." (Gian-Carlo Rota, "Mathematics, Philosophy and Artificial Intelligence", Los Alamos Science No. 12, 1985)


"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." (Noga Alon, "Non-Constructive Proofs in Combinatorics", Proceedings of the International Congress of Mathematicians Kyoto, 1990)


"Combinatorics belongs to those areas of mathematics having experienced a most impressive growth in recent years. This growth has been fueled 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." (Ronald Graham, Martin Grötschel & László Lovász, "Handbook of Combinatorics" Vol. 1, 1995)


"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." (Joel Spencer, "Probabilistic methods", Handbook of Combinatorics Vol. 2, 1995)


"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." (Peter J Cameron, "Combinatorics: topics, techniques, algorithms", 1995)


"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. [...] 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." (Gian-Carlo Rota, "Combinatorics, Representation Theory and Invariant Theory, in Indiscrete Thoughts", 1997)


"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." (Daniel J Kleitman, "On the future of combinatorics", 2000)


"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." (Timothy Gowers, "The two cultures of mathematics", 2000)


"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." (Cristian Lenart, "The Many Faces of Modern Combinatorics", 2003)


"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." (Timothy Gowers, June Barrow-Green & Imre Leader, "The Princeton Companion to Mathematics", 2008)


"Combinatorics seems to be the most fruitful source of easy-to-understand but hard-to-prove theorems, and it is also seems to be the place where insights from the infinite world most clearly illuminate the finite world." (John Stillwell, "Mathematics and Its History", 2010)

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...

On Data: Longitudinal Data

  "Longitudinal data sets are comprised of repeated observations of an outcome and a set of covariates for each of many subjects. One o...