Suggest an edit

Improve this article

Refine the answer for “What is a combination in combinatorics?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A combination (selection) is a choice of k elements out of n distinct ones, without regard to order and without repetition. The number of such choices is denoted C(n, k) and computed by the formula: C(n, k) = n! / (k! (n − k)!), where 0 ≤ k ≤ n.

Example: from 5 different books, choosing 2 for a trip can be done in 10 ways: C(5, 2) = 10.

## Detailed explanation

### Definition and notation

A combination is any subset of size k of a set of n pairwise distinct elements. It is denoted C(n, k), also expressed as "n choose k" (the binomial coefficient).

- Order does not matter.
- There is no repetition (each element can be chosen at most once).
- Parameter range: 0 ≤ k ≤ n; C(n, 0) = C(n, n) = 1.

Formula: C(n, k) = n! / (k! (n − k)!). A convenient equivalent without large factorials: C(n, k) = ∏_{i=1}^{k} (n − k + i) / i, often taking k = min(k, n − k) to reduce the number of iterations.

### When to use combinations

- Choosing a subteam/committee from employees (who is included matters, order does not).
- Problems of the form "how many subsets of size k".
- The number of ways to choose the positions of successes in a series of independent trials.

### Differences from other models

- Permutations: order matters, all n elements are used; the count is n!.
- Arrangements without repetition: order matters, k are taken out of n; the count is A(n, k) = n! / (n − k)!.
- Combinations: order does not matter, k are taken out of n; the count is C(n, k).

### Calculation examples

1. C(5, 2) = 5! / (2!·3!) = 120 / (2·6) = 10.
2. C(10, 3) = 10! / (3!·7!) = (8·9·10) / (2·3) = 120.
3. Symmetry: C(10, 7) = C(10, 3) = 120.

### Properties

- Symmetry: C(n, k) = C(n, n − k).
- Boundary values: C(n, 0) = C(n, n) = 1.
- Pascal's recursion: C(n, k) = C(n − 1, k) + C(n − 1, k − 1).
- Sum over k: ∑_{k=0}^{n} C(n, k) = 2^n (the number of all subsets of a set of n elements).

### Practical calculation without large factorials

Use the multiplicative formula with reduction at each step: successively multiply by (n − k + i) and divide by i, choosing k = min(k, n − k). This is stable even for large n, k.

### Code: computing C(n, k) and generating k-combinations (JavaScript)

```
function binom(n, k) {
  if (k < 0 || k > n) return 0n;
  // BigInt for precision at large n
  let K = BigInt(k);
  let N = BigInt(n);
  if (K > N - K) K = N - K; // symmetry
  let num = 1n;
  let den = 1n;
  for (let i = 1n; i <= K; i++) {
    num *= (N - K + i);
    den *= i;
    // reduce the fraction by GCD so the numbers do not grow too fast
    const g = gcd(num, den);
    num /= g;
    den /= g;
  }
  return num / den;
}

function gcd(a, b) {
  while (b !== 0n) [a, b] = [b, a % b];
  return a;
}

// Generate all k-combinations of array arr in lexicographic order
function combinations(arr, k) {
  const n = arr.length;
  if (k < 0 || k > n) return [];
  const idx = Array.from({ length: k }, (_, i) => i);
  const res = [];
  while (true) {
    res.push(idx.map(i => arr[i]));
    // Find the position to increment
    let t = k - 1;
    while (t >= 0 && idx[t] === n - k + t) t--;
    if (t < 0) break;
    idx[t]++;
    for (let i = t + 1; i < k; i++) idx[i] = idx[i - 1] + 1;
  }
  return res;
}

// Examples
console.log(String(binom(5, 2))); // "10"
console.log(combinations(["A", "B", "C", "D", "E"], 2));
```

### Connection to the binomial formula

The binomial coefficients C(n, k) are the coefficients of a^{n−k} b^{k} in the expansion of (a + b)^n. That is why the set of values for a fixed k across different n forms Pascal's triangle.

### Interview tips

- Always state the criteria out loud: order does not matter, no repetition - so it is a combination.
- Quickly distinguish the models: order matters → permutations/arrangements; order does not matter → combinations.
- Use the product-based formula instead of factorials to avoid overflow and simplify calculations on a whiteboard.
- Check edge cases: k = 0, k = n, and the symmetry C(n, k) = C(n, n − k).

> Summary: a combination is a way to count the number of subsets of a fixed size when order does not matter and elements are not repeated.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts812 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.