Discrete Structures II

Counting rules and combinatorial models

Before choosing a formula, identify the objects being counted and when two outcomes are considered different. The product rule combines sequential choices; the sum rule combines disjoint alternatives. A bijection proves equal counts by pairing objects uniquely in both directions. Choosing k distinct items from n without order gives a binomial coefficient; ordering those choices introduces additional arrangements. Repeated items require removing overcounting carefully. For nonnegative integer solutions to x1 + x2 + x3 = 5, stars and bars gives choose(7,2) = 21; requiring positive values changes the model.

References: Pat Morin — COMP 2804 public course page · Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability

Inclusion-exclusion and pigeonhole reasoning

Adding set sizes counts intersections more than once. For two sets, subtract the intersection once; for more sets, alternate signs according to intersection size. Counting a complement can be simpler than counting the target directly. The pigeonhole principle proves that distributing more than m objects into m boxes forces a shared box. To use it effectively, define the boxes so that sharing one implies the desired property. Generalized versions guarantee a box with at least the ceiling of n/m objects. Such arguments prove existence without necessarily constructing a particular witness.

References: Pat Morin — COMP 2804 public course page · Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability

Recurrences and recursive counting

A recurrence expresses a quantity using smaller instances, but it also needs sufficient initial conditions. Count binary strings of length n with no consecutive ones by splitting on the first symbol. Strings starting with zero leave a valid length n-1 suffix; strings starting with one must continue with zero, leaving length n-2. Thus, for n >= 2, a_n = a_(n-1) + a_(n-2), with a_0 = 1 and a_1 = 2. The empty string counts as one valid construction. Verify that cases are disjoint and cover every valid object before accepting the recurrence.

References: Pat Morin — COMP 2804 public course page · Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability

Probability spaces, conditioning, and independence

A probability model specifies outcomes and their probabilities; equally likely outcomes must be justified, not assumed. Conditional probability restricts attention to an observed event: P(A given B) = P(A and B)/P(B) when P(B) is positive. Independence means knowing one event does not change the other’s probability. Disjoint events with positive probability are not independent. Bayes’ rule reverses a conditioning relationship while accounting for base rates. State the sampling procedure precisely, because selecting a family and selecting a child can create different probability spaces.

References: Pat Morin — COMP 2804 public course page · Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability

Random variables, indicators, and a worked expectation

A random variable assigns a number to each outcome. Expected value is a probability-weighted average and need not be a possible observed value. Indicator variables simplify counting: define I_i as one when event i occurs and zero otherwise, then sum them. Linearity of expectation does not require independence. In a random permutation of n items, let I_i indicate that item i remains in its original position. Each has expectation 1/n, so the expected number of fixed points is n times 1/n = 1, even though those indicators are dependent.

References: Pat Morin — COMP 2804 public course page · Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability

Randomized algorithms and distributional intuition

Distinguish randomness in an algorithm from randomness assumed about its input. Randomized quicksort has good expected comparison cost because pivot choices distribute the recursive partitions; a particular run can still be poor. A geometric variable models waiting until the first success under independent trials with constant success probability. Coupon collection becomes slower near completion because most draws repeat known types. In probabilistic existence proofs, show that an object sampled from a defined distribution has positive probability of satisfying the target property. Keep expected performance separate from a guarantee on every outcome.

References: Pat Morin — COMP 2804 public course page · Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Pat Morin — COMP 2804 public course page ↗Course scope and public lectures · Fall 2026 page; historical video supplements
• Michiel Smid — Discrete Structures for Computer Science: Counting, Recursion, and Probability ↗Open textbook · 2019