Talk:Combinatorics

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Top-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Top Importance
 Field: Discrete mathematics
A vital article.
One of the 500 most frequently viewed mathematics articles.
This article has comments.

Initial comments[edit]

Could someone provide me with a reference to the solutions for the design theory problem presented in the text. It's very intriguing. tempfcps@juno.com Thanks. 69.251.226.145 13:40, 13 April 2007 (UTC)

With sites like this who needs classrooms? This site does a better job explaining things than most teachers do.

The maths articles are generally very good (I can say this because I've not contributed to them). Just wait til the whole 'pedia is like this! Pcb21 10:15 1 Jun 2003 (UTC)

I think that there is lots of overlap between the contents of this page and of permutations and combinations. Maybe we should just reference people there (for some sections) and just breifly outline?

--Lincsimp 09:21, 10 June 2006 (UTC)

Closed formula for Fibonacci number[edit]

should be:

f(n) = (phi)^(n+2)/sqrt(5) - (phi - 1)^(n+2)/sqrt(5)

{ this short program try to verify closed formula for } { Fibonacci number and his recurrence expression }

uses crt;

var

 fib, a, b, n : longint;
 x, fi : real;

begin

 clrscr;
 {  axioms for given Fibonacci numbers : }
 a := 1;                                     { fib(0) = 1 }
 b := 2;                                     { fib(1) = 2 }
 { the Golden mean : }
 fi := (1 + sqrt(5)) /2;
 { checking of recurrence expression and expresion in closed form : }
 for n := 2 to 15 do
 begin
    fib := a + b;       { fib( n ) = fib( n - 1) + fib( n - 2 ) }
    x := ( exp( (n+2) * ln( fi)) -
           exp( (n+2) * ln( fi - 1)) )/ sqrt(5);          { closed formula }
    writeln( 'fib( ',n : 5, ' ) = ', fib : 7, ' .... ',x:8:1);
    { shift for next number : }
    a := b;
    b := fib;
 end;

end.

I haven't run the program, but I have verified with pencil and paper that the formula in the article is right and this one is wrong. - Jwwalker

External link[edit]

An anonymous user keeps adding a bogus external link to an incoherent web page. The user should explain the reason for the link on this page first. Until then, please everyone help me control this matter.

reply 1 user 80.181.108.117

Anyone can ascertain that the link "http://www. giacomo.lorenzoni.name/solprobcombengl/" exist and work fine. To this respect I recommend you to use a computer that works well surely. For the rest, I hope that you won't continue with low accusations.

reply Mhym 15:19, 24 December 2005 (UTC)

This is an incoherent list of bogus mathematics irrelevant to the encyclopedia page. It is also written in an extremely flawed English. I will remove it once again and ask you to never again edit this page. Please stop promoting this page at the expense of the Wikipedia users.

reply 2 212.171.42.221

The animosity, the insulting language, the use of every type of accusation, and above all the absence of precise mathematical reasonings; show dark motives of your action. I hope that an authority prevents you to continue.

reply Mhym 15:26, 25 December 2005 (UTC)

OK, let's agree to make "external links" only to published articles. If you have evidence that your article is published - please present the evidence. If not - plesae do no bother encyclopedia users with this nonsense.

reply 3 80.181.108.80

Your rule "ExternalLinks only to published articles" is unfair and contrary to the ideal more essential of Wikipedia: all have the right to know and to judge what others want to make well-known. With which right you continue so stubbornly to make the censor?

reply Mhym 16:16, 26 December 2005 (UTC)

The most important rule is to have the information correct. This link is unreadble and incomprehensible. Without a publication in a reputable journal the reader cannot make his/her own judgement. I will keep removing it until I am proved wrong (on this Talk page).

reply 4 212.171.42.92

Use a computer that works well surely (see reply 1). Please not to insist in the care of things that you do not want or cannot understand.

end of reply 4 212.171.42.92


I made a little research into this and discovered that this is indeed a link to a self-published book: http://books.lulu.com/content/148685 This work is unrefereed yet for sale. The author should STOP using Wikipedia for personal advertisement purposes. Vandalism is always punished on this web site. Mhym 06:02, 28 December 2005 (UTC)

reply 5 212.171.43.11

see reply 2

end reply 5 212.171.43.11
reply 6 212.171.42.114

Requested unprotection: the page has been protected in consequence of false and trivial accusations against ExternalLink "http://www.giacomo.lorenzoni.name/solprobcombengl/".

end reply 6


I think that external links for this article should be general discussions of combinatorics or major subfields thereof. I don't think that the solution of a particular problem, even if it is correct and well-written, would be appropriate. By the way, my opinion is that Wikipedia should never allow anonymous edits of anything. - Jwwalker 20:52, 29 December 2005 (UTC)

reply 7

I think that the ExternalLinks "http://www.giacomo.lorenzoni.name/solprobcombengl/" provide a information original and pertinent to Combinatorics. I have not prejudices against the anonymity.

end reply 7

Grammar and intro[edit]

I'll say that you all have taken on a monumental task in explaining combinatorics, and I wish you much luck and skill. That said and wished, I'd like to point out a couple of things that seem to 'stick out' as in need of improvement.

[article quote] An example of a combinatorial question is the following: What is the number of possible orderings of a deck of 52 playing cards? That number equals 52! (fifty-two factorial). It may seem surprising that this number (80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000) is so big.

Anyone who has been introduced to factorials will hardly be surprised that 52! is so big. Thus, a reader might logically sense that this article will be addressed to people with little mathematical knowledge. But this article will probably lose all readers that know little of basic math. Beginners cannot be expected to know much about sequences and series, so in that respect, this article will require some seriously skilled and clever presentation to get the ideas across to the unknowledgable.

[article quote] He applied similar formulae for permutations with and without repetitions using the Arabic alphabet for illustrative purposes. He also does some work on combinatorial reasoning.

This is pretty bad English. A dead person 'does' nothing. The answer of course is that 'He also did or performed or pioneered something back then.'

There is some good material in this article but remember that the article leaves behind all beginners by the end of the introduction, so it might be best to not let the article suggest that beginners will be able to follow. I have no intention of editing the hard work of others here, but am happy enough to try to help by making suggestions. Peace.

Hi, I recommend you read Wikipedia:Talk_page_guidelines before you post again in Talk. I've taken the liberty to add a header to your section. In regards to your comments, I like the intro which mentions 52! as being a big number. It starts the article off in an interesting way, instead of plowing right into the maths. It makes the article more appealing to beginners. Nothing wrong with that. As far as the bad grammar goes, next time feel free to just make an edit. There's no point in bringing it up in Talk when its an obvious fix. --JRavn talk 21:56, 18 August 2006 (UTC)

Algebraic Geometry[edit]

Perhaps mentioning the work of Rota connecting algebraic geometry to combinatorics would enrich this entry. I don't know anything about it, in fact I ended up checking this entry to find out about this.

Stomachion section[edit]

The following text was added by User:Gryspnik a few days ago. While apparently correct (the links work, and seem to back up what's said), it was very out of place where it was put, so I've moved it here for later, better incoporation into the article. JesseW, the juggling janitor 18:59, 23 September 2006 (UTC)

Recently there was discovered that the work of Archimedes "Stomachion", believed to be lost, was the first work of Combinatorics ever written. A palimpsest discovered a few years ago, contains most of this lost work and involves finding the number of ways that the problem posed in the Stomachion can be solved. This game consists of 14 irregular strips of paper that can be placed in many different ways in order to form a square. There is additional information on this in the following links:
http://www.sciencenews.org/articles/20040515/bob9.asp
http://www.math.binghamton.edu/zaslav/Nytimes/+Science/+Math/archimedes-combinatorics.20031214.html

You are right Jesse, I moved this info in the history section of combinatronics were it actually belongs. Thanks for that note.


Formula Question[edit]

The formula for Combination with repetition seems somehow strange to me. It consists of three expressions whereas the last two seem odd. Inside the parenthesis they both have the same upper part (n+r-1) but different lower parts (r and n-1). Therefore, either r = n-1 or r = (n-(n-1) = 1) should hold, which I do not believe is always true. I already know the first expression (with r at the bottom) and think that it is correct – how about the second one? —The preceding unsigned comment was added by 141.51.122.97 (talkcontribs) .

The expressions are all equivalent. In general,
 {{p+q} \choose p} = {{p+q} \choose q} ,
because choosing p items (to keep) out of p+q items is equivalent to choosing q items (to throw away) out of p+q items. Either decision amounts to partitioning the set of p+q items into two blocks, one with p items and one with q items. For the formula for combinations with repetition, p=r and q=n-1. Michael Slone (talk) 04:40, 18 October 2006 (UTC)

Consistent Examples[edit]

I think the article might read better if we used the same example for each of four different methods, such as how many trigrams you can make from the first four letters of the alphabet. For permutations with repetition, it's 64; for permutations without repetition, it's 24; for combinations without repetition, it's 4; and for combinations with repetition, it's 20. A list of each of the sets of trigrams in questions might also be helpful, if it doesn't take up too much space. Thoughts? 64.12.116.139 05:32, 23 October 2006 (UTC)

That number at the top[edit]

Could someone write out its name, as well as the numbers? It's not that important, but it might be cool. --Santasassassin 15:15, 13 December 2006 (UTC)

rewrite of "Enumerative combinatorics" section[edit]

The biggest change I made was to put the recursive solution for the (n+2)nd Fibonacci number before the closed form solution. This is because the recursive solution is used to solve for the closed form solution. The recursive solution is not an alternative approach, it is the means to reach the end that is the close form. Also, the initial conditions given were incorrect. They were correct for the Fibonacci numbers, but since f(n) is in fact the (n+2)nd Fibonacci, the correct initial conditions are f(1) = F(3) = 2 and f(2) = F(4) = 3. Ptrillian 09:29, 3 January 2007 (UTC)

Anglo-american playing cards[edit]

I changed "deck of 52 anglo-american playing cards" to "deck of 52 distinct playing cards." For the mathematics to be correct (that the answer is 52!), the only relevant fact is that the 52 cards are distinct. Most english-speaking readers will naturally think of a standard anglo-american deck. However, if a reader is unfamiliar with this deck, I don't want that unfamiliarity to unnecessarily confuse him. Ptrillian 22:51, 5 January 2007 (UTC)

Quality[edit]

I read the article and found it inadequate, very much incomplete, poorly written at times misleading and at times plain wrong. I made few structural changes and hope others can add more material to these (very small) subsections. I realize that in the current state the article may need a complete overhaul. The idea would be to make it resemble Number theory which balances well links to deep parts with history and modern developments. Igorpak 19:35, 21 October 2007 (UTC)

Let me be more specific in my concerns. First, the article discusses at length many permutations, combinations etc. This should be done on specialized pages. Same for the Fibonacci numbers. These examples should be removed (I wasn't brave enough to do that) and replaced by their general description within one paragraph os a small subsection. Second, there is a great need to expand on the different types of combinatorics, especially graph theory and geometric combinatorics. Figures would prove useful. Third, there is a great need to elaborate on the history of combinatorics and connections with other areas. Igorpak 19:49, 21 October 2007 (UTC)

Discussion of formulae (inline)[edit]

I've moved this out of the middle of the article. --90.200.243.218 09:38, 23 October 2007 (UTC)


Is something wrong with equating the three formulae above? The first one seems okay but it doesn't seem to equal the other two despite the equals signs....plug in the numbers from the problem immediately below and see?? Perhaps I am misunderstanding the notation? Can someone who is a mathematician look at this ...feel free to delete my comment if everything is okay...FurnaldHall 03:57, 23 October 2007 (UTC)



The formulae are all correct, if you work it out using the definition it will all work out. (RM)



This probably should be moved to the discussion page. I'm leaving it here in case RM is watching the page, but anyone please feel free to clip and move it.

Using the three formulae for the donut problem below where n=10 and k=3, I get 220, 4, and 1.3333... assuming there is a division line in each formula which isn't shown in the last two. Am I misunderstanding the notation somehow. If not, how do you say the formulae are correct? Obviously I am misunderstanding if they are, but please explain how.FurnaldHall 06:05, 23 October 2007 (UTC)


Questionable quality?[edit]

I've just noticed that on 21 Oct 07 User:Igorpak, in his fairly substantial editing of the page, deleted a subsection describing the notational convention that creates symbols for sets based on enumerative expressions for their cardinality (e.g., 2X for the power set of X). I think that portion of the article was useful information, and I don't know in what other article it might be better placed. What do others think? Shall I restore the paragraph? What about you Igor, what was your thinking?—PaulTanenbaum (talk) 02:09, 13 February 2008 (UTC)

This has nothing to do with combinatorics, but rather a notation standard in set theory. It is as standard as addition or multiplication. Surely, you don't want to explain this on every WP math page... Anyhow, as I see it the page has a horrible quality, especially if you compare it with other fields of science like Biochemistry or Physical cosmology. You are welcome to improve it, but I certainly am not going to be able to do that. Igorpak (talk) 04:27, 13 February 2008 (UTC)
Actually, it does have quite a bit to do with enumerative combinatorics. "As standard as addition or multiplication"? Ah, well, I beg you indulge my ignorance in all its profundity. And no, I don't "want to explain this on every WP math page." It was explained in exacty one article that had several links to it—when you took your stab at improving the article's "horrible quality," did you police up the links that you broke?—PaulTanenbaum (talk) 01:17, 15 February 2008 (UTC)

Why do we multiply?[edit]

In both the deck-of-cards example (52!) and the example of how many ways we can produce 4 groups of people, each of which consists of 5 people, out of total of 20 people, the answer consists of multiplying together some intermediate terms. This is certainly correct, but I suggest that it may not be obvious to novices why we multiply the values instead of, say, adding them. This is sort-of addressed in the section Permutations without repetitions but regrettably the detailed example chosen involves 3! = 3 x 2 x 1 which by chance also equals 3 + 2 + 1.

Should the section Permutations without repetitions appear before Permutations with repetitions? It seems simpler.

JohnH (talk) 14:14, 6 September 2008 (UTC)

Remove new extra examples?[edit]

I think everything in [1] should be reverted. There are multiple issues with it. It's written too much like a how-to textbook instead of an encyclopedic article. The examples mix concepts instead of cleanly showing the concept in the heading like the original examples. I haven't seen the notation {n\choose r_1, r_2, r_3} before, and it's poorly explained with n apparently denoting two different things so it seems unclear whether 3 is supposed to be a fixed or variable number in the notation. The last added example apparently silently assumes that it matters whether the groups are swapped around. Otherwise the final result should be divided by the 4! ways there are to list 4 groups in order. If these examples stay then I think they need considerable work. PrimeHunter (talk) 15:36, 8 September 2008 (UTC)

I agree with your assessment of the last example. I actually noticed the same thing and was going to write a note here about it. I will add the word distinguishable for now and hope for a discussion to occur on having these examples in the first place. I believe it fits much better into the discussion of multinomial generalization of binomials. The multiplication is equivalent to {20\choose 5, 5, 5, 5} and that article says the groups are distinguishable. --cowsandmilk (talk) 19:47, 3 October 2008 (UTC)

Major edits[edit]

Some time ago I asked for this page to be restructured. Since no one did that, I figured it would be easier for me to do this. Please discuss the changes here rather than reverting the changes. I can explain why I did these major edits. Igorpak (talk) 06:09, 30 December 2008 (UTC)

Combinatorial species[edit]

I added a link to Combinatorial species, but it was reverted. What was wrong with it? —Preceding unsigned comment added by 89.53.126.151 (talk) 10:34, 18 January 2009 (UTC)

I think the issue is that calling the theory of combinatorial species a "powerful" theoretical method violates the policy of neutral point of view unless we cite a reliable source who claims that the theory is powerful. (I don't think such a source would be difficult to find.) That said, it is a bald fact that the theory of combinatorial species is a theoretical method in combinatorics, so one could avoid running afoul of NPOV issues by writing
Combinatorics is as much about problem solving as theory building, though it has developed theoretical methods, such as the theory of combinatorial species, especially since the later twentieth century.
After previewing I suspect the mention of species should probably appear later in the article. There are other powerful theoretical methods in combinatorics, and it's probably best if we don't tempt people to list them all in the introduction to the article. Michael Slone (talk) 21:04, 18 January 2009 (UTC)

counting argument[edit]

Should "counting argument" redirect to combinatorics, to lossless data compression#Limitations, or to the pigeonhole principle? --76.209.28.222 (talk) 21:24, 9 February 2009 (UTC)

History[edit]

I'd just like to know if there is any reason why the history section is pretty much entirely devoted to the Jains, with only a breif mention of earlier mathematics, and no further mathematics. (69.214.171.3 (talk) 16:30, 28 February 2009 (UTC))

External links[edit]

This article is about the whole field of combinatorics in general. External links about a specific part of combinatorics should be added to specific articles e.g. the block design link should be on the design article (which it already is), combinations and permutations links should be on the individual combinations and permutations articles. Charvest (talk) 00:43, 26 June 2009 (UTC)

jojo[edit]

rond fied —Preceding unsigned comment added by 91.181.157.21 (talk) 16:34, 30 January 2010 (UTC)

How do you get 63?[edit]

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)

Bell-ringing nonsequiteur removed[edit]

I removed the large image of the change-ringing pattern. Although tangentially related (via campanology), its not actually discussed in the article in any length, and for that image to appear as, essentially, the lede image leaves the reader wondering "Huh? What the heck does this have to do with the topic?"

If we want to add a brief subsection on campanology later in the article, I wouldn't be opposed to the image appearing there. But it is not an appropriate lede image, IMHO. Nandesuka (talk) 14:32, 17 March 2011 (UTC)

There is a quick mentioning of campanology in the history section, following Don Knuth's monograph ACP, vol 4. You can expand it a bit, if you like, maybe by one sentence, but not more to follow WP:DUE. Although the image is the first image on the page, it is placed in the history section. I see no reason to remove it. If you have a good image to be placed in the lede, please feel free to add it. Please read WP:LEDE before making big changes. Mhym (talk) 05:38, 18 March 2011 (UTC)
I'm saying that without expansion in the article, it is incomprehensible to the average reader why the image is there, or what it has to do with combinatorics; the fact that the caption is useless makes this worse. One might as well have a picture of a hot dog on the article with several different types of ingredients on it, captioned, "A hot dog (a sausage in a bun) with a number of different condiments." Nandesuka (talk) 20:50, 18 March 2011 (UTC)
I disagree. I think you should stop making nonsensical comparisons (hot dogs, etc.) This is an example of a Hamiltonian cycles in a certain Cayley graph, and was historically one of first results in what is now part of Graph Theory. As for context, etc. - you see, other images don't have significant background either. The reason is simple - this is a general topic article which simply has no space for that. That's one of the reasons why writing such an article is so difficult - to keep down the page length one has to sacrifice clarity in favor of proving a number of pointers and wikilinks on the topic. This problem is inherent in this kind of articles. For now, please stop removing the image and continue to argue on this page. Also, let other editors decide which of our arguments make more sense. Mhym (talk) 00:39, 19 March 2011 (UTC)

What about Combinatory logic and Lambda calculus?[edit]

What about Combinatory logic and Lambda calculus? Aren't they related to Combinatorics? — Preceding unsigned comment added by 93.78.75.32 (talk) 00:27, 30 June 2014 (UTC)

No! Bill Cherowitzo (talk) 03:15, 30 June 2014 (UTC)

Algebraic combinatorics[edit]

A portion of this section was removed (no reason given) and then replaced but with a clarification flag. I have rephrased the sentence so that "within the last decade or so..." no longer appears and so the clarification of that phrase is no longer needed. I have also removed the sentence about the fastest growing subarea. After examining the last few issues of the Journal of Algebraic Combinatorics I see no evidence that this statement was anything more than hype by an affectionado of this subfield. The article Algebraic combinatorics has similar statements and will also need to be fixed. The statement that I removed may even have been true at some point (though I doubt it) but such time dependent clauses should not appear in an encyclopedia. Bill Cherowitzo (talk) 17:42, 22 July 2014 (UTC)