Talk:Combinatorics

How do you get 63?

If you start out with six tastes (e.g., six different spices which you can use singly or in combination with each other), if you mix two together you get 30 combinations (i.e., six choices for the first one times five choices for the second equals 30 different mixtures). If, as the text suggests, you mix three together, you get 120 different mixtures. So how did the ancient one arrive at 63, and why has no one questioned this before? 71.251.136.49 (talk) 22:24, 11 December 2010 (UTC)

Yes, 6 choices for the first ingredient A times 5 choices for the second ingredient B times 4 choices for the third ingredient C gives 120 ways to mix just the first 3 ingredients. However, several of those 120 mixes taste exactly the same, and apparently the ancient one only counted combinations that taste different. Those mixes include ABC or BCA or CAB or CBA or BAC or ACB, which all taste exactly the same. With exactly 3 spices, selected without repetition from a spice-rack of 6 unique and discriminable spices, there are only 20 different-tasting mixtures.

If I think of it as either using a spice or not (ignoring exactly how much of the spice is used), the 6 bits of information -- used or not -- give 2^6 = 64 different-tasting combinations. Apparently the ancient one excluded the "null" spice of not using any of the available ingredients, leaving 63 flavors. How can we make this article easier to understand? --DavidCary (talk) 22:39, 23 February 2021 (UTC)

The lead

The opening sentence in the lead has been stable for many years, but was a bit complex for anyone not familiar with the field. A recent edit attempted to fix this problem by replacing it with the statement that combinatorics is the mathematical theory of counting and citing it to an introductory probability text. I applaud the attempt, but it really goes a bit too far and leaves out major aspects of the subject, thus giving a false impression of the topic. This is understandable given the nature of the source, which I would not call authoritative, since the only aspect of combinatorics that is relevant to introductory probability is counting. To fix this I added the phrase "at its core" to indicate that while not incorrect, the statement was not complete, thus keeping the simplified form without giving the false impression. The next sentence would then have to say something about the broader definition, so I brought back the original sentence, slightly simplified. Another reason to bring back the sentence is that it contained the appropriate links to help make sense of the remainder of the paragraph and the rest of the article. A new problem now arises in that the simplified and broader definitions do not seem to be related (again, for a reader with no knowledge of the topic), so I added the phrase "in which counting is a primary tool" to make this connection clear. While my changes could perhaps be improved upon, a revert clearly needs to be explained and discussed. --Bill Cherowitzo (talk) 19:04, 26 October 2017 (UTC)

I agree. It is rather difficult to define combinatorics, as this page [1] suggests. If one chooses a random probability textbook over authoritative quotes given there, please argue here. Otherwise, let the page remain as in the stable version before. Mhym (talk) 23:09, 26 October 2017 (UTC)

Perhaps I didn't make myself quite clear. I agree with the editor who felt that the stable version was too opaque. If I thought that returning to it was the best way to handle the situation, I would have reverted to it myself. I think that my revised version is better than either the stable version or the attempt by that editor. Of course there is no universally agreed upon definition, but an encyclopedia needs to give something that a reader can understand and that isn't too far off the mark. Throwing one's hands up in the air is not a good option. We might want to indicate the lack of agreement of a definition, but only after giving some skeletal outline of the topic. What I have suggested comes fairly close to the Princeton Companion treatment if it needs a pedigree. --Bill Cherowitzo (talk) 03:51, 27 October 2017 (UTC)

I am fine with changing the lead, but do want to agree on a version here before the change is implemented. I strongly disapprove the ambiguities like "at its core" which was in the recent version. But I do think "geometric" was a good addition. I am also fine with the old stable version. Perhaps, you can propose a new version, post for comparison the Princeton Companion quote and we can start improving on that. Hopefully we can reach a consensus. Perhaps, other editors will join the discussion so it's not only the two of us. Mhym (talk) 05:48, 27 October 2017 (UTC)

