Definition: Combinations

Let \(A\) be a finite (or infinite) set with at least \(n\) elements. A combination \(C_k\) of size \(0\le k \le n\) is a subset of a \(A\) with exactly \(k\) elements.

A combination can be generated by selecting elements of \(A\) and moving them from the set \(A\) into the set \(C_k\) \(k\) times:

\[\begin{array}{rcll} \text{initial situation}& : & C_0=\{\}&A_0=\{a_1,a_2,\ldots,a_n\}\\ \text{first selection} & : & C_1:=\{a_{i_1}\}&A_1:=A_0\setminus\{a_{i_1}\}\\ \text{second selection} & : & C_2:=\{a_{i_1},a_{i_2}\}&A_2:=A_0\setminus\{a_{i_1},a_{i_2}\}\\ &\vdots&\\ k\text{-th selection} & : & C_k:=\{a_{i_1},a_{i_2},\ldots,a_{i_k}\}&A_k:=A_0\setminus\{a_{i_1},a_{i_2},\ldots,a_{i_k}\}\\ \end{array}\]

Unlike in a permutation, the order of selection of elements does not matter (because the order of the elements of a set does not matter).

Explanations: 1

  1. Definition: Binomial Coefficients
  2. Proposition: Closed Formula For Binomial Coefficients
  3. Proposition: Recursive Formula for Binomial Coefficients
  4. Theorem: Binomial Theorem
  5. Proposition: Simple Binomial Identities

Definitions: 1

Thank you to the contributors under CC BY-SA 4.0!