Counting, combinatorics, and finite probability

Ten records are available and three must be selected for evaluation. If the selection is an unordered subset, there are 120 possibilities. If the three records receive distinct roles, such as first, second, and third reviewer, there are 720. The inputs look the same, but the outcomes being counted differ. A counting formula is correct only for its declared model.

This module develops that modelling habit before introducing probability. Ask what an outcome contains, whether order matters, whether an object can repeat, and whether different constructions describe the same outcome. Once the outcome set is clear, addition, multiplication, bijections, and complementary counting justify the formula. A probability calculation adds a sampling rule; a finite collection is not automatically uniform.

Retrieval check: form a small Cartesian product, list a power set, explain a bijection, and state a proof by cases. Review sets and proofs if needed. Counts are nonnegative integers. We count finite outcomes here; later probability modules extend the language and distinguish probability from empirical frequency more fully.

The addition rule counts alternatives whose outcome sets are disjoint. If A and B do not overlap, then $|A\cup B|=|A|+|B|$. The vertical bars mean finite cardinality in this module, not absolute value of a number. If an outcome belongs to both sets, adding their sizes counts it twice. Either divide the outcomes into genuinely disjoint cases or correct the overlap explicitly in Section 5.

The multiplication rule counts successive choices when each first choice has the same number of permitted continuations. If there are a first-stage choices and b continuations for each, there are ab paths. For two independent choice sets this is the cardinality of their Cartesian product. Counting stages does not itself assert probabilistic independence; it describes the allowed construction tree. Probability independence is an additional property of a sampling model.

If continuation counts vary, sum the branch counts rather than multiplying by an unjustified common value. A catalogue may have two tasks allowing three workers each and one task allowing only one worker: there are seven permitted task–worker pairs, not nine. The product rule would become correct for an unrestricted catalogue in which every task allowed all three workers, but that would be a different constraint set.

A bijection is another counting tool: construct a one-to-one correspondence between a difficult outcome set and an easier one. To use it, verify that every allowed outcome has exactly one representation and every allowed representation yields an outcome. If a representation omits cases or duplicates them, the apparent correspondence cannot justify equal counts. Stars and bars in Section 4 is a particularly useful example.

Counting by construction needs the same attention to scope as a proof. A leaf of a decision tree should represent a completed allowed outcome, not an intermediate partial choice. If two different paths lead to the same outcome after order is discarded, leaf counting overcounts the unordered model. That is why drawing an ordered selection tree is not enough to count subsets without further adjustment.

Empty choices have identity counts. Selecting no positions produces one empty sequence, not zero sequences. The product of zero stage counts is one under the empty-product convention. In contrast, an actual stage with no permitted options prevents any complete outcome, so a product containing a zero factor is zero. These two situations should not be confused by the word “empty.”

In CS, decision paths describe configurations, strings, assignments, and search spaces. Counting a search space does not give the time taken by every algorithm exploring it; an algorithm may exploit structure or inspect only part. In AI, possible data splits depend on whether records are distinct, whether roles are named, and which group constraints apply. A formula describing arbitrary record subsets does not respect subject-level grouping unless the model includes that constraint.

An ordered selection of r distinct objects without replacement from n distinct objects has count

The first position has n choices, the next n−1, and each subsequent position one fewer. Factorial $n!$ is the product of positive integers through n, with $0!=1$. Selecting all n objects gives n! permutations. Selecting zero gives one empty ordered selection. If r>n and replacement is forbidden, the count is zero; the factorial expression above is stated only on its allowed range.

When repeated labels are indistinguishable, different named-object permutations can describe the same label string. For the multiset A,A,B, the distinct strings are AAB, ABA, BAA, only three. Temporarily naming the two A objects gives six permutations, and each final label string has exactly two such representations. Dividing by that common multiplicity gives $3!/2!=3$.