Ok. I will do that, although, I'm afraid, given the nature of the beast, you are going to have to accept some ambiguity in the lead. If this could be done without ambiguity there would be a clear-cut definition of the field, which we know does not exist. --Bill Cherowitzo (talk) 17:20, 27 October 2017 (UTC)

Right. Perhaps, it's better to start from scratch and make a somewhat vague but acceptable compilation version of some definitions on that page above, than try to make incremental improvements. Mhym (talk) 20:02, 27 October 2017 (UTC)

Here is a first pass. This is meant to replace the first paragraph. The Mazur quote is from Combinatorics : A Guided Tour and the Ryser reference is to Combinatorial Mathematics.

Version 1
The following discussion has been closed. Please do not modify it.
Combinatorics, it has been said, "may rightly be called the mathematics of counting." Few, however, would take this as a definition without a great deal of further amplification. Agreement on how this amplification should proceed is lacking and, according to Ryser (1963, p. 2), a definition of this subject is difficult because it crosses so many mathematical subdivisions. In so far as an area can be described by the types of problems it addresses, combinatorics is involved with the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations, associated with finite sets, the existence of such structures that satisfy certain given criteria, the construction of these structures, perhaps in many ways, drawing upon ideas from several areas of mathematics, and optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion. Perhaps the easiest way to give an accounting of what combinatorics is, is to describe its subdivisions with their problems and techniques as is done below. However, even this approach is not completely satisfactory since it does not capture the purely historical reasons for including or not including some topics under the combinatorics umbrella. Although primarily concerned with finite sets, some combinatorial questions and techniques can be extended to an infinite (specifically, countable) but discrete setting. This concentration on finite sets implies that techniques used in combinatorial arguments are more likely to be drawn from algebra than analysis.

Let me try to edit this. I kept much, but revised the first few sentences. It is more dry and less eloquent perhaps but more direct and to the point, making it more useful perhaps. I totally disagree with the last proposed lead sentence - much of Asymptotic and Arithmetic Combinatorics uses tools from Analysis, Probabilistic Combinatorics uses tools from Probability, etc. There seem to be no sensible way to make this distinction correct and meaningful.

NOTE: I am trying to follow WP:LEAD, which is useful reading for those editors unfamiliar with this. Mhym (talk) 23:19, 29 October 2017 (UTC)

Version 2
The following discussion has been closed. Please do not modify it.
Combinatorics is an area of Mathematics primarily concerned with counting and structural properties of finite sets. It is closely related to many other areas of mathematics, incorporating many tools and ideas, and with many applications ranging from Logic to Statistical Physics, from Evolutionary Biology to Sociology, etc. To fully understand the scope of Combinatorics requires a great deal of further amplification. According to H. J. Ryser, see Ryser (1963, p. 2), a definition of the subject is difficult because it crosses so many mathematical subdivisions. In so far as an area can be described by the types of problems it addresses, combinatorics is involved with the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations, associated with finite sets, the existence of such structures that satisfy certain given criteria, the construction of these structures, perhaps in many ways, drawing upon ideas from several areas of mathematics, and optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion. Leon Mirsky have said: "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." [2] Thus, perhaps the easiest way to define combinatorics is to describe its subdivisions with their problems and techniques. This is the approach we use below. Note, however, even this approach is not completely satisfactory since it does not capture the purely historical reasons for including or not including some topics under the combinatorics umbrella. Note also that although primarily concerned with finite sets, some combinatorial questions and techniques can be extended to an infinite (specifically, countable) but discrete setting. _______________________________________________________________

This looks good to me. A few copyediting changes and a modification of the first sentence of the second paragraph are all that I think are needed. We can reference Pak's quotations for the addition. I think that this added phrase (or its equivalent) is needed to bring clarity to why we are addressing the definition question in the way that we are. I don't think that there was anything wrong with the algebra statement, as I phrased it, considering that up until very recently combinatorics was dealt with by the NSF in its algebra section. However, this is not a deal breaker and I'll be happy to let it slide. --Bill Cherowitzo (talk) 05:07, 30 October 2017 (UTC)

