Combinatorics in Software Engineering: Seven Counting Ideas, from Test Matrices to Parse Trees

By Sergey Nosov

5 October 2026

A product that supports three browsers, two languages, and four screen sizes has twenty-four test configurations before anyone writes a test. Ten on/off feature flags multiply that to 24,576. Insert random keys into a hash table with one hundred slots, and a collision becomes more likely than not with the thirteenth key. Amazon says that Route 53 gives each customer domain four of its 2,048 virtual name servers, which allows about 730 billion distinct combinations. Each of these is a counting question, and combinatorics is the branch of mathematics that answers counting questions.

Each idea here is simple on its own. The value is in recognizing that the problem in front of you is a counting problem, and in knowing which tool counts it. This article covers seven tools: permutations and combinations, Cartesian products, the pigeonhole principle, binomial coefficients, inclusion–exclusion, graph counting, and recursive counting. For each, I give the definition, where it shows up in development work, and at least one number worked out. I checked every calculation in JavaScript on Node.js 22, and the article includes the functions that do the work. This article is a companion to Functional Completeness and the Building Blocks of Logic. Boolean algebra tells you what a circuit can compute; combinatorics tells you how many cases you have to consider.

Permutations and Combinations: Does Order Matter?

A permutation is an arrangement, so order matters. A combination is a selection, so order does not. Choosing k items out of n gives n! / (n − k)! permutations and n! / (k! (n − k)!) combinations, because every combination of k items can be arranged in k! orders.

A third case trips people up: sequences in which items may repeat. Strings of length k over an alphabet of n characters number n ** k, written with JavaScript’s exponent operator. A generator that lists every four-character string of uppercase letters, lowercase letters, and digits counts these, not permutations: 62 ** 4 is 14,776,336 strings. Forbid repeated characters and the count drops to 62 × 61 × 60 × 59, or 13,388,280 permutations.

The exponent explains why password length beats character variety. Fifteen lowercase letters allow 26 ** 15, about 1.7 × 10²¹ strings. Eight characters drawn from the ninety-four printable ASCII characters other than the space allow 94 ** 8, about 6.1 × 10¹⁵, roughly 275,000 times fewer. NIST’s password guideline, SP 800-63B-4, published in July 2025, takes the same view. It states that “Password length is a primary factor in characterizing password strength.” It requires at least fifteen characters for a password used on its own. It also says that verifiers “SHALL NOT impose other composition rules (e.g., requiring mixtures of different character types) for passwords.”

Treat the count as a ceiling, not a strength rating. It assumes that every string is equally likely, which holds for a random generator and fails for people. The same NIST document says that “estimating entropy for user-chosen passwords is challenging.”

Order matters for workflows too. A six-step wizard whose steps can be completed in any order has 6!, or 720, possible sequences, and ten steps have 3,628,800. Testing them all is rarely affordable. NIST’s guide Practical Combinatorial Testing (SP 800-142, October 2010) describes sequence covering arrays, which “ensure that any t events will be tested in every possible t-way order.” For ten events, it reports that fourteen tests cover every ordering of every three events, all 720 of them.

Forms bring the two ideas together. Six optional fields, each filled or empty, give sixty-four fill patterns (2 ** 6). That total is also the sum of the combinations of every size, from no fields filled to all six.

Cartesian Products: Why Test Matrices Explode

The Cartesian product of several sets is the set of all ordered tuples that take one element from each. Its size is the product of the set sizes, so a matrix of three browsers, two languages, and four screen sizes holds twenty-four configurations (3 × 2 × 4). Every new dimension multiplies the total. Running the whole product is exhaustive testing, and it stops being affordable quickly.

Combinatorial testing covers a slice of the product instead: every pair of values, or every triple, rather than every full combination. The justification is empirical. NIST began studying how many parameters it takes to trigger real failures in 1999, and its guide sums up the results in what it calls the interaction rule. “Most failures are induced by single factor faults or by the joint combinatorial effect (interaction) of two factors, with progressively fewer failures induced by interactions between three or more factors.” In a NASA application that NIST studied, a single parameter value triggered 67 percent of failures, two or fewer triggered 93 percent, and three or fewer 98 percent. The same guide warns that pairwise testing may miss 10 to 40 percent or more of the bugs in a system, and that it is not sufficient for mission-critical software.