More generally, a multiset of N objects with label multiplicities $n_1,\ldots,n_k$ and $\sum n_i=N$ has $N!/(n_1!\cdots n_k!)$ distinct full arrangements. The numerator counts temporarily named objects; permutations within each equal-label group leave the final label string unchanged. Every label string has the same product of internal permutations, which justifies division. The fixed multiplicities and full-arrangement setting are assumptions of this formula.

Do not divide by an arbitrary symmetry factor without checking that every outcome has that many representations. Some problems have stabilised or exceptional cases: for example, repeated-label partial selections may have unequal numbers of named-position constructions. The pair AA can have one construction while AB has two in the three-position A,A,B model. Dividing three constructions by a guessed factor two would not produce the correct two distinct outcomes.

What counts as distinct depends on the problem. Two records with the same category label are normally still different records. Swapping them between named roles changes the record-level outcome even if the printed label sequence is unchanged. If only categories are recorded, the observed label outcomes may collapse multiple record choices. Keep the underlying outcome set and its representation separate when moving towards probability.

Counting ordered choices with replacement also needs consistent option sets. If each position has n allowed symbols, $n^r$ applies. If later allowed symbols depend on earlier selections, count the resulting branches. A password rule banning repeated characters or requiring at least one digit introduces constraints; neither n! nor $n^r$ automatically accounts for every such rule. Start with the construction and then identify the appropriate formula.

Boundary checks catch many formula mistakes. Verify r=0, r=1, r=n, and impossible r>n in the chosen model. For repeated arrangements, a multiset whose labels are all identical has one full label string, matching $N!/N!=1$. A formula giving zero or N! there describes a different notion of distinctness or contains a modelling error.

An unordered r-element subset of an n-element set is a combination. Its count is the binomial coefficient:

Each chosen subset of r distinct objects has exactly r! ordered arrangements. Dividing $P(n,r)$ by that common number therefore counts every subset once. This is an argument about equal representation multiplicity, not a formula to memorise independently of the model. Order is discarded and replacement is forbidden in this basic combination count.

Complementing a subset gives a bijection between r-element subsets and (n−r)-element subsets. Therefore $\binom nr=\binom n{n-r}$. The correspondence uses a fixed universe of n distinct objects, exactly as complements did in Module 03. The boundary counts $\binom n0=\binom nn=1$ are the empty subset and the full subset, not claims that these two subsets are the same object when n>0.

Pascal’s identity follows by distinguishing one named object x. An r-subset either excludes x, giving $\binom{n-1}r$ possibilities, or includes x, leaving $\binom{n-1}{r-1}$ choices for its remaining members. The cases are disjoint and exhaustive, hence

For n≥1 this includes boundary r values if we define a binomial coefficient as zero when the selection size is negative or exceeds its nonnegative top index. The proof’s cases explain both the identity and its recurrence. They do not depend on cancelling factorials and therefore show why the count has that form.

The binomial theorem connects subsets with algebra:

In a product of n copies of (a+b), each expanded term chooses b from exactly r positions and a from the rest. There are $\binom nr$ position subsets producing that monomial, which explains its coefficient. At n=0 both sides equal one by the empty-product convention. The statement uses commuting scalar a,b; matrix products need additional conditions because their order can matter.

Setting a=b=1 gives $2^n=\sum_{r=0}^n\binom nr$, another count of the power set by its disjoint subset-size classes. This connects Module 03’s include/exclude argument with the combination formula. Counting one collection in two different ways is a double-counting proof when each method is justified and both really describe the same collection.

Data splitting adds modelling details. Selecting r records for one named group determines the complementary group when every record belongs to exactly one of those two groups. Selecting training, validation, and test groups with fixed sizes gives a multinomial count rather than just one binomial coefficient. Grouped subjects, chronology, or eligibility rules can restrict the allowed partitions. A mathematically correct unconstrained count is not automatically the application’s count.

A uniform subset can be generated by making successive uniform choices without replacement and then discarding order. Each ordered sequence has the same probability, and each subset has exactly r! such sequences, so their total weights agree. That conclusion uses both properties. A procedure favouring certain records at an early stage can produce biased subsets even though it always returns r different records. “Random” in an implementation description should therefore be replaced by a precise mechanism before assigning probabilities.