Version 3
The following discussion has been closed. Please do not modify it.
Combinatorics is an area of mathematics primarily concerned with counting and structural properties of finite sets. It is closely related to many other areas of mathematics, incorporating many tools and ideas, and with many applications ranging from logic to statistical physics, from evolutionary biology to sociology, etc. To fully understand the scope of combinatorics requires a great deal of further amplification, the details of which are not universally agreed upon. According to H. J. Ryser, see Ryser (1963, p. 2), a definition of the subject is difficult because it crosses so many mathematical subdivisions. In so far as an area can be described by the types of problems it addresses, combinatorics is involved with the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations, associated with finite sets, the existence of such structures that satisfy certain given criteria, the construction of these structures, perhaps in many ways, drawing upon ideas from several areas of mathematics, and optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion. Leon Mirsky has said: "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." [3] Thus, perhaps the easiest way to define combinatorics is to describe its subdivisions with their problems and techniques. This is the approach that is used below. However, even this approach is not completely satisfactory since it does not capture the purely historical reasons for including or not including some topics under the combinatorics umbrella. Although primarily concerned with finite sets, some combinatorial questions and techniques can be extended to an infinite (specifically, countable) but discrete setting. _____________________________________________________________

As we seem to be converging on this change, let's try to get some other comments before finalizing.

Soliciting comments for change of lead (Joel B. Lewis—Will Orrick—David Eppstein) --Bill Cherowitzo (talk) 19:10, 30 October 2017 (UTC)

I think "finite sets" is too specific. There is certainly important work on the combinatorics of finite sets (e.g. Sperner's theorem) but most people would include graph theory (or at least the theory of finite graphs) in combinatorics, and although graphs can be represented as sets they are not the same thing as sets. I would prefer "finite structures", but then we should change "structural" earlier in the sentence to some other word. (Also, from the graph-theoretic perspective, I'm not entirely happy about the emphasis on counting — the enumerative combinatorics of graphs, while important, is a small part of graph theory overall.) —David Eppstein (talk) 19:21, 30 October 2017 (UTC)

Thanks David. I certainly include graph theory in combinatorics and your point is well taken. I think this is easily fixed. As to your issue with counting ... this could just be a matter of perspective. When I think of counting in this context, I have in mind more than just enumeration. I am thinking of it as a fundamental proof technique, and as such, it is pervasive in all of combinatorics, including graph theory. Just think of the handshaking lemma, Ramsey theory, and any proof that sets up a bijection between finite sets. Perhaps this vision needs to be made stated more clearly. --Bill Cherowitzo (talk) 20:51, 30 October 2017 (UTC)

Some comments:

• I agree with David about "finite structures."
• I think the grammar in the second sentence is broken; "and with" should be "and having", right?
• Can you say a bit about what is intended by the phrase "incorporating many tools and ideas"?
• I am a bit unhappy with the mention of sociology in the lead, since it is not mentioned in the article body anywhere.
• I suggest moving the Ryser citation into ref tags rather than leaving it in-line.
• I feel like the end gets a bit essay-ish.

All that said, I think it does a very good job saying what combinatorics is about. --JBL (talk) 00:06, 31 October 2017 (UTC)

Thanks Joel. I agree with your points and will take care of them. I didn't realize the bit about the ending until you mentioned it and I'm not quite sure how to handle that, but I'll sleep on it. Suggestions welcome. --Bill Cherowitzo (talk) 02:48, 31 October 2017 (UTC)

