Difference between revisions of "Combination"
(→Derivation: Clarification) |
(→Derivation) |
||
Line 17: | Line 17: | ||
== Derivation == | == Derivation == | ||
− | Consider the set of letters A, B, and C. There are <math>3!</math> different [[permutations]] of those letters. Since order doesn't matter with combinations, there is only one combination of those three. In general, since for every permutation of <math>{r}</math> objects from <math>{n}</math> elements <math>P(n,r)</math> | + | Consider the set of letters A, B, and C. There are <math>3!</math> different [[permutations]] of those letters. Since order doesn't matter with combinations, there is only one combination of those three.(<math>ABC,ACB,BAC,BCA,CAB,CBA</math> are all equivalent in combination but different in permutation.) |
+ | |||
+ | In general, since for every permutation of <math>{r}</math> objects from <math>{n}</math> elements <math>P(n,r)</math> which is <math>\frac{n!}{n-r!}</math>.Now since in permutation the order of arrangement matters(ABC is not same as ACB) but in combinations the order of arrangement does not matter(ABC is equivalent to ACB).Suppose <math>r</math> elements are selected out.For permutation <math>r</math> elements can be arranged in <math>r!</math> ways.We have overcounted the number of combinations by <math>r!</math> times.So We have <math>{r}!{C}({n},{r})=P(n,r)</math>, or <math>{{n}\choose {r}} = \frac {n!} {r!(n-r)!}</math>. | ||
==Formulas/Identities== | ==Formulas/Identities== |
Revision as of 11:57, 18 May 2012
A combination is a way of choosing objects from a set of
where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size
from an original set of size
Notation
The common forms of denoting the number of combinations of objects from a set of
objects is:
Formula
Derivation
Consider the set of letters A, B, and C. There are different permutations of those letters. Since order doesn't matter with combinations, there is only one combination of those three.(
are all equivalent in combination but different in permutation.)
In general, since for every permutation ofobjects from
elements
which is
.Now since in permutation the order of arrangement matters(ABC is not same as ACB) but in combinations the order of arrangement does not matter(ABC is equivalent to ACB).Suppose
elements are selected out.For permutation
elements can be arranged in
ways.We have overcounted the number of combinations by
times.So We have
, or
.
Formulas/Identities
One of the many proofs is by first inserting into the binomial theorem. Because the combinations are the coefficients of
, and a and b disappear because they are 1, the sum is
.
We can prove this by putting the combinations in their algebraic form.
. As we can see,
. By the commutative property,
. Because
, by the transitive property, we can conclude that this is true for all non-negative integers n and r where n is greater than or equal to r. Another reason this is true is because that choosing what you don't want is the same as choosing what you do want, because by choosing what you don't want, you imply that you choose the rest. This identity is also the reason why Pascal's Triangle is symmetrical.