Difference between revisions of "Combination"

Line 20: Line 20:
  
 
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>.
 +
 +
==Other Formulas==
 +
<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>
  
  

Revision as of 23:46, 1 November 2007

This is an AoPSWiki Word of the Week for Nov 1-7

A combination is a way of choosing $r$ objects from a set of $n$ where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size $r$ from an original set of size $n$


Notation

The common forms of denoting the number of combinations of ${r}$ objects from a set of ${n}$ objects is:

  • $\binom{n}{r}$
  • ${C}(n,r)$
  • $\,_{n} C_{r}$
  • $C_n^{r}$

Formula

${{n}\choose {r}} = \frac {n!} {r!(n-r)!}$

Derivation

Consider the set of letters A, B, and C. There are $3!$ 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 ${r}$ objects from ${n}$ elements $P(n,r)$, there are ${r}!$ more ways to permute them than to choose them. We have ${r}!{C}({n},{r})=P(n,r)$, or ${{n}\choose {r}} = \frac {n!} {r!(n-r)!}$.

Other Formulas

$\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}$

$\sum_{x=0}^{n} \binom{n}{x} = 2^n$


Examples

Links

See also