Representation matters for repeated selections too. An ordinary set cannot record multiplicity: {A,A,B} is the same set as {A,B}. A multiset retains two copies of A and one of B; you can represent it by a tuple of counts or a sorted list of labels. The explorer uses double brackets for multisets to distinguish them from ordinary subset braces. Choosing a canonical sorted representation removes order while retaining repeated labels. Converting that representation to a set would discard another distinction and change the count again. Compare the representation with the outcome definition before using it as an enumeration key.

Distributing n identical tasks among k named workers means finding nonnegative integer tuples $(x_1,\ldots,x_k)$ whose sum is n. Tasks are indistinguishable, workers are distinguishable, and workers may receive zero. The count is

The stars and bars construction writes n stars for tasks and k−1 bars separating workers’ portions. A bar may be at an end or next to another bar, encoding zero allocations. The total string has n+k−1 positions, and choosing the bar positions determines it uniquely. Conversely, any permitted allocation produces exactly one such string. This bijection justifies the count.

Selecting r objects from n distinct types without caring about order and allowing repetition is the same nonnegative-count model: $x_i$ records how often type i is selected and $\sum x_i=r$. Its count is $\binom{n+r-1}r$ for n≥1. An ordered repeated sequence instead has $n^r$ possibilities. Forgetting order collapses sequences, but the multiplicity varies with repeated labels, so simple division by r! is generally incorrect.

Lower bounds can be removed by substitution. If every worker must receive at least one task, write $y_i=x_i-1\ge0$. The new total is n−k, giving $\binom{n-1}{k-1}$ when n≥k; when n<k, no allocation is possible. More general lower bounds $x_i\ge l_i$ use $y_i=x_i-l_i$ and reduce the total by $\sum l_i$. State feasibility before evaluating any factorial expression.

Upper bounds cannot be removed by the same subtraction alone. For five identical tasks among three named workers, each receiving at most two, start from 21 unrestricted allocations. A specified worker receiving at least three has six allocations after subtracting three from that worker, leaving two tasks among three workers. There are three such forbidden sets, and two workers cannot both receive three with only five tasks. Hence the valid count is $21-3\cdot6=3$, namely permutations of (2,2,1).

This example uses complementary counting and inclusion–exclusion, developed next. It also shows why checking constraints after applying an unrestricted formula matters. A formula can correctly count its model while incorrectly solving the posed problem. Bounds, named versus unnamed recipients, and distinguishability of tasks are all structural assumptions rather than implementation details.

If workers are unnamed, (2,1,2) and (1,2,2) may describe the same partition of task counts. The named-worker stars-and-bars formula would then overcount. Integer partitions are a different counting problem with different techniques; they are outside this module’s core. Do not divide by k! automatically, because allocations with equal portions have different symmetry multiplicities from allocations with distinct portions.

Empty boundaries remain informative. With zero tasks and k≥1 named workers there is one allocation, all zeros, matching the formula. With a positive minimum per worker and zero tasks there are none. With zero workers the declared formula does not apply; a separate model could allow one empty assignment only when there are also zero tasks. A precise statement keeps exceptional domains explicit.

When A and B overlap, their intersection was counted twice in $|A|+|B|$. Subtracting it once gives $|A\cup B|=|A|+|B|-|A\cap B|$. A membership proof divides the universe into A-only, B-only, intersection, and neither. Members of the first two regions contribute one on both sides; intersection members contribute $1+1-1=1$; neither contributes zero. This explains the correction rather than merely naming it.

For three sets, add singles, subtract pair intersections, and add the triple intersection:

A member of all three contributes three at first, loses three through pair subtractions, then gains one from the triple term. A member of exactly two contributes two minus one. A member of exactly one contributes one. Those disjoint membership cases cover the proof. More sets use alternating intersection terms, though explicit enumeration may be simpler for a very small teaching model.

Complementary counting calculates a desired count by subtracting its complement from a known total. It is useful when the undesired event has a simpler description: “at least one collision” is the complement of “all chosen buckets distinct.” The two cases must be exhaustive and disjoint in a common universe. Complementing an incomplete list of failures would omit other invalid cases.

