Talk:Combination

Mathematics B‑class High‑priority

	Mathematics portal 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
B	This article has been rated as B-class on Wikipedia's content assessment scale.
High	This article has been rated as High-priority on the project's priority scale.

Pascal's Triangle, Algorithms

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)[reply]

But what if?

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)[reply]

REDIRECT to Binomial coefficient

Binomial coefficient

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)[reply]

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)[reply]

No. Agree with Mike on this one. Definately NOT the same topic. fintler 23:32, 14 December 2006 (UTC)[reply]

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)[reply]

Consistency in style

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)[reply]

I most often see permutations written in the form _nP_r, 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)[reply]

Efficient calculation

{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)[reply]

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

Merge

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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

Combination with repetition

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).

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

Yes it is right. It is proved twice in multiset. No need to repeat it here. Bo Jacoby 21:46, 31 December 2006 (UTC).[reply]

Hi, I've added an alternative explanation.--Bizso (talk) 22:06, 15 April 2009 (UTC)[reply]