Talk:Combination

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-priority)
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
High Priority
 Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.

Efficient calculation[edit]

 {n \choose k} = \frac{n!}{k! \cdot (n-k)!}.

The most obvious method of obtaining the numerical value given above is not the most efficient method. This is most inefficient if the value of n is very large.

A more efficient algorithmn for the numerical value is

 {n \choose k} = \frac { ( n - 0 ) }{ (r - 0) } \times \frac { ( n - 1 ) }{ (r - 1) } \times \frac { ( n - 2 ) }{ (r - 2) } \times \frac { ( n - 3 ) }{ (r - 3) } \times \cdots \times \frac { ( n - (r - 1) ) }{ (r - (r - 1)) }

Example:

 {70 \choose 4} = \frac { 70 }{ 4 } \times \frac { 69 }{ 3 } \times \frac { 68 }{ 2 } \times \frac { 67 }{ 1 } = 916895
That is true. But one should add that after putting it in the form
 {70 \choose 4} = \frac { 70 }{ 4 } \times \frac { 69 }{ 3 } \times \frac { 68 }{ 2 } \times \frac { 67 }{ 1 }
one should CANCEL BEFORE MULTIPLYING. Michael Hardy 23:53, 30 August 2005 (UTC)

No Michael, just compute backwards like this: ((((((67/1)×68)/2)×69)/3)×70)/4 . Bo Jacoby 11:58, 23 March 2006 (UTC)


Consistency in style[edit]

Wouldn't it be more consistent to have the term representing combinations in the same style as the term representing permutations? Combinations is (n k) and Permutations is P(n, k). I suggest C(n, k) would be better. David Ball 01:58, 28 December 2005 (UTC)

I most often see permutations written in the form nPr, although this is mostly aesthetics and simply a matter of preference. I would also suggest to use n,r rather than n,k to match the Permutaions article. 141.156.41.21 00:18, 10 November 2006 (UTC)

REDIRECT to Binomial coefficient[edit]

this page looks like it is about the exact same topic, and I think the pages should be merged. Any takers? Fresheneesz 23:11, 4 February 2006 (UTC)
I couldn't agree more. I had a concept review problem on my summer math worksheet regarding both permutations and combinations, so I looked here on Wikipedia for reference. I found permutations easily enough, but it was hard to find combinations. (probably because the word has so many other meanings)The two should both be on the same page. --Iellwen, August 2006
No. It's obviously NOT the same topic as binomial coefficient, since it includes enumeration of ordered things including permutations and permutations-with-repetition, etc. This proposal is silly. Michael Hardy 20:39, 30 August 2006 (UTC)
No. Agree with Mike on this one. Definately NOT the same topic. fintler 23:32, 14 December 2006 (UTC)

Fintler, for a proof that the binomial coefficient count the number of k-combinations of an n-set, see Multiset#Polynomial_notation. Bo Jacoby 01:22, 15 December 2006 (UTC)

I agree partially with the original poster: either the definitions of the binomial coefficient and combination need to be stated clearly to show that they are different concepts, or they need to be considered the same concept. Currently, both pages give n!/k!/(n-k)! as their definition, and this is entirely incorrect. The definition of a binomial coefficient is given in the first sentence on the page, it is the coefficient of the x^k term in (1+x)^n. The definition of a combination is the count of sets without replacement or regard to order from n elements to a sets of size k. The fact that both of these equal n!/k!/(n-k)! is a theorem, not a definition. Antares5245 (talk) 07:30, 26 July 2009 (UTC)


Merge[edit]

(Meta-talk)[edit]

   This "Merge" talk section (about merging the substance of what was then the article "Permutations and combinations") incorporated article text, including what was presumably a heading "Combination with repetition" from that article. (For the record, probably the level (depth) of the heading was changed to better fit the environment of this talk page.)
   For the record, that other page got renamed from "Permutations and combinations" to "Twelvefold way".
   I'm acting in the hope that additional (parenthesized) headings, and an (additional) level change, will help make it more intuitive than it was as i found it.
