Difference between revisions of "Combination"
m (→Other Formulas) |
|||
| Line 21: | Line 21: | ||
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>, there are <math>{r}!</math> more ways to permute them than to choose them. We have <math>{r}!{C}({n},{r})=P(n,r)</math>, or <math>{{n}\choose {r}} = \frac {n!} {r!(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. In general, since for every permutation of <math>{r}</math> objects from <math>{n}</math> elements <math>P(n,r)</math>, there are <math>{r}!</math> more ways to permute them than to choose them. We have <math>{r}!{C}({n},{r})=P(n,r)</math>, or <math>{{n}\choose {r}} = \frac {n!} {r!(n-r)!}</math>. | ||
| − | == | + | ==Formulas/Identities== |
| − | <math>\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}</math> | + | * <math>\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}</math> |
| − | <math>\sum_{x=0}^{n} \binom{n}{x} = 2^n</math> | + | * <math>\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}</math> |
| + | |||
| + | * <math>\sum_{x=0}^{n} \binom{n}{x} = 2^n</math> | ||
One of the many proofs is by first inserting <math>a = b = 1</math> in to the [[binomial theorem]]. Because the combinations are the coefficients of <math>2^n</math>, and a and b cancel out because they are 1, the sum is <math>2^n</math>. | One of the many proofs is by first inserting <math>a = b = 1</math> in to the [[binomial theorem]]. Because the combinations are the coefficients of <math>2^n</math>, and a and b cancel out because they are 1, the sum is <math>2^n</math>. | ||
| + | |||
| + | * <math>\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}</math> | ||
== Examples == | == Examples == | ||
| Line 40: | Line 44: | ||
* [[Permutations]] | * [[Permutations]] | ||
* [[Pascal's Triangle]] | * [[Pascal's Triangle]] | ||
| + | * [[Generating_function]] | ||
Revision as of 20:58, 3 November 2007
| This is an AoPSWiki Word of the Week for Nov 1-7 |
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. In general, since for every permutation of objects from elements 
, there are 
more ways to permute them than to choose them. We have 
, or .
Formulas/Identities
One of the many proofs is by first inserting 
in to the binomial theorem. Because the combinations are the coefficients of 
, and a and b cancel out because they are 1, the sum is .
