Counting and Combinatorics

Why counting matters in IT

Many questions in IT are counting questions in disguise. How many addresses fit in a subnet? How many passwords would an attacker have to try? How many test runs cover every combination of feature flags? How many links does a network need if every site connects to every other site?

For small cases you could list every possibility and count them. Combinatorics, the mathematics of counting, gives you shortcuts that work just as well when the answer is in the billions. This page builds those shortcuts step by step, always with a small case you can check by hand first.

The product rule and the sum rule

Multiplying choices

Kestrel Energy runs servers at two sites, Amsterdam (ams) and Eindhoven (ehv), and each site has three tiers: web, app and database. How many different server roles is that? List them as a tree: first choose the site, then the tier.

Every site branches into the same three tiers, so the tree has 2 groups of 3 leaves: 2 × 3 = 6. This is the product rule: if a task consists of steps done one after another, and the first step can be done in m ways and the second in n ways no matter what you chose first, then the whole task can be done in m \cdot n ways. With more steps you keep multiplying.

Worked example: how many 4-digit PIN codes exist?

1. The first digit can be any of 10 digits (0 to 9).
2. The second digit can again be any of 10, whatever the first was. So far 10 × 10 = 100.
3. The third and fourth digits each multiply by 10 again: 100 × 10 × 10 = 10,000.

The same rule explains the familiar powers of two in networking. Each bit is a step with 2 options, so n bits give 2^n patterns: an IPv4 address of 32 bits has 2^{32} = 4{,}294{,}967{,}296 possible values, and a subnet with 8 host bits has 2^8 = 256 addresses (see the subnetting formulas for why two of them are not usable).

import itertools

sites = ["ams", "ehv"]
tiers = ["web", "app", "db"]
roles = [f"{s}-{t}" for s, t in itertools.product(sites, tiers)]
print(roles)
print(len(roles), len(sites) * len(tiers))

print(10 ** 4)          # 4-digit PIN codes
print(2 ** 32)          # IPv4 addresses
print(2 ** 5)           # on/off combinations of 5 feature flags

['ams-web', 'ams-app', 'ams-db', 'ehv-web', 'ehv-app', 'ehv-db']
6 6
10000
4294967296
32

The last line is a testing question: five independent on/off feature flags give 32 combinations to test. Ten flags give 1,024 and twenty give over a million, which is why test teams rarely test every combination and instead pick a smart subset (pairwise testing covers every pair of flag values with far fewer runs).

Adding alternatives

The sum rule is the partner of the product rule. If a task can be done in one of several ways that cannot both happen, you add. A service desk ticket can be raised by phone (one of 3 queues) or by the portal (one of 5 categories): a new ticket lands in one of 3 + 5 = 8 places. The question to ask yourself is: do I make both choices (multiply), or one or the other (add)?

Factorials and permutations

Factorial: all orderings

In how many orders can Kestrel's three on-call engineers, Amara, Tomasz and Hamid, be put on a rota? Count with the product rule:

1. The first slot can go to any of the 3.
2. The second slot goes to one of the 2 who are left.
3. The last slot goes to the 1 person remaining.

So there are 3 × 2 × 1 = 6 orders. This product of all whole numbers from n down to 1 is the factorial of n, written n! ("n factorial"):

By agreement 0! = 1: there is exactly one way to arrange nothing (do nothing). This is not a trick; it keeps the formulas below correct when a count is zero. Factorials grow fast: 10! = 3{,}628{,}800, and 100! has 158 digits.

Permutations: ordered selections

A permutation is an arrangement in which the order matters. Often you only arrange some of the items. Kestrel's NOC team has 10 engineers; one must be on call Monday, another Tuesday and a third Wednesday. How many rotas are possible?

1. Monday: 10 choices.
2. Tuesday: 9 choices (the Monday person is used).
3. Wednesday: 8 choices.
4. Product rule: 10 × 9 × 8 = 720.

This is the start of 10!, stopped after 3 factors. In general, the number of ordered selections of k items from n is

Read it as: "multiply k factors, starting at n and counting down". The fraction form gives the same answer because the factors from n-k down to 1 cancel: \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720.

Combinations: when order does not matter

Now a different question. A change review needs a panel of 3 of the 10 engineers, and the panel has no roles: Amara, Tomasz and Hamid is the same panel as Hamid, Amara and Tomasz. How many panels are possible?

1. Count ordered selections first: 720, as above.
2. Every panel of 3 people was counted once for each of its orderings, and 3 people have 3! = 6 orderings.
3. So divide: 720 ÷ 6 = 120 different panels.

A combination is such a selection in which order does not matter. The number of combinations of k items from n is the binomial coefficient, written \binom{n}{k} and read "n choose k":

It is the permutation count \frac{n!}{(n-k)!} divided by the k! orderings of each group. Two useful facts follow directly:

• \binom{n}{k} = \binom{n}{n-k}: choosing 3 people for the panel is the same as choosing the 7 who are not on it. So \binom{5}{2} = \binom{5}{3} = 10.
• Adding \binom{n}{k} for every k from 0 to n gives 2^n: every subset of n items has some size, and each item is either in or out (see Sets and Relations). For 4 items: 1 + 4 + 6 + 4 + 1 = 16.

Python's math module has all three counts built in, and itertools can list the actual arrangements so you can check a small case:

import itertools
import math

print(math.factorial(10))
print(math.perm(10, 3), math.comb(10, 3))
print(math.comb(5, 2), math.comb(5, 3))
print(sum(math.comb(4, k) for k in range(5)))

