Exercises: The Basics of Counting

DataField.Dev

Exercises: The Basics of Counting

These run from mechanical warm-ups to modeling, code, and full proofs. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek. Every counting answer should come with a one-line reason — which rule, and why its proviso holds. A number with no justification earns no credit, because the whole subject is the modeling, not the arithmetic.

Part A — Warm-ups (⭐)

15.1 † Without listing, how many 5-digit PINs (digits 0-9, repeats allowed) are there? State the rule you used and why its proviso holds.

15.2 A function takes two boolean flags and one argument that is one of 6 enum values. How many distinct input combinations are there? Is exhaustive testing feasible?

15.3 † How many bytes (8 bits, each 0 or 1) are there? How many distinct values can a 16-bit register hold? Write both as a power of 2 and as a decimal number.

15.4 A vehicle license plate is 2 uppercase letters followed by 5 digits. How many plates are possible? Which rule, and what is the "regardless of earlier steps" condition here?

15.5 † How many integers from 1 to 200 are divisible by 7? (Use the floor formula from §15.4.)

15.6 A drink order is either one of 9 coffees or one of 4 teas, and no drink is both. How many single-drink orders are possible? Name the rule and verify its proviso in one phrase.

Part B — Computation (⭐⭐)

15.7 † How many strings of length 7 over the 26 lowercase letters use all distinct letters? Write the descending product explicitly, and explain why the product rule still applies even though the pool of available letters shrinks at each step.

15.8 A password policy requires a length of exactly 4, 5, or 6 over the 26 lowercase letters. How many passwords does the policy allow? Identify the "sum of products" structure.

15.9 † How many integers from 1 to 300 are divisible by 4 or by 6? (Careful: 4 and 6 are not coprime — what is the overlap divisor?)

15.10 How many integers from 1 to 1000 are divisible by 2, 5, or 7? Lay out the three singles, three pairs, and one triple before combining with the alternating signs.

15.11 † How many 6-character strings over the 36 symbols {lowercase letters, digits} contain at least one digit? Use the subtraction principle and show the universe, the complement, and the difference.

15.12 In how many distinct ways can 7 people be seated around a circular table, counting two seatings as the same when one is a rotation of the other? State the over-count factor and confirm it is uniform.

15.13 A 4-character "tag" is built from the 26 lowercase letters, but the first character must be a vowel (a, e, i, o, u) and the last must be a consonant. How many tags are possible? Which positions are independent, and which constrain the count?

Part C — Prove it (⭐⭐, scaffolded)

15.14 † (Fill in the missing steps.) Prove the two-set inclusion-exclusion formula $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$ by partitioning. Fill each blank.

The set $A \cup B$ is the union of three pairwise-disjoint pieces: $A \setminus B$, $\underline{\hphantom{xxxxx}}$, and $A \cap B$. By the sum rule, $\lvert A \cup B \rvert = \lvert A \setminus B \rvert + \underline{\hphantom{xxxxx}} + \lvert A \cap B \rvert.$
The set $A$ partitions into $A \setminus B$ and $A \cap B$, so $\lvert A \setminus B \rvert = \underline{\hphantom{xxxxx}}$. Symmetrically $\lvert B \setminus A \rvert = \underline{\hphantom{xxxxx}}$.
Substituting both into the sum-rule line and simplifying gives $\lvert A \cup B \rvert = \underline{\hphantom{xxxxxxxxx}}$, as claimed. $\blacksquare$

15.15 (Fill in the missing steps.) Prove the division rule: if $f \colon S \to T$ is onto and every $t \in T$ has exactly $d$ preimages, then $\lvert T \rvert = \lvert S \rvert / d$. Complete the argument.

The preimage sets $\{f^{-1}(t) \mid t \in T\}$ are pairwise _ (because each element of $S$ maps to exactly one $t$) and their union is _ (because $f$ is a function defined on all of $S$), so they ____ the set $S$.
By the sum rule, $\lvert S \rvert = \sum_{t \in T} \lvert f^{-1}(t) \rvert = \sum_{t \in T} \underline{\hphantom{xx}} = \underline{\hphantom{xxxxx}}$.
Dividing both sides by $d$ gives the result. $\blacksquare$

15.16 † Prove that the sum rule is the special case of two-set inclusion-exclusion in which $A \cap B = \emptyset$. (One or two lines: start from the inclusion-exclusion formula and apply the hypothesis.)