The pigeonhole principle gives a guarantee rather than a probability. If n objects are placed in m boxes with n>m, at least one box contains two or more objects. If every box held at most one, the total would be at most m, contradicting n>m. More generally some box contains at least $\lceil n/m\rceil$ objects for positive m: otherwise all boxes would hold too few to reach the total.

Five named items assigned to four buckets must collide regardless of the assignment rule or whether choices are uniform. Three items in four buckets may collide, but need not: a distinct-bucket assignment is possible. Counting and a sampling model can describe its probability; the pigeonhole condition does not give a guarantee before the capacity is exceeded. High probability and certainty are different claims.

Proof by cases and proof by contradiction from Module 04 justify these tools. Inclusion–exclusion tracks each membership case’s coefficient. Pigeonhole assumes every box has insufficient occupancy and derives a count contradiction. The formula’s compactness should not obscure those reasons, especially when a new constraint changes which cases are possible.

An application may have unequal capacities. If bucket i has capacity $c_i$, more than $\sum c_i$ objects force an overflow somewhere. That is a direct extension of the same contradiction argument. It does not identify which bucket overflows, and fewer objects than total capacity do not guarantee that a particular assignment avoids overflow. Existence of a feasible assignment and behaviour of a chosen allocation are separate questions.

Choose the easiest justified count. For a union with a small overlap, subtract the intersection. For at-least-one events, inspect the none-event complement. For impossibility or forced repetition, compare occupancy with capacity. Naming what a calculation counts and checking its boundaries often reveals a mistaken model sooner than doing larger arithmetic.

A finite sample space $\Omega$ contains all outcomes of the model. An event E is a subset of it. Under a uniform model assigning equal probability $1/|\Omega|$ to each outcome, $\Pr(E)=|E|/|\Omega|$. This familiar ratio is conditional on equal likelihood. Merely knowing an outcome set is finite does not assign probabilities to its members.

For unequal probabilities, give nonnegative weights $p_\omega$ summing to one and calculate $\Pr(E)=\sum_{\omega\in E}p_\omega$. A deterministic rule is an extreme example assigning probability one to one outcome and zero to the rest. Counting how many possible outcomes exist cannot distinguish that rule from a uniform random choice; the sampling mechanism must be part of the model.

For k named items independently choosing uniformly among m buckets, with $0\le k\le m$, no-collision probability is $\prod_{i=0}^{k-1}(m-i)/m$. Its complement gives collision probability. At k=0 the empty product is one, so collision probability is zero. For k>m collision is guaranteed by pigeonhole, independent of uniformity. A real hash function applied to a particular fixed dataset may not behave like independent uniform choices, so the formula is a model calculation, not an automatic description of every implementation.

Independence matters in making all ordered triples equally likely: each complete tuple receives the product of its stage probabilities, here $(1/4)^3$. If all items are forced to use the same randomly chosen bucket, each individual choice is uniform but the choices are dependent and collision is certain for three items. Uniform marginals alone do not supply the independent-tuple model.

Collapsing representations can also destroy uniformity. Choose an unordered pair of named positions from three positions labelled A,A,B uniformly. There are three equally likely position pairs. One produces AA and two produce AB, so the two observed label outcomes have probabilities 1/3 and 2/3. Treating the observed set {AA,AB} as uniform would give the wrong answer. The mapping from original outcomes to observations preserves probability by summing all preimage weights.

Simulation samples the declared mechanism and reports observed frequency. It can check a prediction and expose implementation mistakes; its finite frequency need not equal the exact probability. A fixed random seed helps reproduce a particular run, but does not make the sample a mathematical enumeration. Later modules develop sampling error and concentration. Here, report exact count, model probability, and sampled fraction as distinct quantities.

The small collision lab enumerates all 64 tuples, then samples ten thousand independent trials under the same four-bucket model. Changing bucket weights, correlations, or the definition of a collision changes the event or mechanism and requires a new calculation. A graph that looks close to the formula is not an explanation of why the model applies. State the assumptions before comparing numbers.