The savings depend on how many parameters there are. The browser matrix still needs twelve configurations for pairwise coverage, half of the full product. Each of the twelve browser and screen-size pairs needs its own test, and the two languages fit around them. With more parameters, the gap widens quickly. NIST’s guide works through a panel of thirty-four on/off switches, about 17 billion settings in all. It reports that “all 3-way interactions can be tested with only 33 tests, and all 4-way interactions with only 85.”

Ten on/off flags show how far the reduction can go. Exhaustive testing needs 1,024 configurations. Six are enough for every pair of flags to appear in all four combinations of on and off:

    A B C D E F G H I J
1:  0 0 0 0 0 0 0 0 0 0
2:  1 1 1 1 1 1 0 0 0 0
3:  1 1 1 0 0 0 1 1 1 0
4:  1 0 0 1 1 0 1 1 0 1
5:  0 1 0 1 0 1 1 0 1 1
6:  0 0 1 0 1 1 0 1 1 1

Each row is a test run and each column a flag. The design is not luck. Every column has a 1 in exactly three of the last five rows. Each flag uses a different set of three, and there are exactly ten ways to choose three rows out of five. Any two columns share a row where both are 1, each has a 1 where the other has a 0, and the first row is all zeros. Five configurations are not enough: an exhaustive search shows that they can cover every pair for at most four flags. Checking coverage takes a few lines:

const tests = [
  "0000000000",
  "1111110000",
  "1110001110",
  "1001101101",
  "0101011011",
  "0010110111",
];

// Every pair of flags must show 00, 01, 10, and 11 in some test.
function coversAllPairs(rows) {
  const flags = rows[0].length;
  for (let a = 0; a < flags; a++) {
    for (let b = a + 1; b < flags; b++) {
      const seen = new Set(rows.map((r) => r[a] + r[b]));
      if (seen.size < 4) return false;
    }
  }
  return true;
}

console.log(coversAllPairs(tests)); // true

Real parameter models usually have more than two values per parameter, and they carry constraints, such as a payment method offered only in some countries. Building those arrays by hand is impractical. NIST’s ACTS and Microsoft’s open-source PICT generate covering arrays from a model of parameters and constraints. Put the constraints into the generator rather than deleting invalid tests afterward. PICT’s documentation explains why: “an offending test case may cover other, possibly valid, pairs that would not otherwise be tested.” The PICT README claims that “testing all pairs is an effective alternative to exhaustive testing and much less costly.” NIST’s numbers say how effective, and where pairs stop being enough. My Software Development Principles series treats pairwise testing as a principle of its own, with the indicators of proper application and the common violations.

The Pigeonhole Principle: When a Collision Is Certain

The pigeonhole principle says that if you put more items into containers than there are containers, at least one container holds more than one item. Hash 101 keys into one hundred slots, and at least two keys share a slot. No hash function can prevent it.

The principle is a proof technique more than a calculation, and three of its proofs matter in daily work:

The Birthday Bound: When a Collision Is Likely

Pigeonhole says when a collision is certain. In practice, collisions arrive far earlier. Suppose k values land in n equally likely slots. The chance that they all land in different slots is the product of 1 − i / n for each i from one to k − 1. The chance of at least one collision passes one half near √(2n ln 2), about 1.18 times the square root of n. This is the birthday problem: twenty-three people make a shared birthday more likely than not, at 50.7 percent.

For the hash table above, the thirteenth key makes a collision more likely than not, long before the 101st key makes one certain. A random 32-bit identifier reaches even odds of a duplicate at about 77,000 values. RFC 9562, the May 2024 standard that replaced RFC 4122, gives version 4 UUIDs 122 random bits, which push even odds out to about 2.7 × 10¹⁸ values. The rule of thumb: an identifier with b random bits has about a 39 percent chance of a duplicate after 2 ** (b / 2) values. Size identifiers by half their bits.

// Exact chance that k values in n equally likely slots
// include at least one collision.
function collisionChance(k, n) {
  let allDistinct = 1;
  for (let i = 1; i < k; i++) allDistinct *= 1 - i / n;
  return 1 - allDistinct;
}

// For huge n, 1 - i / n rounds to exactly 1, so use the
// approximation 1 - e^(-k(k - 1) / 2n). Math.expm1 keeps
// tiny results that 1 - Math.exp(...) would round to 0.
function collisionChanceApprox(k, n) {
  return -Math.expm1((-k * (k - 1)) / (2 * n));
}

console.log(collisionChance(13, 100)); // 0.557...
console.log(collisionChance(23, 365)); // 0.507...
console.log(collisionChanceApprox(77163, 2 ** 32)); // 0.4999...
console.log(collisionChanceApprox(1e9, 2 ** 122)); // 9.40...e-20