This wasn't meant to be a final version, just some minor improvement in the hope there will be more. I am ok changing sociology to something else, reformatting the citation, finite structures, rewording(s), etc. I would also probably like to see if there is a way to use some parts of the existing lead here - I think there are some good lines there as well. Perhaps, David and Joel can help here with more than minor changes. So, what's the new version now? Mhym (talk) 05:20, 31 October 2017 (UTC)

Here is my latest attempt to incorporate corrections suggested and include the rest of the lead (with some minor changes to avoid overlap). We can certainly continue to tweak this, but I'm not seeing any need for major changes. --Bill Cherowitzo (talk) 19:01, 1 November 2017 (UTC)

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.

To fully understand the scope of combinatorics requires a great deal of further amplification, the details of which are not universally agreed upon. According to H. J. Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions. In so far as an area can be described by the types of problems it addresses, combinatorics is involved with

• the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
• the existence of such structures that satisfy certain given criteria,
• the construction of these structures, perhaps in many ways, drawing upon ideas from several areas of mathematics, and
• optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.

Leon Mirsky has said: "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." One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques. This is the approach that is used below. However, there are also purely historical reasons for including or not including some topics under the combinatorics umbrella. Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically, countable) but discrete setting.

Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory, which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.

A mathematician who studies combinatorics is called a combinatorialist.

References

_____________________________________________________________

1) I am thinking "combinatorist" is old fashioned and should be deleted. I tried WP:GOOGLE and found 50K for "combinatorialist" vs 2.2K for "combinatorist", many of which I am sure to this WP page and its mirrors. I say we scrap this version.

2) I find "This approach is not completely satisfactory" to be overly negative. I would put a positive spin on it, as in "To fully understand the definition one needs to see historical reasons for including or not including some topics under the combinatorics umbrella. According to Gian-Carlo Rota, "combinatorial theory has been the mother of several of the more active branches of today's mathematics, which have become independent", singling out algebraic topology as the most successful example." [4] I tried to find a better link but failed. I think it's a chapter of "Discrete thought" by Rota.

P.S. Now that I read algebraic topology, that article includes a section "Notable algebraic topologists". Maybe we also should have a section like that. Category:Combinatorialists has many, of course, but some of those are best known for work in other fields. Mhym (talk) 20:50, 1 November 2017 (UTC)

I've gone ahead and incorporated some of this in the draft. 1) Although I see a need for it, I wouldn't mind ditching the whole sentence. Certainly, when I see "combinatorist" I grit my teeth, so I am happy to see that go. 2) Reworded slightly to remove the pronoun. I like the Rota quote but it seems to me to be opening up a new topic that isn't addressed in the article, so I've left it out for the nonce. A list of combinatorialists seems like a good idea, perhaps with a disclaimer that some in the list may be more well known for their contributions in other fields. --Bill Cherowitzo (talk) 21:35, 1 November 2017 (UTC)

Some more suggestions.

1) Let's then ditch the "fully appreciate" sentence. It make the text flow better.

2) It would be a good idea to preface "Combinatorics problems..." sentence with a sentence to the effect that combinatorics is well known for its problems. Otherwise this feels like a logical jump between paragraphs.

3) I would like to have some quotes or at least citations right after "independent branch of mathematics in its own right." sentence. I looked at the list of Pak's quotes referenced above. I liked Lovasz's quote "In my opinion, combinatorics is now growing out of this early stage..." and Stanley's quote "On the other hand, the "depth" of the subject is rapidly increasing..." Not sure if you want to do anything. Mhym (talk) 00:09, 2 November 2017 (UTC)

1) I would really like to hold on to the sentence as it indicates that there is some hapstance as to what is considered in the purview of combinatorics. I've trimmed the sentence, but if it is still problematic I'd rather try to fix it than ditch it. 2) Done ... could be improved. 3) I am getting a little concerned that we are moving away from summarizing the article and towards writing an essay on combinatorics. The way to tackle this is write more in the body of the article first and then amend the lead to reflect that. --Bill Cherowitzo (talk) 16:27, 2 November 2017 (UTC)

