Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 68 ยท Projects

Project: A Combinatorics Toolkit

Build a small counting library from scratch, check every formula against brute-force enumeration, simulate the birthday paradox and print a tidy report.

Counting formulas are easy to misremember and easy to misapply, so a good habit is to never trust one until a computer has checked it on small cases. In this project you will build a tiny combinatorics library: functions for permutations, combinations, derangements, Catalan numbers and more, each paired with a brute-force counter that enumerates the objects one by one. When the formula and the enumeration agree, you can trust the formula on cases too big to enumerate.

The finished toolkit has four parts: exact counting functions, generators that produce the objects themselves, a verifier that compares the two, and a report that prints the results. We finish with a Monte Carlo simulation of the birthday paradox, checked against its exact probability.

You should be comfortable with Permutations and Combinations, Advanced Counting and Discrete Probability.

The toolkit plan

Formulas Fast exact counts with big integers.
Generators Produce the actual objects.
Verifier Compare formula to brute force.
Report One clean table of results.
1 / 2

Step 1: the counting functions

We start with the counts. Python integers never overflow, so factorials stay exact. We avoid computing factorial(n) / factorial(k) with floats; integer division // keeps everything exact. math.comb and math.perm exist, but writing our own versions once is a good way to understand them, and we compare ours to the built-ins.

The functions to write:

  • permutations_count(n, k): ordered selections of k from n, no repeats, nยท(nโˆ’1)ยทยทยท(nโˆ’k+1).
  • combinations_count(n, k): unordered selections, built by a product that divides at each step so numbers stay small.
  • multiset_count(n, k): unordered selections with repetition, by stars and bars, which equals C(n + k โˆ’ 1, k).
  • derangements_count(n): permutations with no fixed point, using the recurrence D(n) = (n โˆ’ 1)(D(n โˆ’ 1) + D(n โˆ’ 2)).
  • catalan(n): C(2n, n) / (n + 1).
  • stirling2(n, k): ways to split n items into k nonempty groups, using S(n, k) = kยทS(n โˆ’ 1, k) + S(n โˆ’ 1, k โˆ’ 1).
Python The counting functions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Choosing 5 cards from 52 gives 2,598,960 hands, and both our function and math.comb agree. The derangement numbers begin 1, 0, 1, 2, 9, 44, 265, 1854. The Catalan numbers begin 1, 1, 2, 5, 14, 42, 132, 429, 1430. The five Stirling numbers S(5, k) are 1, 15, 25, 10, 1, and they add up to 52, the fifth Bell number.

Notice the trick in combinations_count. After the loop step i, result equals C(n โˆ’ k + i, i), which is always an integer, so the floor division never loses anything.

Step 2: generators that build the objects

A count is only a number. To verify it we need the objects themselves. Generators fit well: they produce one object at a time without building a giant list.

Some come straight from itertools. For the others we write our own, because they have no ready-made equivalent: derangements (filter permutations), set partitions (recursive), and balanced parenthesis strings (the objects counted by Catalan numbers).

For set partitions, the recursive idea is: put the first element into an existing block, or into a new block of its own, then recurse on the rest.

Python Generators for each family

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three items have two derangements, (1, 2, 0) and (2, 0, 1). There are five balanced strings with 3 pairs, which is the Catalan number C(3), and five set partitions of {a, b, c}, which is the Bell number B(3). The last line prints 6, the multiset count for choosing 2 from 3 with repetition.

When a generator produces objects with a clever rule (like balanced_parentheses), the rule is exactly what you are testing. A wrong rule that produces too many or too few objects is caught the moment the count disagrees with the formula.

Step 3: the verifier

Now glue the pieces. A verifier takes a name, a formula function and a generator function, and compares them for a range of small inputs. It returns rows so a report can show them, and it never stops at the first mismatch, since we want to see all of them.

Make the interface uniform: both callables receive the same arguments. Here is the design.

Python
def verify(name, formula, enumerate_fn, cases):
    rows = []
    for args in cases:
        expected = formula(*args)
        actual = sum(1 for _ in enumerate_fn(*args))
        rows.append((name, args, expected, actual, expected == actual))
    return rows