--Jerzyt 02:05, 26 July 2014 (UTC)

(Earliest contribs to "Merge" section )[edit]

I think the Combinations section of Permutations and combinations should be merged into this article. "Permutations and combinations" hardly actually describes combinations, and mainly focuses on details of permutations. Anyone agree/disagree with this proposal? --Evil Eccentric 00:08, 23 March 2006 (UTC)

I prefer short focused articles with links to related subjects rather that long articles explaining everything. So I support your suggestion. See also the article on Multiset, where the formula for 'combination with repetition' is derived. Information from all three articles might be merged. Bo Jacoby 11:42, 23 March 2006 (UTC)
After riding the fence on this one for a while (since the two topics are often considered together), I support two separate articles: 1. Permutations and 2. Combinations, with clear links between the two, and no combined article. The location for the derivation of the 'combination with repetition' formula can reside in either article as long as there is a link from one to the other explaining its location. If it has to come down to a vote, put the derivation in the shorter article to balance their lengths out.
-- Adam Trogon 21:14, 18 May 2006 (UTC)
This is just to alert you that Permutation with repetitions entry of Permutations and combinations is inconsistent and has to be fixed. See my detailed remark at Talk:Permutations_and_combinations. In addition, this part of Permutations and combinations article is also a part of Combinatorics, with the same problems.
I tried to trace the history. It seems that the text was first added to Combinatorics by User:Haham_hanuka, and then copied to Permutations and combinations by User:Charles Matthews. Not sure this info helps...
--Alex -- talk to me 06:32, 26 May 2006 (UTC)

There is a seperate article discussing Permutation but the Combination article is 'almost' just a stub. I support the removal of the Permutations and combinations article and replacing that with two seperate articles covering these two distinct and very interesting topics. - Manish 28 August 2006
— Preceding unsigned comment added by Altrn8r (talk) 21:35, 28 August 2006

I concurr with Manish. Permutation and Combination should be kept seperate, and there's little point having an article talking about both.
WhaleWey 02:10, 6 November 2006 (UTC)

(Contrib that embedded an "imported" heading into this talk page)[edit]

(Note: except for retrofitted parenthesized section headings, everything in this sub-section is part of a single talk contribution.)

(Initial (& original) content)[edit]

I'm doing the merge now. The following section was in the article but seems to contradict this article:

