Encyclopedia > Combination

  Article Content

Combination

Combinations are studied in combinatorics: let S be a set; the combinations of this set are its subsets. A k-combination is a subset of S with k elements. The order of listing the elements is not important in combinations: two lists with the same elements in different orders are considered to be the same combination. The number of k-combinations of set with n elements is the binomial coefficient "n choose k", written as nCk, nCk or as
<math>{n \choose k},</math>
or occasionally as C(n, k).

One method of deriving a formula for nCk proceeds as follows:

  1. Count the number of ways in which one can make an ordered list of k different elements from the set of n. This is equivalent to calculating the number of k-permutations.
  2. Recognizing that we have listed every subset many times, we correct the calculation by dividing by the number of different lists containing the same k elements:

<math> {n \choose k} = \frac{P(n,k)}{P(k,k)} </math>

Since

<math> P(n,k) = \frac{n!}{(n-k)!} </math>
(see factorial), we find

<math> {n \choose k} = \frac{n!}{k! \cdot (n-k)!} </math>

It is useful to note that C(n, k) can also be found using Pascal's triangle, as explained in the binomial coefficient article.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Westhampton Beach, New York

... size is 2.81. In the village the population is spread out with 20.5% under the age of 18, 6.1% from 18 to 24, 24.6% from 25 to 44, 28.2% from 45 to 64, and 20.7% who ...

 
 
 
This page was created in 23.6 ms