team = ["Amara", "Hamid", "Tomasz"]
print(len(list(itertools.permutations(team))))
for panel in itertools.combinations(team, 2):
    print(panel)

3628800
720 120
10 10
16
6
('Amara', 'Hamid')
('Amara', 'Tomasz')
('Hamid', 'Tomasz')

Counting links in a full mesh

A classic IT use: in a full mesh every site has a direct link to every other site. A link connects a pair of sites, and the pair Amsterdam–Eindhoven is the same link as Eindhoven–Amsterdam, so the number of links is the number of combinations of 2 from n:

The formula grows roughly with the square of n: 10 sites need 45 links, 100 sites need 4,950. That is why large networks use hub-and-spoke or partial meshes. The same count gives the number of secret keys needed when every pair of people shares its own symmetric key; the cryptography basics page shows that 1,000 people would need 499,500 keys.

import math

for sites in (5, 10, 100, 1000):
    print(f"{sites:>5} sites: {math.comb(sites, 2):>7,} links")

    5 sites:      10 links
   10 sites:      45 links
  100 sites:   4,950 links
 1000 sites: 499,500 links

Choosing the right formula

Two questions decide which count you need: does the order matter, and may the same item be chosen more than once?

Password and key spaces

The key space of a password scheme or cipher is the number of different passwords or keys it allows. It is a sequence count: with a pool of s symbols and a length of L, there are s^L possibilities. An attacker who tries keys at random or in order finds the right one, on average, after searching half of the space.

Security people usually state a key space in bits: the number of bits you would need to number every possibility, which is the logarithm base 2 of the count (see Powers, Roots and Logarithms). Worked example for 8 characters from lowercase, uppercase and digits:

1. Pool size: 26 + 26 + 10 = 62 symbols (sum rule: each character is one of these, not several).
2. Key space: 62^8 \approx 2.18 \times 10^{14} (product rule over 8 positions).
3. In bits: \log_2(62^8) = 8 \cdot \log_2 62 \approx 8 \cdot 5.954 \approx 47.6 bits.

import math

pool = 26 + 26 + 10        # lower, upper, digits
for length in (8, 12, 16):
    space = pool ** length
    print(f"{length:>2} chars: {space:.3e} combinations, {math.log2(space):.1f} bits")

 8 chars: 2.183e+14 combinations, 47.6 bits
12 chars: 3.226e+21 combinations, 71.5 bits
16 chars: 4.767e+28 combinations, 95.3 bits

What does that mean in time? Assume an attacker who has stolen a database of fast, unsalted hashes and can test 10 billion guesses per second (a plausible order of magnitude for dedicated hardware; slow password hashes cut it by many orders of magnitude, see how systems store passwords):

pool = 62
guesses_per_second = 10 ** 10
average_8 = pool ** 8 / 2 / guesses_per_second      # seconds; on average half the space
average_12 = pool ** 12 / 2 / guesses_per_second
print(f"8 chars: about {average_8 / 3600:.1f} hours")
print(f"12 chars: about {average_12 / (3600 * 24 * 365):,.0f} years")

8 chars: about 3.0 hours
12 chars: about 5,115 years

Four more characters turn three hours into about five thousand years, because each character multiplies the space by 62. Adding a symbol class (say 32 punctuation marks) only changes the base from 62 to 94, which adds less than one bit per character. Length wins. Passphrases of random words follow the same rule with words as the symbols: a list of 7,776 words gives about 12.9 bits per word.

import math

words = 7776               # a diceware word list (6^5)
print(f"{math.log2(words):.2f} bits per word")
print(f"{5 * math.log2(words):.1f} bits for five words")
print(f"{math.log2(94) - math.log2(62):.2f} extra bits per character from adding 32 symbols")

12.92 bits per word
64.6 bits for five words
0.60 extra bits per character from adding 32 symbols

The pigeonhole principle

The simplest counting fact of all: if you put more pigeons than there are holes, at least one hole holds two or more pigeons. This is the pigeonhole principle: when n items go into m boxes and n > m, some box contains at least two items. More precisely, some box holds at least \lceil n / m \rceil items (the ceiling rounds up to a whole number).

It sounds obvious, but it proves things that are not. A worked example: Kestrel's monitoring tool tags each ticket with an 8-bit value (256 possible tags) computed from its number, and 300 tickets arrive in a week.

1. Items: 300 tickets. Boxes: 256 tags.
2. 300 > 256, so at least two tickets share a tag, however cleverly the tag is computed.
3. At least \lceil 300 / 256 \rceil = 2 tickets share the fullest tag.

# Pigeonhole: 300 tickets, 8-bit tag (256 values) -> at least two share a tag
tickets = range(20001, 20301)
tags = {}
for t in tickets:
    tags.setdefault(t % 256, []).append(t)
print(len(tags), max(len(v) for v in tags.values()))

256 2

All 256 tags are used and the fullest one holds 2 tickets, exactly as the principle predicts. The same argument applies everywhere in IT:

• Hash collisions must exist. A hash function such as SHA-256 maps files of any length to 256-bit values. There are far more possible files than 2^{256} outputs, so some different files must share a hash. Security depends on collisions being infeasible to find in practice, not impossible to exist. How soon you can expect one by chance is a probability question: see the birthday paradox on Probability.
• Lossless compression cannot shrink everything. There are 2^n files of n bits but fewer shorter files, so no compressor can make every file smaller.
• Address pools run out. A /24 network has 254 usable host addresses, so a 255th device on that network cannot get an address of its own.