Combination

In mathematics, combination is a selection of items from a collection, such that (unlike permutations) the order of selection does not matter

Introduction

In mathematics, a combination is a selection of items from a collection, such that (unlike permutations) the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements, the number of k-combinations is equal to

$$\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\frac{n(n-1) \cdots(n-k+1)}{k(k-1) \cdots 1}$$

which can be written using factorials as

$$\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\frac{n !}{k !(n-k) !}$$

When k exceeds n/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation

$$\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=\left(\begin{array}{c}{n} \\ {n-k}\end{array}\right)$$

for $0 \leqslant k \leqslant n$

Number of k-combinations for all k

The number of k-combinations for all k is the number of subsets of a set of n elements. There are several ways to see that this number is $2^{n}$. In terms of combinations

$$\sum_{0 \leq k \leq n}\left(\begin{array}{l}{n} \\ {k}\end{array}\right)=2^{n}$$

These combinations (subsets) are enumerated by the 1 digits of the set of base 2 numbers counting from 0 to $2^{n}-1$, where each digit position is an item from the set of n.

Given 3 cards numbered 1 to 3, there are 8 distinct combinations (subsets), including the empty set:

$$|\{\{ \} ;\{1\} ;\{2\} ;\{1,2\} ;\{3\} ;\{1,3\} ;\{2,3\} ;\{1,2,3\}\}|=2^{3}=8$$

Representing these subsets (in the same order) as base 2 numerals:

0 – 000

1 – 001

2 – 010

3 – 011

4 – 100

5 – 101

6 – 110

7 – 111