Counting foundations support search-space estimates, collision analysis, dataset splits, and finite uncertainty. Their common habit is to define the outcome set before calculating. The probability extension adds another habit: describe how outcomes are selected before turning counts into chances. These two declarations are the essential exit skills of this module.

Use Python 3.11 or later with no packages; see the primer. itertools constructs finite sequences and subsets, math.comb supplies an exact integer reference, and Fraction retains exact probabilities. Explain the outcome model before running. Each lab receives ten explanation points: prediction 3, count/model interpretation 4, fault or variation analysis 3.

Forty minutes: predict the binary-string count, six ordered pairs, three unordered subsets, and the five-task allocation count. Run the script and identify what makes outcomes distinct in each line. Explain the zero-selection case. Change the selection from two named positions to an unordered pair without replacement and justify division by two. The three-from-ten enumeration confirms the worked 120 and 720 counts without replacing their derivations.

Download lab1_selections.py

"""Count ordered, unordered, and repeated choices over small explicit domains."""
from itertools import combinations, permutations, product
from math import comb, factorial


def main():
    binary = ["".join(bits) for bits in product("01", repeat=4)]
    assert len(binary) == 2 ** 4
    print("Length-four binary strings:", len(binary))
    print("Ordered two from ABC:", ["".join(p) for p in permutations("ABC", 2)])
    print("Unordered two from ABC:", ["".join(p) for p in combinations("ABC", 2)])
    for n, r in ((3, 2), (5, 0), (5, 3), (10, 3)):
        ordered = len(list(permutations(range(n), r)))
        unordered = len(list(combinations(range(n), r)))
        assert ordered == factorial(n) // factorial(n - r)
        assert unordered == comb(n, r)
        print(f"n={n}, r={r}: ordered={ordered}, unordered={unordered}")
    allocations = [(a, b, 5 - a - b) for a in range(6) for b in range(6 - a)]
    assert len(allocations) == comb(7, 2)
    print("Five identical tasks across three named workers:", len(allocations))
    print("First five allocations:", allocations[:5])


if __name__ == "__main__":
    main()

Length-four binary strings: 16
Ordered two from ABC: ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']
Unordered two from ABC: ['AB', 'AC', 'BC']
n=3, r=2: ordered=6, unordered=3
n=5, r=0: ordered=1, unordered=1
n=5, r=3: ordered=60, unordered=10
n=10, r=3: ordered=720, unordered=120
Five identical tasks across three named workers: 21
First five allocations: [(0, 0, 5), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 4, 1)]

Forty minutes, after Section 6: predict 64 tuples, 40 collision tuples, and probability 5/8. Run and compare the sampled fraction with the exact count. The seed reproduces the sample; it is not a proof that the frequency must equal 5/8. Change to five items and four buckets: no-collision count must be zero and collision guaranteed. Update the no-collision calculation for the changed model rather than retaining the three-item expression. Discuss why a correlated choice mechanism would invalidate the uniform-independent formula.

Download lab2_collisions.py

"""Uniform independent bucket choices: exact enumeration and a seeded sample."""
from fractions import Fraction
from itertools import product
from random import Random


def main():
    buckets, items = 4, 3
    outcomes = list(product(range(buckets), repeat=items))
    collisions = sum(len(set(outcome)) < items for outcome in outcomes)
    exact = Fraction(collisions, len(outcomes))
    no_collision_count = buckets * (buckets - 1) * (buckets - 2)
    assert exact == 1 - Fraction(no_collision_count, buckets ** items)
    print("Model: 3 named items choose independently and uniformly among 4 buckets.")
    print("Total outcomes:", len(outcomes), "collision outcomes:", collisions)
    print("Exact probability:", exact, "=", float(exact))
    rng = Random(2026)
    trials = 10000
    observed = 0
    for _ in range(trials):
        outcome = [rng.randrange(buckets) for _ in range(items)]
        observed += len(set(outcome)) < items
    estimate = observed / trials
    print(f"Seed=2026, trials={trials}, observed collision fraction={estimate:.4f}")
    print("A sampled fraction is not the exact probability or a collision guarantee.")


