Difference between revisions of "Combination"

(corrected notation)
m (changed first example problem to internal link)
Line 22: Line 22:
 
== Examples ==
 
== Examples ==
  
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2005&p=368223 AIME 2005II/1]
+
* [[2005_AIME_II_Problems/Problem_1 | 2005 AIME II Problem 1]]
 
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385889 AIME 2000II/5]
 
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385889 AIME 2000II/5]
 +
  
 
== See also ==
 
== See also ==

Revision as of 18:58, 21 July 2006

Introduction

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:

  • ${n}\choose {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)!}$.


Examples


See also