combination (idea)

A combination is a subset of a certain size of some set of objects, without regard to order. For instance, there are 10 combinations of two letters from the set {A, B, C, D, E}, namely AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE.

Compare this with the permutations of the same size from the same set. Note that each combination appears twice in the list of permutations. This is because there are 2 ways to arrange two numbers. The number of combinations equals the number of permutations of the type desired divided by the number of permutations of a set that size, using all the elements.

The number of combinations of r objects from a set of n objects is often written as C(n,r) or _nC_r or with two numbers between tall parentheses sorta like this:

  /   \
 |  n  |
 |     |
 |  r  |
  \   /

All of these various forms of notation are often pronounced "n choose r".

C(n,r) can be calculated as n!/{r!(n-r)!} where ! represents the factorial function. Note that C(n,r) = C(n,n-r); there is a one-to-one correspondence between subsets of size r and subsets of size n-r -- just consider what's left over after you take away a subset of size r.