(Heading, and prose content, imported from WP "Permutations and combinations" article (a.k.a. "Twelvefold way")[edit]

Combination with repetition[edit]

When the order does not matter and an object can be chosen more than once, then the number of combinations is

{{(n + r - 1)!} \over {r!(n - 1)!}} = {{n + r - 1} \choose {r}} = {{n + r - 1} \choose {n - 1}}

where n is the number of objects from which you can choose and r is the number to be chosen. This can be visualised in the following way: Imagine a string of n symbols, from which we choose r examples. e.g. pick eight symbols from the list {a, b, c, d, e}. We can rewrite this using the symbols 1 and /, meaning 'choose one' and 'next symbol' respectively. Therefore a choice of, say, {a, a, b, c, c, c, e, e} could be represented, starting at 'a', as {1,1,/,1,/,1,1,1,/,/,1,1}. ("Choose an 'a'; choose another 'a'; move on to the next symbol, 'b'; choose a 'b';" etc.) This is an equivalent to choosing n − 1 positions for the / symbol in a string of length (n − 1) + r, where n = 5 and r = 8 in this example. Thus this problem is equivalent to choosing n - 1 positions from amongst n + r − 1, without repetition, and hence falls under a previously described case.

For example, if you have ten types of donuts to choose from and you want three donuts there are

{{(10 + 3 - 1)!} \over {3!(10 - 1)!}} = {220}

ways to choose (see also multiset).

(Further (& original) comment, by includer, on the embedded section; also includer's sig)[edit]

Is this right? If so, please incorporate into the article.
Tocharianne 19:05, 31 December 2006 (UTC)

(Contribs responding to includer)[edit]

Yes it is right. It is proved twice in multiset. No need to repeat it here.
--Bo Jacoby 21:46, 31 December 2006 (UTC).
Hi, I've added an alternative explanation.
--Bizso (talk) 22:06, 15 April 2009 (UTC)

((Potential) subsequent responses to the jerk who insisted on "clarifying" the confusing structure)[edit]

But what if?[edit]

If K is "any number greater than 1 and smaller or equal to N"? What kind of combination without repetitions is it and what's the shorthand equation? How can one calculate the amount of of combinations possible if a P amount of the elements at hand can be exchanged with an F amount of alternatives yet none to L or all of P can coexist with none to L or Q or all of FUndead Herle King (talk) 19:35, 5 April 2008 (UTC)

Pascal's Triangle, Algorithms[edit]

Shouldn't this article at least make a passing reference to pascal's triangle, and mention some algorithms for calculating combinations? Antares5245 (talk) 08:50, 25 July 2009 (UTC)

here is what I get[edit]

nCk can be expressed as follows??

1...n

k

1..k-1.(n-k+1)

1..k-2.(n-k)

1..k-3.(n-k-1)

1..k-4.(n-k-2)

1....

1......(1)


=sum(n-k+1)


1..k-1.k-2.(n-k)

1....

1....(1)


=sum(n-k)



1..k-2.k-3.(n-k-1)


=sum(n-k-1)


...

=sum(n-k-2)


answer=k-1 terms from [sum(n-k+1) + sum(sum(n-k)) + sum(sum(sum(n-k-1))) ......]
— Preceding unsigned comment added by 192.18.192.21 (talk) 10:29, 29 July 2009


Repeated undoes[edit]

There have now been two successive unmotivated undoes by 76.251.40.133 (talk) of the same edit, with a few days' interval. I've reverted a second time, but would not like to go into edit warring. Given this user's (or IP's) track record, I guess it is just vandalism, and measures should be taken if it recurs again. Of course if there is any motivation for the undoes, this is the place to explain. Marc van Leeuwen (talk) 11:20, 21 February 2010 (UTC)

Rewrote the introduction[edit]

I rewrote the introduction. The previous one assumed a reading and mathematical level higher than could reasonably be expected of most people visiting this page. As this is a topic commonly taught to high school students, at the very least the introduction should be geared towards them. However I am not an expert on this subject, and only based it off of my understanding of the section on this subject in Kreyszig's text Advanced Engineering Mathematics which is a general textbook not one written by an expert on this particular subject. It should be checked for any factual errors, or information that would better give a basic understanding of what a combination is.
— Preceding unsigned comment added by Glmory (talkcontribs) 16:38, 25 September 2010

Underlined exponents[edit]

I have commented it out. Go ahead and restore my last edit if it is mathematically meaningful.

\frac{52^{\underline{5}}}{5!}

-- AAS 16:42, 27 March 2011 (UTC) — Preceding unsigned comment added by Ann arbor street (talkcontribs)

Okay, from what was explained to me, this is falling factorial power notation. I haven't heard of it before and I am not sure how approriate it is in this article, so I'll copy the text I commented out here for discussion and or somebody just reverting me.

\* CUT FROM ARTICLE

As a concrete example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:

 {52 \choose 5} = \frac{52^{\underline{5}}}{5!} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} = 
2,598,960.

END CUT FROM ARTICLE */

That's it. Ann arbor street (talk) 22:29, 27 March 2011 (UTC)