if __name__ == "__main__":
    main()

Model: 3 named items choose independently and uniformly among 4 buckets.
Total outcomes: 64 collision outcomes: 40
Exact probability: 5/8 = 0.625
Seed=2026, trials=10000, observed collision fraction=0.6188
A sampled fraction is not the exact probability or a collision guarantee.

Forty minutes: predict the full label strings and pair multiplicities for named positions labelled A,A,B. Explain why full arrangement division by two works while giving each observed pair probability one half does not. Run, preserve both probabilities, and describe the mapping from the three equally likely position pairs to two label outcomes. As a variation use labels A,B,C, where all pair observations have the same weight because the mapping no longer merges distinct position pairs.

Download lab3_repeated_labels.py

"""Distinguish named positions from repeated labels and preserve sampling weights."""
from collections import Counter
from fractions import Fraction
from itertools import combinations, permutations
from math import factorial


def main():
    labels = ("A", "A", "B")
    raw = list(permutations(labels))
    unique = sorted({"".join(outcome) for outcome in raw})
    assert len(raw) == 6 and len(unique) == factorial(3) // factorial(2)
    print("Named-position permutations:", len(raw))
    print("Distinct label strings:", unique, "count=", len(unique))
    selected = Counter("".join(sorted(pair)) for pair in combinations(labels, 2))
    print("Uniform pair of named positions; label multiplicities:", dict(sorted(selected.items())))
    total = sum(selected.values())
    for outcome, count in sorted(selected.items()):
        print(" ", outcome, "probability=", Fraction(count, total))
    print("Two possible label outcomes are not automatically equally likely.")
    print("Repair the count by defining whether positions, records, or labels are distinct.")


if __name__ == "__main__":
    main()

Named-position permutations: 6
Distinct label strings: ['AAB', 'ABA', 'BAA'] count= 3
Uniform pair of named positions; label multiplicities: {'AA': 1, 'AB': 2}
  AA probability= 1/3
  AB probability= 2/3
Two possible label outcomes are not automatically equally likely.
Repair the count by defining whether positions, records, or labels are distinct.

Exercises 1–12 take 110 minutes and earn five points each. Two extensions add 25 minutes. Give the outcome definition and assumptions before the arithmetic; a correct number for the wrong model does not earn full credit.

Nine choices are automatic; the written model explanation supplies the remaining point after review. Read each explanation as a reminder of the assumptions behind a count.

Required, 15 minutes: in the textbook linked by MIT Mathematics for Computer Science, read the product, sum, and subset-counting discussions. For one example, specify whether order and repetition matter before choosing a formula.

Required, 20 minutes: read the inclusion–exclusion and elementary finite-probability introductions. Identify where equally likely outcomes are assumed. Re-explain an overlap correction by membership cases, and distinguish its count from a sampling probability.

Optional: compare the official itertools combinatoric iterators with their output order and replacement conventions, and inspect math.comb as an exact integer reference. The lesson’s examples, derivations, and figures are original.

Outcome definitions determine the count: choose disjoint alternatives, follow construction branches, or prove a bijection. Ordered choices, subsets, and multisets retain different distinctions. Inclusion–exclusion corrects overlap; complement counts the easier opposite case; pigeonhole proves a capacity guarantee. Probability adds weights, with count ratios justified only under uniformity.

Exit task: derive ordered and unordered three-from-ten counts, prove Pascal’s identity, count a constrained task allocation, and explain the independent collision model alongside a dependent counterexample. Use exercises 60, lab explanations 30, and quiz 10. State every modelling assumption before arithmetic and repair any failed distinction after feedback.

Module 06 studies sums, growth, and recurrences. Before it, explain why counting a search space does not by itself establish the operation count of a particular algorithm. Keep the finite-sum induction and product-rule argument ready: both will justify growth calculations.