The last line is the reassuring one: a billion random UUIDs carry about a one-in-10¹⁹ chance of any duplicate, provided that the bits really are random. Generate them with a cryptographically secure generator, as I described in Secure Random Number Generation for App Developers. RFC 9562 leaves the judgment to the application: “Implementations should weigh the consequences of UUID collisions within their application.”

Binomial Coefficients: Counting the Ways to Choose

The binomial coefficient C(n, k), read n choose k, counts the subsets of size k in a set of n. Picking three servers out of ten for a deployment can be done in C(10, 3), or 120, ways. The coefficients form Pascal’s triangle, where each one is the sum of the two above it.

The textbook formula, n! / (k! (n − k)!), is the wrong way to compute it. Factorials outgrow fixed-size integers fast: 20! fits in a signed 64-bit integer, and 21! does not fit even in an unsigned one. In JavaScript’s floating-point numbers, the formula fails quietly. It returns 155117519.99999997 for C(30, 15), whose true value is 155,117,520, and NaN for C(200, 3), because 171! already overflows to Infinity. Multiply and divide one step at a time in BigInt instead, and every intermediate result stays an exact integer:

// Exact n choose k with BigInt. After step i, result
// equals C(n - k + i, i), so every division is exact.
function choose(n, k) {
  n = BigInt(n);
  k = BigInt(k);
  if (k < 0n || k > n) return 0n;
  if (k > n - k) k = n - k;
  let result = 1n;
  for (let i = 1n; i <= k; i++) {
    result = (result * (n - k + i)) / i;
  }
  return result;
}

console.log(choose(10, 3)); // 120n
console.log(choose(8, 2)); // 28n
console.log(choose(2048, 4)); // 730862190080n

Binomial coefficients sit under one of the most useful isolation patterns in cloud engineering. In a 2019 article in the Amazon Builders’ Library, Colm MacCarthaigh describes shuffle sharding: instead of splitting workers into fixed shards, give each customer its own combination of workers. With eight workers and two per customer, there are twenty-eight possible shuffle shards. A problem that takes down one customer’s pair of workers then has a scope of impact, in his words, of “just 1/28th.” Route 53 applies the same arithmetic at scale: 2,048 virtual name servers, four per customer domain, and C(2048, 4), or 730,862,190,080, possible shards. The article says that AWS uses that headroom to “ensure that no customer domain will ever share more than two virtual name servers with any other customer domain.”

The same coefficients give the odds that a quorum survives. Suppose each of n replicas is up with probability p, independently of the others. The chance that at least m are up is the sum of C(n, i) × p ** i × (1 − p) ** (n − i) for every i from m to n:

// Chance that at least m of n independent replicas are up,
// when each one is up with probability p.
function atLeast(m, n, p) {
  let total = 0;
  for (let i = m; i <= n; i++) {
    total += Number(choose(n, i)) * p ** i * (1 - p) ** (n - i);
  }
  return total;
}

console.log(atLeast(2, 3, 0.99)); // 0.999702...
console.log(atLeast(3, 5, 0.99)); // 0.9999901494

With replicas that are each up 99 percent of the time, a majority of three is available 99.9702 percent of the time, and a majority of five 99.9990 percent. The catch is the word independently. Replicas that share a rack, a power supply, or a bad deployment fail together, and the binomial model then overstates their availability.

Inclusion–Exclusion: Counting Overlaps Once

When sets overlap, adding their sizes counts the shared members more than once. The inclusion–exclusion principle corrects the sum. For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|. For three, add the three sizes, subtract the three pairwise overlaps, and add back the members that belong to all three.

Suppose a dashboard shows 1,200 users with an administrator role, 800 with an auditor role, and 500 with a support role, and someone adds them up to 2,500 privileged accounts. Now suppose 300 users are both administrators and auditors, 250 are administrators with support access, 200 are auditors with support access, and 150 hold all three roles. Each pairwise count includes those 150. The real count is 1,200 + 800 + 500 − 300 − 250 − 200 + 150 = 1,900. The sum is 600 accounts too high, and the whole error is overlap, which is normal when users can hold several roles.

The principle works for probabilities too, and its first term is useful on its own. Suppose a request needs three independent dependencies, each down 0.1 percent of the time. Inclusion–exclusion gives the chance that at least one is down as 0.002997001. The first term alone, the sum of the three probabilities, gives 0.003. That first term is the union bound. It never underestimates, and when the probabilities are small, it is close enough to decide with. For independent events, the complement is shorter still: 1 − 0.999 ** 3 gives the same 0.002997001.

