Combinatorics for Programmers

How many passwords can a hacker try? How many times will a nested loop run? Will two keys collide in a hash table? These are counting questions, and the branch of mathematics that answers them is combinatorics. For programmers, combinatorics is not abstract theory; it is how you estimate running time, judge security and design efficient algorithms.

The Two Basic Counting Rules

Almost every counting argument is built from two rules:

• Rule of product: if one choice can be made in \( m \) ways and a second, independent choice in \( n \) ways, together they can be made in \( m \times n \) ways.
• Rule of sum: if a task can be done in \( m \) ways or in \( n \) ways, with no overlap, there are \( m + n \) ways.

In code, the rule of product matches nested loops and the rule of sum matches if/else branches.

Worked Example 1: Password Strength

A system allows 8-character passwords using lowercase letters, uppercase letters and digits. How many passwords are possible, and how long would brute force take at \( 10^{10} \) guesses per second?

Step 1. Characters per position. \( 26 + 26 + 10 = 62 \) (rule of sum).

Step 2. Positions. Each of 8 positions is independent, so by the rule of product:

$$ 62^8 = 218{,}340{,}105{,}584{,}896 \approx 2.18 \times 10^{14} $$

Step 3. Time. \( \dfrac{2.18 \times 10^{14}}{10^{10}} \approx 21{,}834 \) seconds, about 6 hours.

Step 4. Compare with 12 characters. \( 62^{12} \approx 3.23 \times 10^{21} \), which at the same rate takes about \( 3.23 \times 10^{11} \) seconds, roughly 10,000 years. Adding four characters multiplies the work by \( 62^4 \approx 14.8 \) million. Length beats complexity.

Permutations: Order Matters

The number of ways to arrange \( n \) distinct items in order is

$$ n! = n \times (n-1) \times \cdots \times 2 \times 1 $$

Choosing and arranging \( r \) of them gives

$$ P(n, r) = \frac{n!}{(n - r)!} $$

Factorials grow explosively: \( 10! = 3{,}628{,}800 \) and \( 20! \approx 2.43 \times 10^{18} \). This is why the brute-force solution to the travelling salesman problem, which checks every ordering of cities, becomes hopeless beyond about a dozen cities, and why programmers look for smarter algorithms.

Combinations: Order Does Not Matter

When we just pick a group, the count is the binomial coefficient

$$ \binom{n}{r} = \frac{n!}{r!\,(n - r)!} $$

Worked Example 2: Counting Loop Iterations

How many times does the inner statement run?

for i in range(n): for j in range(i + 1, n): compare(a[i], a[j])

Step 1. Recognise the pattern. Each run picks a pair of indices with \( i < j \). Every unordered pair appears exactly once.

Step 2. Count pairs.

$$ \binom{n}{2} = \frac{n(n - 1)}{2} $$

Step 3. Check with \( n = 5 \). Directly: \( i = 0 \) gives 4 runs, \( i = 1 \) gives 3, then 2, then 1, then 0. Total \( 4 + 3 + 2 + 1 = 10 \), and \( \binom{5}{2} = \frac{5 \times 4}{2} = 10 \). It matches.

Step 4. Conclusion. The loop is \( O(n^2) \). For \( n = 100{,}000 \) it runs about \( 5 \times 10^9 \) times, a strong hint to look for a better algorithm such as sorting first.

Pascal's Triangle in Code

Binomial coefficients satisfy \( \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \), which allows computing them with addition only, avoiding huge factorials and overflow. This is a classic introduction to dynamic programming.

Subsets and Bitmasks

A set of \( n \) items has \( 2^n \) subsets, because each item is either in or out. Programmers exploit this with bitmasks: the integers from \( 0 \) to \( 2^n - 1 \) correspond one-to-one with subsets, bit \( k \) indicating whether item \( k \) is included. For \( n = 3 \), the mask \( 101_2 = 5 \) represents \( \{\text{item } 0, \text{item } 2\} \). Looping over all masks enumerates every subset, a standard technique for small \( n \) (up to about 20 to 25).

The Pigeonhole Principle and Hashing

If you put \( n + 1 \) pigeons into \( n \) holes, at least one hole holds two. Simple as it sounds, it proves that any hash function from a large set into a smaller one must have collisions, and that no lossless compression algorithm can shrink every file.

The birthday paradox shows collisions arrive much sooner than intuition suggests. The probability that \( k \) people all have different birthdays is

$$ P(\text{no match}) = \frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{365 - k + 1}{365} $$

For \( k = 23 \) this is about \( 0.4927 \), so the chance of a shared birthday is about \( 50.7\% \). In general, collisions become likely after about \( \sqrt{N} \) random items from \( N \) possibilities. A 32-bit hash (\( N \approx 4.3 \times 10^9 \)) reaches a 50% chance of a collision after only about 77,000 items, which is why secure systems use hashes of 256 bits.

Stars and Bars: Distributing Identical Items

How many ways can \( n \) identical items be split among \( k \) distinct groups? Represent the items as stars and use \( k - 1 \) bars as dividers:

$$ \binom{n + k - 1}{k - 1} $$

Worked Example 3: Allocating Servers

Five identical tasks are distributed among three servers (a server may get none). In how many ways?

Step 1. Model. Count solutions of \( x_1 + x_2 + x_3 = 5 \) with \( x_i \ge 0 \).

Step 2. Apply stars and bars. \( n = 5 \), \( k = 3 \):

$$ \binom{5 + 2}{2} = \binom{7}{2} = 21 $$

Step 3. Variation. If every server must receive at least one task, first give each one task, leaving 2 to distribute freely: \( \binom{2 + 2}{2} = \binom{4}{2} = 6 \).

Step 4. Sanity check. The six arrangements with every \( x_i \ge 1 \) are the orderings of \( (3,1,1) \) (3 ways) and \( (2,2,1) \) (3 ways), giving 6. Correct.

Inclusion-Exclusion

To count items with property A or B, add both counts and subtract the overlap:

$$ |A \cup B| = |A| + |B| - |A \cap B| $$

For example, among 1 to 100, there are 33 multiples of 3, 20 multiples of 5 and 6 multiples of 15, so \( 33 + 20 - 6 = 47 \) numbers are divisible by 3 or 5. That is exactly the kind of quick check you can use to test the output of a FizzBuzz-style program.

Catalan Numbers

The Catalan numbers \( 1, 1, 2, 5, 14, 42, \ldots \), given by \( C_n = \frac{1}{n+1}\binom{2n}{n} \), count the number of binary search tree shapes with \( n \) nodes, the number of valid bracket sequences with \( n \) pairs, and many other structures. For \( n = 3 \), \( C_3 = \frac{1}{4}\binom{6}{3} = 5 \): there are 5 distinct BST shapes with three keys.

Did You Know?

• There are \( 52! \approx 8.07 \times 10^{67} \) ways to shuffle a deck of cards, so a properly shuffled deck has almost certainly never appeared before in history.
• Early online poker software was cracked in the late 1990s partly because its shuffling used a 32-bit random seed, which can produce at most about 4.3 billion of those orderings.

Key Takeaways

• The rules of product and sum match nested loops and branches in code.
• Use permutations when order matters and combinations when it does not.
• \( 2^n \) subsets can be enumerated with bitmasks.
• The pigeonhole principle and birthday paradox explain why hash collisions are inevitable and arrive early.
• Stars and bars, inclusion-exclusion and Catalan numbers solve many distribution and structure-counting problems.

If counting problems or an algorithms assignment has you stuck, Amathify's subject experts and PhD scholars can provide clear step-by-step solutions; reach us on WhatsApp or through the Ask a Question form.