I am happy with 1) and 2) changes. As for 3), I agree with you actually. I don't think the lead should be overly long. But this is a discussion, and since others are not bringing this up I thought it is worth mentioning as a possibility. In fact, I am largely happy with the current version. I would probably add a citation link to Rota and Lovasz in places I mentioned, and be done with it. If someone want to expand on this, the right place is the "History" section.

Anyone else has comments, corrections, suggestions, before we implement the lede change? Mhym (talk) 20:57, 2 November 2017 (UTC)

Ok. I've put the links in (with the quotes). I'm ready to go live with this. --Bill Cherowitzo (talk) 18:35, 3 November 2017 (UTC)

I think it's certainly good enough to go live. I have three further comments:

* I think the first sentence is kind of a mouthful, but don't have a constructive suggestion.

* The first bullet point is extremely hard to parse -- I think it makes perfect sense with the final clause removed, but maybe other simplifications are possible.

* I suggest removing "drawing upon ideas from several areas of mathematics" from the third bullet point: it's not wrong, but it seems off-point to me, and the connections between combinatorics and other fields are discussed elsewhere in the lead.

JBL (talk) 01:15, 4 November 2017 (UTC)

Thanks Joel. As usual, good points that I agree with. However, we may have hit the "point of diminishing returns" with this. We could spend weeks polishing the prose and getting this just right only to have some editors come by ten minutes after we post this and make valid major changes. I think we should just post it as is and then let the wiki do its magic to improve it. My goal was to make this introduction more reader friendly than the current one and I think this version succeeds at that, even if it could still use some tweaking. Working with Mhym has been very constructive and informative, but it is time to put this baby out there before we get accused of trying to own this article. --Bill Cherowitzo (talk) 17:41, 4 November 2017 (UTC)

Wcherowi yes, absolutely (and that's why I started my comment the way I did) -- I would be happy to make further edits on the live version. --JBL (talk) 18:09, 4 November 2017 (UTC)

I also agree. May edit the article later especially to tweak the first sentence. Thank you, Wcherowi for being so helpful. Mhym (talk) 02:58, 5 November 2017 (UTC)

_____________________________________________________________

• I am ok with the revised sentence. I just don't like anon edits on items that were discussed here. Mhym (talk) 23:16, 25 August 2020 (UTC)

Reopening the discussion, I disagree with the emphasis on counting and restriction to finiteness in the opening sentence of the current lede. A lot of combinatorics is about structure without counting, or structure with some counting as an auxiliary aspect. Also, most combinatorics is finite, but an unmodified restriction is "misledeing" (sic). I suggest a rewrite that puts counting and structure on the same level of importance. I also hope for an improvement in "certain ... structures", where "certain" is too vague. On the other hand, it's very hard to be more specific. Ideas? Zaslav (talk) 17:34, 29 February 2024 (UTC)

Riordan transformations

I am researching the actual usage/meaning of Riordan transforms and noticed they seem to be missing from Wikipedia. Would anybody be interested in an entry, and where should it be placed. I can give various published references to it and one project paper by Renzo Sprugnoli (which seems to have disappeared from the internet, but I have a copy). "In the raw" they are a little difficult/confusing to understand. They are related to Riordan Arrays Combinatorial identities "Formal"/"Method of coefficients" mathematical methods https://local.disia.unifi.it/merlini/papers/MofC.pdf etc... In my case I am using them to generate generating functions for Hadamard products of power series, and attempts to form closed partial sums of various functions. But since it's for private usage it won't be published. Rrogers314 (talk) 21:37, 24 March 2021 (UTC)

@Rrogers314: At a quick glance, the obvious places such material might fit are Riordan array, Generating function transformation, and Riordan transform (yes, it does not exist yet, but it could, provided sufficient sources exist). Which is best depends exactly what you are planning to write. --JBL (talk) 22:52, 24 March 2021 (UTC)