In data work, the trap is combining counts that were computed separately: search facets joined with OR, active users across several products, or code coverage across test suites. A union cannot be computed from the set sizes alone; it needs the overlaps too. When you have the rows, let the database deduplicate them, with UNION rather than UNION ALL, or with COUNT(DISTINCT …). When all you have are counts, inclusion–exclusion is the correct way to combine them, and it needs every intersection count.

Graph Combinatorics: Connections, Paths, and Cycles

An undirected graph with n nodes can have up to C(n, 2) = n(n − 1) / 2 edges. Fred Brooks used that count in The Mythical Man-Month (1975) to explain why adding people to a project does not divide the work evenly. “If each part of the task must be separately coordinated with each other part, the effort increases as n(n-1)/2. Three workers require three times as much pairwise intercommunication as two; four require six times as much as two.” The same count applies to services. Ten services that may all call each other have forty-five possible connections, or ninety if each direction of a call counts separately.

Paths multiply faster than connections. Suppose a request passes through layers of services, and every service in one layer can call every service in the next. The number of distinct call paths is then the product of the layer widths. That is the Cartesian product again. Twenty layers of three services give 3 ** 20, about 3.5 billion paths. Counting them does not mean walking them. A depth-first search that remembers the count for every node it has finished visits each node and edge only once:

// Count the distinct paths from `from` to `to` in a dependency
// graph. Memoized depth-first search; throws on a cycle.
function countPaths(graph, from, to) {
  const memo = new Map();
  const onPath = new Set();
  function visit(node) {
    if (node === to) return 1n;
    if (memo.has(node)) return memo.get(node);
    if (onPath.has(node)) throw new Error(`Cycle through ${node}`);
    onPath.add(node);
    let total = 0n;
    for (const next of graph[node] ?? []) total += visit(next);
    onPath.delete(node);
    memo.set(node, total);
    return total;
  }
  return visit(from);
}

const calls = {
  gateway: ["orders", "catalog", "accounts"],
  orders: ["pricing", "inventory"],
  catalog: ["pricing", "inventory"],
  accounts: ["pricing"],
  pricing: ["database"],
  inventory: ["database"],
};

console.log(countPaths(calls, "gateway", "database")); // 5n

The same search answers the dependency question. Package managers, build systems, and service start-up sequences all need an acyclic dependency graph, because a cycle has no valid order. The function throws when it reaches a node that is still on its own path, which is exactly a cycle. For the full job, a topological sort produces a valid order or proves that none exists. Shortest-path algorithms such as Dijkstra’s and A* work on the same graphs, but they search for the best path instead of counting all of them.

Recursive Counting: Catalan Numbers and Memoization

How many strings of n pairs of brackets are balanced? For three pairs there are five: ((())), (()()), (())(), ()(()), and ()()(). The general answer comes from a recursion. In every balanced string, the first opening bracket has a matching closing bracket. That pair splits the rest into two smaller balanced strings: one inside the pair and one after it. So the count for n + 1 pairs is the sum, over every split, of the count inside times the count after. These counts are the Catalan numbers, sequence A000108 in the On-Line Encyclopedia of Integer Sequences:

// Catalan numbers by dynamic programming:
// c[0] = 1, c[n + 1] = sum of c[i] * c[n - i] for i = 0..n.
function catalan(max) {
  const c = [1n];
  for (let n = 0; n < max; n++) {
    let sum = 0n;
    for (let i = 0; i <= n; i++) sum += c[i] * c[n - i];
    c.push(sum);
  }
  return c;
}

console.log(catalan(10).join(", "));
// 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796

The same numbers count the shapes of binary trees, which is why they matter to anyone who writes a parser. Give a grammar the ambiguous rule E → E + E | id, and the expression a + b + c + d has five parse trees, one for each way to place the parentheses: (((a + b) + c) + d), ((a + (b + c)) + d), ((a + b) + (c + d)), (a + ((b + c) + d)), and (a + (b + (c + d))). An expression with ten operands has 4,862. Precedence and associativity rules exist to pick one tree out of all of them.

The recursion also shows why memoization matters. The naive recursive Fibonacci function makes 331,160,281 calls to compute the fortieth Fibonacci number, because it solves the same subproblems again and again. Store each result the first time, and the same computation takes seventy-nine calls. The Catalan function above does the same with a table: it computes each value once, from the values before it.

Takeaways

Further Reading