ngosangns Knowledge Base

Enumeration Problems

#technology#combinatorics#algorithms#backtracking

Updated: 2026-09-24

Enumeration problems ask for every configuration that satisfies a condition, and this note covers the counting and the algorithms behind them. It begins with arrangements with and without repetition, then permutations and combinations, with the formulas that size each family. The generation method comes next. It builds the first configuration, prints it, and derives the next one until none remain, which produces a lexicographic listing. Totality, reflexivity, antisymmetry, and transitivity define that order, and the note shows how sequences of different lengths compare. Backtracking closes the note, with a template that chooses one element at a time and undoes choices, plus branch and bound pruning for problems that need an optimum.

Table of Contents

Arrangements, Combinations, Permutations

  • Number of k-arrangements with repetition of a set of n elements: nkn^k
    • Example of one k-arrangement with repetition: 112(k=3)112(k=3)
  • Number of k-arrangements without repetition of a set of n elements: n(n−1)(n−2)...(n−(k+1))=n!(n−k)!n(n-1)(n-2)...(n-(k+1))=\frac{n!}{(n-k)!}
    • Example of one k-arrangement without repetition: 123(k=3)123(k=3)
  • Permutation: the number of k-arrangements without repetition of a set of n elements when k=nk=n
    • Example of one permutation: 1234(n=k=4)1234(n=k=4)
  • Combination: a k-combination of a set X of n elements is a collection Y of subsets, where each subset has k elements
    • The permutations of a subset in Y are exactly the k-arrangements without repetition of the set X
    • The number of permutations of a subset in Y is k!k!
    • Number of subsets in Y = (number of k-arrangements without repetition of set X / k!k!)
    • Example of one subset in Y: (1,2,3)=(3,2,1)(1,2,3)=(3,2,1)

The Generation Method

  • Generation algorithm: 
    〈Build the first configuration〉;
repeat
〈Output the current configuration〉;
〈From the current configuration, generate the next one if any remain〉;
until 〈no configurations left〉;
  • The result of the generation method is called a dictionary (lexicographic listing)
  • A total lexicographic order is a dictionary in which each result is greater than the previous one; it must satisfy the following requirements:
    • Totality: Either a ≤ b or b ≤ a
    • Reflexivity: a ≤ a
    • Antisymmetry: If a ≤ b and b ≤ a then a = b must hold
    • Transitivity: If a ≤ b and b ≤ c then a ≤ c
  • Comparing two sequences lexicographically:
    • Let a[1..n] and b[1..n] be two sequences of length n, where the elements of a and b already have a total order ≤. Then:
      • a < b if there exists a positive integer k: 1 ≤ k < n such that: 
        a[1]   = b[1]
a[2]   = b[2]
...
a[k-1] = b[k-1]
a[k]   = b[k]
a[k+1] < b[k+1]
      • a = b if a[i] = b[i] for all i: 1 ≤ i ≤ n
      • If the two sequences a and b have different lengths, lexicographic order can still be defined. Append special elements ∅ to the end of a or b so that their lengths are equal, and treat these ∅ elements as smaller than all other elements; this reduces the problem to comparing two sequences of the same length. Examples: 
        <1, 2, 3, 4> < <5, 6>
<a, b, c>    < <a, b, c, d>
'calculator' < 'computer'
  • Some lexicographic examples in the ebook:
    • Generating binary strings of length n
    • Listing k-element subsets
    • Listing permutations

The Backtracking Algorithm

  • Backtracking is used to solve the problem of enumerating configurations
  • Each configuration is built one element at a time, and each element is chosen by trying all possibilities
  • Example of backtracking applied to enumerating arrangements with repetition: 
    procedure Try(i: Integer);
begin
	for 〈every value V that can be assigned to x[i]〉 do
		begin
			〈Try x[i] := V〉;
			if 〈x[i] is the last element in the configuration〉 then
				〈Report the configuration found〉
			else
				begin
					〈Record that x[i] takes value V (if needed)〉;
					Try(i + 1); {Recursive call to choose x[i+1]}
					〈If needed, undo the record of trying x[i] := V so another value can be tried〉;
				end;
		end;
end;
  • Some problems in the ebook that apply backtracking:
    • The number decomposition problem
    • The N-queens problem
  • Branch and bound evaluation within the backtracking process
    • Helps prune early any options that are certainly not optimal or contain no solution
    • The branch and bound technique gives backtracking the ability to evaluate at each step
    • Related problems in the ebook:
      • The traveling salesman problem
      • The ABC sequence

See also: Problem Solving Approaches · Algorithm Development · Le Minh Hoang Book Notes