We deliberately use sum(1 for _ in ...) rather than len(list(...)) so memory use stays constant even when the generator is large.

A verifier is itself code, so it can have bugs. A good test is to feed it a deliberately wrong formula and make sure it reports a mismatch. We do that below with a "formula" that forgets to subtract one.

Python Verifying formulas against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see 29/30 checks passed and a single mismatch line for the broken formula (formula 6, brute force 5). That deliberate failure shows the safety net actually works.

Step 4: the birthday paradox

How many people must be in a room before two probably share a birthday? Most people guess about 180. The true answer is 23. The exact probability that all n birthdays differ (ignoring leap days) is the product

365/365 ยท 364/365 ยท 363/365 ยทยทยท (365 โˆ’ n + 1)/365

and the probability of at least one match is one minus that. Note the connection to counting: the numerator is the permutation count P(365, n), and the denominator is the total count 365โฟ of ordered birthday lists.

We compute the exact answer with integers (using Fraction, so there is no rounding), then simulate with a fixed seed. The simulation should land close to the exact value, though it will never match exactly: that is the nature of Monte Carlo.

Python Exact and simulated birthday probabilities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The exact column reads 0.1169, 0.5073, 0.7063, 0.9704 and 0.9992, and the group of 23 is the first to pass 50%. The simulated values fluctuate by a few thousandths because a seed fixes the sequence but not the sampling error, which shrinks roughly like 1 divided by the square root of the number of trials.

Step 5: the report

The last piece turns results into something a person can read. A report function should align columns, so we compute the width of each column from the data instead of hard-coding it. We also include a section that shows what a formula predicts for large inputs where brute force is hopeless: C(100, 50) has 30 digits and no computer can enumerate it, but the formula answers instantly.

Python A formatted report

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first table shows, for example, 10! = 3628800 and Catalan(10) = 16796. The second table prints C(100, 50) = 100891344545564193334812497256, a number with 30 digits. The last line reveals a neat fact: the fraction of permutations that are derangements approaches 1/e โ‰ˆ 0.367879, and for n = 20 the two numbers agree to six decimal places.

Ideas to extend the project

  • Add integer partitions p(n) with the recurrence over the largest part, and verify against a generator.
  • Add a multinomial(n, groups) function and check it with distinct permutations of a word.
  • Count surjections from an n-set onto a k-set with k! * stirling2(n, k) and verify by enumerating all functions with itertools.product.
  • Turn the verifier into a command-line check that exits with an error when any row fails, so it can run before every commit.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the toolkit compare each formula with a brute-force count?

    Brute force is slow but obviously correct on small inputs, so matching it validates the formula that will be used where enumeration is impossible.
  2. 2. Why does combinations_count use result * (n - k + i) // i inside the loop?

    After step i the value equals C(n-k+i, i), which is an integer, so the floor division is exact and no float rounding appears.
  3. 3. How many balanced strings of parentheses use 4 pairs?

    Balanced strings with n pairs are counted by the Catalan numbers 1, 1, 2, 5, 14, ... so 4 pairs give 14.
  4. 4. In the birthday calculation, the numerator of the no-match probability counts what?

    The favourable outcomes are ordered lists of n different days, which number P(365, n). The total is 365 to the power n.
  5. 5. What does the deliberately broken formula in the verifier test demonstrate?

    A checker that has never been seen failing might be checking nothing. Feeding it a wrong formula proves it reports mismatches.

Summary

  • Write exact counting functions with integer arithmetic, and compare them with math.comb and math.perm.
  • Generators produce the objects themselves, so a counting rule can be tested by enumeration.
  • A verifier that reports every mismatch, and is itself tested with a wrong formula, makes counting code trustworthy.
  • The birthday problem is a counting argument: one minus P(365, n) over 365 to the n, with 23 people already above 50%.
  • Simulations with a fixed seed approximate exact answers but never equal them; use Fraction when you need exact probabilities.

Next: Project: Social Network Analyzer, where counting gives way to graphs.