I've tried to restore the section into a coherent state that retains the new example with an explanation, and to put in an indication with wikilink where the falling factorial power notation is first used. Marc van Leeuwen (talk) 07:54, 28 March 2011 (UTC)
Just one more point: see the talk page section #Efficient calculation above for why it is useful to not be too succinct in explaining how to compute these values; people don't necessarily understand the implications of given formulas. I'll add that while cancelling every factor from the denominator is certainly most efficient for hand computation, it is not necessarily best for machine computation, as finding the proper factor in the numerator to cancel against is somewhat tedious; whence the interest of pointing out a straightforward all-integer computation. I'll add though that in practice it would possibly be hard to find many applications where it would not be faster still to tabulate a sufficiently large portion of Pascal's triangle computed from the (additive) recurrence, since binomial coefficients are rarely used in isolation. Marc van Leeuwen (talk) 08:12, 28 March 2011 (UTC)

Rfc: Use of falling factorials on combinations page, or falling factorials are so "fetch"[edit]

As in "that is so fetch" from the film mean girls.

I picked up the book Concrete Mathematics: A Foundation for Computer Science, by Graham, Knuth, and Patasinnir. This is the book I was referred to for information on rising and falling factorial notation.

The book is a graduate level math book used by would-be computer scientists. While I enjoy the book, and while it and at least one of its authors have a cult following, its authors freely admit they use unconventional notation. Quote from page "X",

SOME OF THE SYMBOLISM in this book has not (yet?) become standard. Here is a list of notations that might be unfamiliar to readers who have learned similar material from other books, together with the page numbers where these notations are explained...


...
 x^{\underline{n}} = \frac{x!}{(x-n)!} falling factorial power: [p]47, [p]211

In the above quote from page X, they forward reference pages 47 and 211 for rising and falling factorial definitions. On pages 47-48, they have the following discussions on their favored falling and rising factorial notation, which is selectively quoted to get to the point and to reduce the amount of math blocks I have to do, but not to distort the information conveyed in the book:

Such new fangled mth powers are defined by the rule...Notice the little straight line under the m; this implies that the m factors are supposed to go down and down, stepwise. There's also a corresponding definition where the factors go up and up:


...


Several other notations for factorial powers appear in the mathematical literature, notably "Pochhammer's symbol"...But the underline/overline convention is catching on, because it's easy to write, and easy to remember, and free of redundant parentheses.

Having never seen the notation before, and believing that it is not standard, and given that the notation has to be explained and defended in an computer science centered graduate level math book, this notation is not sufficiently conventional to be included in this article on combinations, in my view. In the article, we should instead stick with {52 \choose 5} = \frac{52!}{5!47!} instead of the unconventional {52 \choose 5} = \frac{52^{\underline{5}}}{5!}. I am not trying to start an edit war, but I really don't think unconventional notation should be used in this article until it is commonly used (and hence conventional) in books that introduce the topic at hand, viz., combinations. Currently, I've only seen it in a graduate level computer science/math text booksbook by witty and clever authors). Ann arbor street (talk) 15:59 & 16:01, 8 May 2011 (UTC)


  • Absolutely agree. This indeed is a non-standard notation and its use in the article just adds to making things more confusing rather than improving the quality/readability of the article. - Subh83 (talk | contribs) 19:50, 8 May 2011 (UTC)
  • Agree. Exclamation point is universally understood, underlined exponent no so much. Apparently this is a different way of writing the Pochhammer symbol, if so then use that as the notation.--RDBury (talk) 06:45, 9 May 2011 (UTC)
  • Disagree, because the question is badly posed. The opposition is not between falling factorial powers and factorials, because they are not notations for the same thing. There are two different issues at stake. One issue is between a formula for \tbinom nk as a quotient with k factors each in numerator and in numerator, and one with n factors each (grouped into factorials) and which only exists if kn. Another issue is between different notations that can be used for the first kind of formula, like
\frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1}, or \frac{n^{\underline k}}{k!} (using falling factorial power and factorial) or \frac{(n)_k}{k!} (using the Pochhammer symbol).
As for the first issue; I feel strongly that, while the article should give both formulas, it should not unduly stress the second one, because (1) it requires additional mention of the case k>n which is often forgotten, (2) it merely has redundant factors repeated in numerator and denominator with respect to the first form, (3) the most natural derivation of the formula (via double counting of k-permutations) obtains the first form directly, the second form indirectly, (4) unless point (2) is understood, the expression with factorials suggests an unwieldy computation, (5) that expression appears to nevertheless have a kind of magic attraction on people (and hence is often proposed as "definition" of binomial coefficients), which makes the risk that it will be overlooked rather small. I note that the article is currently very balanced with respect to this issue; the lead gives the first formula in a no-frills form, then immediately the second one with a warning about k>n; the following sections discuss both forms in a natural development, that would be less so if the factorials were pushed to the front.
As for the purely notational question, the article gives the expanded product first, giving the equivalent by more compact form with a falling factorial power only fairly late, and accompanied by a repetition of the expanded expression and an explicit indication of the notation. If one really feels that it is inadmissible to mention the compact notation even once, it can simply be removed (it has exactly two instances in the article, together with the explanation at its first use) and the article will still be coherent. I would strongly oppose however to replacing it by the Pochhammer symbol, which although older is not that common in mathematics that people reading this article would likely come across, and has a lot of confusing aspects to it (see the Pochhammer symbol article, and Knuth's "Two notes on notation" cited there for more on this).
You are of course entitled to never have seen the falling factorial power notation before, that happens. I will admit that 'As in "that is so fetch" from the film mean girls' explains nothing to me. One can actually find quite some notation in WP math articles that is not extremely common, and sometimes more recent than 1988. But the frankness in Concrete mathematics about the novelty of the notation and its informal tone are no argument against the notation itself. Marc van Leeuwen (talk) 08:02, 9 May 2011 (UTC)
I agree with most of what you're saying except on the use of the Pochhammer symbol. It may not be as familiar as the factorial, but it is widespread enough to be notable in the WP sense. It's even listed in A&S which is about as standard a reference as you can get. If a version using falling factorials is to be used, and you give a pretty good argument that they should, then I'd prefer using Pochhammer since it the more common, adding a short definition in the article for those who aren't familiar with it, and adding a link for those who more more details on it.--RDBury (talk) 18:01, 9 May 2011 (UTC)
Just a precision: I did not say or want to suggest that the Pochhammer symbol is insufficiently notable to have it's own article; that would not be a subject for this talk page anyway. I just said it is not a notation that those reading the article on combinations will be likely to come across (it is used a lot in hypergeometric series, although with a different meaning).
  • Agree. we should mostly just use factorial notation here. We can explain Pochhammer symbol, and mention this way of writing it with an underline. But best to stick with factorial where possible.
  • Agree. The falling factorial notation contributes nothing to the content of the article, and has potential to cause confusion (as does the phrase "that is so fetch" in this context!). Just stick with factorials and written-out products. Jowa fan (talk) 04:36, 10 May 2011 (UTC)
  • Agree: Without prejudice toward the notation, it doesn't add anything to this article. If it was more important or central it would be acceptable -- you'd have to define it, of course, but it is used often enough that WP"V and such could be satisfied. But without good reason to use it we would succeed only in making the article less well-understood. CRGreathouse (t | c) 23:48, 10 May 2011 (UTC)

Well, since there does not seem to be much support for the falling factorial power notation, I'll just take it out and the discussion can be closed. Marc van Leeuwen (talk) 07:23, 13 May 2011 (UTC)

An eminent way to count the combination of objects.[edit]

I have done an extensive research on Permutation and combination. I have also found a convenient method of numbering permutation. This convenient method of counting combination is presented in some of the word document which is attached to my sight.

https://sites.google.com/site/junctionslpresentation/home

The eminent method of counting combination is represented as C-Junction or C-Junction Number(CJN) and also mentioned as Combination order number(CON).

But the CJN and CON are different terms which is mentioned in this site in my word document.
— Preceding unsigned comment added by 14.97.31.204 (talk) 14:04, 23 May 2012 (UTC) + further unsigned edit at 14:30, 23 May 2012

The word documents are pasted at the bottom of this page.
https://sites.google.com/site/junctionslpresentation/proof-for-advance-permutation
— Preceding unsigned comment added by 14.97.31.204 (talk) 14:27, 23 May 2012 (UTC)

Found an error?[edit]

Hello, maybe this is the wrong place to post this comment, but I didn't know where else to post it. Take a look to the first equation in the paragraph "Number of combinations with repetition", just after the line "If S has n elements, the number of such k-multicombinations is also given by a binomial coefficient, namely by ". I'm not sure, but iI think that equation may be wrong.
— Preceding unsigned comment added by 82.60.1.230 (talk) 14:31 & :32, 11 October 2012

This is a well known and correct formula, but it is not intuitive. Perhaps adding a short proof would clarify the result.
Bill Cherowitzo (talk) 16:33, 11 October 2012 (UTC)
Are you sure that both members of that equation are equal? — Preceding unsigned comment added by 82.60.1.230 (talk) 19:04, 11 October 2012 (UTC)
Yes, with the exception of the case n = k = 0, mentioned in the article. C(m,r) = C(m,m-r) reflects the fact that counting r-subsets is the same as counting their complements, which are m-r subsets in a set of size m.
Bill Cherowitzo (talk) 20:12, 11 October 2012 (UTC)
   I was confused by the punctuation of 82...'s 1st contrib, which began this section -- in fact, i was afraid for a while that i'd butchered it in the process of annotating the multiple edits!
   Others might be helped by this, my refactoring of the long 2nd sent:
--Jerzyt 08:18, 25 &08:13, 26 July 2014 (UTC)

MathJax not rendering cancellations in Firefox[edit]

I consulted Help:Displaying_a_formula as well as Google searched, but I couldn't figure out how to either ensure the package is being included, and therefore determine if the issue is on my end, or to include the package manually. Are any other MathJax users having issues? Curtis (talk) 21:15, 13 March 2014 (UTC)

n-Choose-r[edit]

   The math notation that (in the frequent case where nothing about the context makes unsuitable either n or r as names for the two arguments, variables, or parameters) is read aloud as either

  • "n C r",
  • "combinations of n things taken r at a time", or
  • "n chose r".

Its symbol can be wiki-coded as either nCr or nCr. (Our article prefers n and k, to the point of not even mentioning r, by the way.)
   IMO, exhibiting only with what looks to me like the (still IMO fairly exoteric) TeX representations (tho they work too well to favor the wiki-markup versions) is likely to be intimidating to non-professionals; we should discuss the combinations notations over a range (typewriter thru Tex or even more professional) of typographic standpoints somewhere, and link there from the acc'g article (if that place is not the accompanying article).
--Jerzyt 08:05, 26 July 2014 (UTC)

Militant ignorance against vairations[edit]

It is common place to accuse people in rollback without talk, when you (initiate) rollbacks without talk. That is one reason why it is difficult to talk to people who expose such behaviour. Another is that they refute meaningful and easily verifiable information on the grounds that they are final instance of expertise and if something is not familiar to them, it is not standard, as "one gentleman classified my edit" . Why do they think that if that something they have never heard of is non-standard? At first, the notion of variations makes sense to complement permutations and combinations. Secondly, there are thousands of references in the google so that it is difficult to choose one as a reference. They are well known in Russian schools and authors of ru:Размещения had a difficult time to find English counterpart before I had created the article on variations. Wait, at first, nobody has right to label something non-standard and unsourced while there is a corresponding article in the Wikipedia. It is a vandalism to remove links to the valid Wikipedia articles under pretext that the link is unsourced. How can a reference to the source be unsourced? You cannot call an article in Wikipedia not a source. There is no excuse for User:Wcherowi behaviour. --Javalenok (talk) 09:04, 19 August 2014 (UTC)

It is nonstandard in English mathematical literature. Perhaps there is another term, but k-permutations seems adequate. — Arthur Rubin (talk) 17:05, 24 August 2014 (UTC)