What are the main types of problems combinatorics solves?

AlgorithmsJunior~3 min read

Short answer

Enumerative combinatorics: counting the number of objects by rules (permutations, arrangements, combinations, the sum and product principles, inclusion-exclusion, generating functions).
Partitions and distributions: "balls and boxes," partitions of sets and integers, distributions with constraints.
Probability problems on finite spaces: computing probabilities by counting outcomes (binomial and hypergeometric distributions, the Bernoulli scheme).
Extremal combinatorics: finding the maximum/minimum of discrete structures under constraints (the pigeonhole principle, bounds and constructions).
Constructive and existence problems: building an object with given properties or proving (non)existence (often with the probabilistic method).
Combinatorial optimization: choosing an optimal discrete structure (matchings, coverings, routing), often on graphs.

Problems: "How many are there...?" Techniques: the sum and product principles, permutations (n!), arrangements A(n, k) = n!/(n−k)!, combinations C(n, k) = n!/(k!(n−k)!), variants with repetition, inclusion-exclusion, recurrences, and generating functions.

Example: in how many ways can 5 out of 10 employees be seated in 5 different seats? Answer: A(10, 5) = 10!/5!.
Example: in how many ways can 3 reviewers be chosen out of 10? Answer: C(10, 3) = 120.

2) Partitions and distributions

Problems of distributing items into categories/"boxes" under constraints (items distinguishable/indistinguishable, boxes distinguishable/not, empty boxes allowed/forbidden), partitions of sets and integers.

The "stars and bars" method: the number of solutions to x1 + … + xk = n with xi ≥ 0 equals C(n + k − 1, k − 1).
Stirling numbers S(n, k): partitions of a set into k nonempty subsets; Bell numbers: all partitions of a set.
Example: distributing 7 identical candies among 3 children (empty shares allowed): C(7 + 3 − 1, 3 − 1) = C(9, 2) = 36.

3) Probability problems on finite outcomes

In equiprobable spaces, the probability of an event is the ratio of the number of favorable outcomes to the total. Combinations and the hypergeometric distribution are often used; for independent trials, the Bernoulli scheme and the binomial distribution.

Example: the probability of getting exactly 2 aces in a 5-card hand out of 52 cards: C(4, 2) · C(48, 3) / C(52, 5).

4) Extremal combinatorics

The problem is to find the largest/smallest possible values of parameters of discrete structures under constraints. The pigeonhole principle, the handshake lemma, two-sided bounding methods, and the probabilistic method are used.

Example: among 13 people, two will be found who were born in the same month (13 > 12, by the pigeonhole principle).

5) Constructive and existence problems

The task is to build an object with given properties (graph colorings, codes, block designs) or to prove impossibility/existence. Invariants, parity, and the probabilistic method (proving existence without an explicit construction) are often used.

6) Combinatorial optimization

Optimization problems on discrete structures: minimum coverings/vertex covers, maximum matchings, assignment, routing, scheduling. Related to graphs, linear programming, and algorithms. In applied programming these come up in planning, resource allocation, and optimizing tests and configurations.

Basic principles and formulas (cheat sheet)

Sum principle: if objects are chosen from mutually exclusive options A and B, the total is |A| + |B|.
Product principle: a sequential choice multiplies the numbers of options.
Permutations: n!; with repetition: n! / (r1! r2! …).
Arrangements: A(n, k) = n! / (n − k)!.
Combinations: C(n, k) = n! / (k!(n − k)!).
Combinations with repetition: C(n + k − 1, k).
Inclusion-exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|; generalizes to more sets.

Example: a mini utility for typical calculations (JavaScript)

/* Basic counting functions: permutations, arrangements, combinations, stars-and-bars, and hypergeometric probability */
function factorial(n) {
  if (n < 0 || !Number.isInteger(n)) throw new Error('n must be a non-negative integer');
  let r = 1;
  for (let i = 2; i <= n; i++) r *= i;
  return r;
}

function nPr(n, k) {
  if (k < 0 || k > n) return 0;
  let r = 1;
  for (let i = 0; i < k; i++) r *= (n - i);
  return r; // equals n! / (n-k)!
}

function nCr(n, k) {
  if (k < 0 || k > n) return 0;
  k = Math.min(k, n - k);
  let res = 1;
  for (let i = 1; i <= k; i++) {
    res = (res * (n - k + i)) / i; // the multiplicative formula is stable
  }
  return Math.round(res);
}

// "Stars and bars": the number of solutions to x1+...+xk = n, xi >= 0
function starsAndBars(n, k) {
  if (n < 0 || k <= 0) return 0;
  return nCr(n + k - 1, k - 1);
}

// Hypergeometric probability: out of N objects, K "successes", choose n without replacement, probability of exactly k successes
function hypergeom(N, K, n, k) {
  if (k < 0 || k > K || k > n || n > N) return 0;
  const favorable = nCr(K, k) * nCr(N - K, n - k);
  const total = nCr(N, n);
  return favorable / total;
}

// Usage examples
console.log('A(10,5) arrangements:', nPr(10, 5)); // 30240
console.log('C(10,3) combinations:', nCr(10, 3));   // 120
console.log('Permutations of 8 elements:', factorial(8)); // 40320
console.log('Distributing 7 identical candies among 3 children:', starsAndBars(7, 3)); // 36
console.log('P(exactly 2 aces in 5 cards):', hypergeom(52, 4, 5, 2)); // ≈ 0.0399

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.