15.17 Prove that for finite sets $A$ and $B$, the number of elements in exactly one of $A$, $B$ (the symmetric difference) is $\lvert A \rvert + \lvert B \rvert - 2\lvert A \cap B \rvert$. (Start from the two-set formula and remove the overlap a second time. This previews §15.6's complement habit.)

Part D — Find the error (⭐⭐)

Each argument below reaches a wrong number. State precisely which rule was misapplied and which proviso was violated, then give the correct count.

15.18 † Claim: "The number of 2-letter strings over {a, …, z} whose two letters are in strict alphabetical order (first letter earlier than second) is $26 \times 26 = 676$." "Reasoning": "There are 26 choices for the first letter and 26 for the second, so by the product rule the answer is $26^2$." — Find the flaw and explain why the product rule does not apply.

15.19 Claim: "How many integers from 1 to 100 are divisible by 4 or by 6? Answer: $\lfloor 100/4 \rfloor + \lfloor 100/6 \rfloor = 25 + 16 = 41$, by the sum rule." — Find the flaw and give the correct count.

15.20 † Claim: "How many ways can 5 distinct beads be arranged on a bracelet, where rotations and flips are considered the same? Answer: $5! / (2 \cdot 5) = 120/10 = 12$, by the division rule." A grader marks this not fully justified. Explain what the division rule requires that this argument never checks, and name the situation in which the simple division rule can fail. (You are not asked to compute the true bracelet count.)

15.21 Claim: "How many 8-character lowercase passwords contain at least one vowel? Answer: pick one position to hold a vowel (8 ways), put a vowel there (5 ways), and fill the other 7 positions freely ($26^7$ ways): $8 \times 5 \times 26^7$." — This number is far too big. Identify the over-counting error and state the correct (complement-based) method.

Part E — Model it (⭐⭐⭐)

Translate each real scenario into discrete-math objects (sets, sequences of choices, a universe) and then count. Show the model before the arithmetic.

15.22 † (Test-space sizing.) A configuration object has: a log level (one of 5), a region (one of 4), three independent boolean feature flags, and a timeout that is an integer from 0 to 30 inclusive. Model the configuration space as a product, compute its size, and decide whether exhaustive unit testing is feasible. Then state what happens to the size if the timeout becomes a full 32-bit integer, and what that means for your testing strategy.

15.23 (Keyspace + security argument.) A system uses 9-character passwords over the 95 printable ASCII characters. (a) Model the keyspace and compute its size. (b) At $10^9$ guesses per second, about how long is a worst-case brute-force search? (c) The team proposes requiring at least one of the 10 digits. Model the new keyspace using the subtraction principle, compute it, and state in one sentence whether the policy made brute force harder or easier — and why that is a subtle trade-off.

15.24 † (Collision space, sets up Ch.17.) A hash function maps inputs to one of $2^{32}$ buckets. Treat "a sequence of $k$ stored items, each landing in some bucket" as a sequence of independent choices. (a) How many distinct bucket-assignment sequences are there for $k$ items? (b) How many of those sequences have all distinct buckets (no collision), assuming $k \le 2^{32}$? Express the second count as a descending product $P(n, k)$-style expression with $n = 2^{32}$. (You will turn this into a probability of collision in Chapter 17 — here, just the counts.)

15.25 (State-space sizing.) A small protocol's connection is described by: a state (one of 6: e.g. CLOSED, LISTEN, SYN_SENT, SYN_RCVD, ESTABLISHED, CLOSED_WAIT), a 1-byte sequence-number window position (256 values), and two independent boolean flags (urgent, keepalive). (a) Model and count the total number of distinct connection descriptors. (b) Is exhaustive model-checking of all descriptors feasible? (c) If you added a 16-bit field, what would the new size be, and would your answer to (b) change?

Part F — Implement it & Conjecture and test (⭐⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, matching the book's convention. Reference solutions live in code/exercise-solutions.py.

15.26 † (Implement it.) Write keyspace(alphabet_size, length) returning the number of strings of the given length over an alphabet of that size, using the product rule. Then write one line that prints the size of the 10-character keyspace over the 95 printable ASCII characters. Add the hand-derived # Expected output:.

15.27 (Implement it.) Write at_least_one(universe_alpha, forbidden_alpha, length) that returns the number of length-length strings over an alphabet of size universe_alpha containing at least one character from a "required" sub-alphabet, where forbidden_alpha is the count of characters that are not in the required set. Use the subtraction principle: (all strings) − (strings avoiding the required set). Print the count of 6-character lowercase strings with at least one vowel (universe 26, forbidden 21). Include the # Expected output:.

15.28 † (Conjecture and test, then prove.) For the integers $1$ to $N$, let $g(N)$ be the count divisible by 2 or 3. Write a brute-force counter count_div_2_or_3(N) using a comprehension, and a formula version formula_div_2_or_3(N) using inclusion-exclusion with floors. Print both for $N = 30, 60, 100$. They should agree. Conjecture a closed form for $g(N)$ when $N$ is a multiple of 6, then prove it (hint: count exactly within one block of 6 consecutive integers and multiply).

15.29 (Conjecture and test, then prove.) Define $h(n) = $ the number of bit strings of length $n$ that contain no two consecutive 1s. Write a brute-force counter (generate all $2^n$ strings, filter) and print $h(n)$ for $n = 1, 2, 3, 4, 5$. You will get $2, 3, 5, 8, 13$. Conjecture which famous sequence this is and the recurrence it satisfies; state the recurrence $h(n) = \underline{\hphantom{xx}}$ and justify it by a sum rule case split on the last bit. (We solve such recurrences in Chapters 18-19; here, conjecture and justify the recurrence only.)

15.30 (Implement it.) Write incl_excl_3_sizes(a, b, c, ab, ac, bc, abc) taking the seven region counts (three singles, three pairwise intersections, one triple intersection) and returning $\lvert A \cup B \cup C \rvert$. Print the value for the divisible-by-2-3-5 example of §15.4 ($a,b,c = 50,33,20$; $ab,ac,bc = 16,10,6$; $abc = 3$). Include the # Expected output:.

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

15.31 † (Ch. 8 + 15.) Let $A$ and $B$ be finite sets with $\lvert A \rvert = m$, $\lvert B \rvert = n$. (a) Using the Cartesian product from Chapter 8, give $\lvert A \times B \rvert$ and name the counting rule that proves it. (b) How many elements are in the power set $\mathcal{P}(A)$? (Each element of $A$ is independently in or out of a subset — frame it as a product.)

15.32 (Ch. 9 + 15.) How many functions are there from a set of size $m$ to a set of size $n$? (Model each function as a sequence of $m$ independent choices — one output per input.) How many of them are injective, assuming $m \le n$? Connect the injective count to the descending product $P(n, m)$.

15.33 † (Ch. 11 + 15.) The descending product $26 \times 25 \times \cdots \times 19$ from §15.2 can be written with factorials as $\frac{26!}{18!}$. Using the factorial notation introduced in Chapter 11, write the general "$k$ ordered choices from $n$ without repetition" count as a ratio of factorials, and confirm it equals $n(n-1)\cdots(n-k+1)$.

15.34 (Ch. 14 + 15.) A brute-force routine that lists every 8-character lowercase password does $26^8$ units of work. (a) Express the cost of listing every length-$L$ password over an $a$-letter alphabet in big-O notation, in terms of $a$ and $L$. (b) Using Chapter 14's vocabulary, explain why this is "exponential in $L$" and why that single fact — not any cleverness — is what makes brute force infeasible. Tie it to §15.6's combinatorial-explosion remark.

15.35 (Ch. 12-13 + 15.) Recall a relation on a set $S$ is a subset of $S \times S$ (Chapter 12). (a) How many distinct binary relations are there on a set of size $n$? (Hint: a relation is any subset of the $n^2$-element set $S \times S$ — combine a product with the subset-counting idea of Exercise 15.31.) (b) How many of them are reflexive? (A reflexive relation must contain all $n$ diagonal pairs $(x, x)$; the other $n^2 - n$ pairs are free.)

15.36 (Deep Dive.) Conjecture the four-set inclusion-exclusion formula by extending the alternating pattern (add singles, subtract pairs, add triples, subtract the quadruple). Write it out in full for sets $A, B, C, D$, count how many terms of each sign appear, and connect the term counts to the row of Pascal's triangle you would expect (a preview of Chapter 16 and the general theorem of Chapter 17).

15.37 (Deep Dive.) A "derangement" of $n$ labeled items is an arrangement in which no item is in its original position. Using the subtraction principle and inclusion-exclusion on the "bad" events $A_i = $ "item $i$ is in its original position," set up (do not fully evaluate) the count of derangements of 3 items as (all arrangements) − $\lvert A_1 \cup A_2 \cup A_3 \rvert$, compute it by hand for $n = 3$, and verify by listing all $3! = 6$ arrangements. (Chapter 17 develops derangements in general; here, exercise the inclusion-exclusion machinery on a tiny case.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each count, the rubric rewards: the correct rule named, an explicit check of its proviso (independence for products, disjointness for sums, uniform over-count for division, a stated universe for complements), and the right arithmetic — in that order of importance.