Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 36 ยท Projects and Practice

Project: A Counting Library

Build a small, tested counting library in Python: permutations, combinations, multisets, derangements, Stirling, Bell, Catalan and partitions, cross-checked by brute force.

In this project you assemble the formulas from the whole course into one small library, and then build a test harness that proves each function correct by comparing it with brute-force enumeration. The second part matters more than the first: a counting formula you have not cross-checked is only a guess.

What we build

A set of functions, all exact (Python integers), each with a clear definition:

Function Counts
perm(n, k) ordered selections of k from n
comb(n, k) unordered selections
multichoose(n, k) multisets of size k from n kinds
derangements(n) permutations with no fixed point
stirling2(n, k) set partitions into k blocks
bell(n) all set partitions
catalan(n) balanced parentheses, binary trees, ...
partitions_count(n) integer partitions
surjections(n, k) onto functions, by inclusion-exclusion

Step 1: write the functions

Each uses the best method from earlier lessons: closed forms where they exist (Catalan, multichoose by stars and bars), recurrences with memoization where they do not (Stirling, derangements D_n = (n-1)(D_{n-1} + D_{n-2})), and the coin-change loop for partitions.

Python The library and known-value tests

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 tests are known values: for example C(52,5) = 2,598,960 poker hands, D_8 = 14,833, B_8 = 4,140, and the ninth test checks that two different formulas for surjections agree. assert stops with the failing index if anything is wrong.

Step 2: cross-check against brute force

Known values are a spot check. A stronger test compares each function with an enumeration that does not use the formula at all. itertools makes brute force easy for small sizes:

  • permutations(range(n)) for n!;
  • combinations(range(n), k) for binomials;
  • combinations_with_replacement for multisets;
  • a filter on permutations for derangements;
  • product((0, 1), repeat=n-1) for compositions;
  • a filtered product for strings avoiding a pattern.
Python Formula versus 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.

All six rows print ok. The last row tests a recurrence you derive yourself: strings with no three equal bits in a row satisfy a_n = a_{n-1} + a_{n-2} starting at 2, 4 (append the opposite bit, or double a run of length 1), giving 68 for n = 8.

flowchart LR
    A["Choose formula or recurrence"] --> B["Implement"]
    B --> C["Known-value assertions"]
    C --> D["Brute-force cross-check on small n"]
    D --> E["Trust it for large n"]

Verification before trust.

Step 3: extend the library

Ideas for your own extensions, each worth a short test:

  1. Stars and bars with bounds using the product of truncated polynomials (generating functions).
  2. Necklaces and bracelets with Burnside (Burnside's lemma).
  3. Modular binomials with a factorial table (algorithms lesson).
  4. Ranking and unranking of permutations and subsets.
  5. A tiny command-line wrapper: python counting.py catalan 20.
  6. Property-based tests: check sum_k comb(n,k) == 2^n and bell(n) == sum stirling2 for random n.

Keep brute-force checkers even after the library is finished. Whenever you change a formula, a 5-second regression test saves hours.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why compare a formula with brute force instead of trusting a few known values?

    A formula can match a handful of values by luck; enumerating all small cases catches off-by-one and overlap mistakes.
  2. 2. Which brute-force object checks multichoose(5, 4)?

    Multisets of size 4 from 5 kinds are exactly the combinations with replacement.
  3. 3. What does assert do when a test fails?

    An AssertionError stops the run and shows the values that disagreed.
  4. 4. How many derangements of 7 objects are there?

    D(7) = 1854; D(8) = 14833.

Summary

  • A counting library is a set of exact functions, each justified by a formula or recurrence from the course.
  • Test twice: against known values, then against brute force from itertools on small inputs.
  • Extend it with Burnside, generating functions, modular arithmetic and ranking.

Next: Project: Poker, Lottery and Birthdays