Day 53 — Counting in CS

Updated

July 30, 2026

Day 53 — Counting in CS

Stage V · concept day
Goal: Apply product/sum, \(P(n,k)\), \(\binom{n}{k}\), stars-and-bars, and IE to CS-shaped spaces: passwords, states, hashes, execution trees, bit constraints, protocol messages; reason about size via \(\log_2\).

Why this matters

Discrete math earns its keep when you can estimate how big a design space is before you build it. Security entropy, exhaustive test feasibility, hash collision culture, and protocol versioning all reduce to counting. Today is applied fluency—no new hard theorems; tight modeling.

Theory

Modeling checklist

For any CS counting problem:

  1. Name the object (string, function, path, assignment, packet).
  2. Alphabet / domain / codomain sizes.
  3. Order matter? Repetition allowed? Distinguability?
  4. Constraints: forbidden patterns, at-least-one, injectivity, ranges.
  5. Method: product, sum/cases, complement, \(P\)/\(\binom{n}{k}\), stars-bars, IE.
  6. Sanity: small parameters; \(\log_2\) of huge answers for “bits of entropy.”

Passwords and keys

  • Alphabet \(\Sigma\), length \(k\), rep OK: \(|\Sigma|^k\).
  • No repetition: \(P(|\Sigma|,k)\).
  • Policy “at least one digit”: \(|\Sigma|^k - |\Sigma_{\text{letters}}|^k\).
  • Entropy bits (uniform random password): \(\log_2\) of the search space size.
  • Rough: \(36^8\) ≈ \(\log_2(36^8)=8\log_2 36\approx 8\cdot 5.17\approx 41.4\) bits.

State spaces

A system with independent fields \(f_i\in S_i\) has state space \(\prod |S_i|\) (product type).
Illegal combinations: subtract or IE.
Feature flags: \(2^n\) configurations; with mutual exclusions, less.

Hash buckets

\(n\) distinct keys, \(k\) buckets:

  • All assignments: \(k^n\) (functions).
  • Every bucket nonempty: surjections \(k!\,S(n,k)\).
  • Collision existence: PHP when \(n>k\); counts of collision patterns more refined.
  • Birthday culture: collision probability ~ \(1-e^{-n(n-1)/(2k)}\)—not pure counting, but \(\binom{n}{2}/k\) approx.

Trees of executions

A nondeterministic program with branching factor \(b\) and depth \(d\): up to \(b^d\) leaves (execution traces).
Recursive algorithms: recurrence for number of call-tree nodes (Day 54–55).
Test paths in a CFG: path counting ≠ node counting; loops make infinite paths—bound unwind depth.

Language of bit constraints

Length-\(n\) bit-strings:

Constraint Count
Free \(2^n\)
Exactly \(k\) ones \(\binom{n}{k}\)
No two consecutive ones Fibonacci (Day 54)
Starts with 10 or ends with 11 IE or cases
Parity even \(2^{n-1}\)

Protocol message spaces

A message format: header fields with fixed widths + payload.
Example: version 3 bits, type 5 bits, length 8 bits, flags 4 bits → \(2^{3+5+8+4}\) syntactic messages (semantics may forbid many).
TLV / enum tags: sum over cases (sum rule on message type).

Asymptotic size and \(\log_2\)

When \(N\) is huge, report \(\log_2 N\) (bits) or \(\log_{10} N\) (digits).
Stirling: \(\log_2(n!)\approx n\log_2 n - n\log_2 e\) for permutation spaces.
Compare \(n^k\) vs \(k^n\) vs \(n!\) growth for algorithm design (Stage VIII prep).

Function spaces (summary table)

Maps Count
All \(A\to B\) \(\|B\|^{\|A\|}\)
Injections \(P(\|B\|,\|A\|)\)
Surjections IE form
Bijections \(n!\) if equal size
Partial functions \((\|B\|+1)^{\|A\|}\) (image or undefined)

Worked examples

Example 1 — Password entropy

8-char passwords from [a-zA-Z0-9]: \(62^8\).
\(\log_2(62^8)=8\log_2 62\approx 8\cdot 5.95\approx 47.6\) bits.
If only lowercase: \(26^8\), \(\approx 37.6\) bits—about 10 bits weaker.

Example 2 — PIN policies

4-digit PIN: \(10^4=10000\).
Distinct digits: \(P(10,4)=5040\).
No leading zero as “number”: \(9\cdot 9\cdot 8\cdot 7=4536\) for distinct.

Example 3 — Feature flags with exclusion

10 flags, but flags 1 and 2 cannot both be true: total \(2^{10}=1024\); both true: \(2^8=256\); valid \(1024-256=768\).

Example 4 — IPv4 addresses

\(2^{32}\) theoretical; private ranges etc. are subsets. Count \(10.0.0.0/8\): \(2^{24}\).

Example 5 — Hash assignments

100 keys, 10 buckets: \(10^{100}\) total; surjective: \(10!\,S(100,10)\) (astronomical; existence of empty buckets almost sure by occupancy theory).

Example 6 — UUID-like

122 random bits (UUID v4 culture): \(2^{122}\) possibilities—\(\log_2\) is the point.

Example 7 — Execution tree

Binary recursive procedure, depth 10 full tree: \(2^{10}=1024\) leaves; \(2^{11}-1\) nodes if complete binary.

Example 8 — Bit constraints

Length 8 with no three consecutive 1s—harder (recurrence later). Length 8 exactly 4 ones: \(\binom{8}{4}=70\).

Example 9 — Protocol sum rule

Messages of type A (payload 4 bits) or type B (payload 8 bits), 1-bit type tag: \(2^4+2^8=16+256=272\) if tag distinguishes; if tag+payload free without structure, different.

Example 10 — API keys

sk_ + 24 chars from 58-char alphabet (Base58 culture): \(58^{24}\) keys.

Example 11 — Test matrix

3 browsers × 4 OSes × 2 modes = 24 configurations (product). If one browser-OS pair unsupported: \(24-2=22\) if 2 modes still apply.

Example 12 — Semantic versioning space

major.minor.patch with major \(0..9\), minor \(0..99\), patch \(0..99\): \(10\cdot 100\cdot 100=100{,}000\) version triples.

Example 13 — Partial functions

Functions from 5 endpoints to 3 handlers or “unhandled”: \(4^5\).

Example 14 — Log compare

Which larger: \(20!\) or \(2^{60}\)? \(\log_2(20!)\approx \sum_{k=1}^{20}\log_2 k \approx 61.1\) roughly—comparable to \(2^{60}\). (Actual \(20!\approx 2.43\times 10^{18}\), \(2^{60}\approx 1.15\times 10^{18}\).)

Example 15 — Restricted passwords IE

Length 6 from 62 chars, must include ≥1 digit AND ≥1 letter:
total \(62^6\) − pure digits \(10^6\) − pure letters \(52^6\) + empty? (can’t be both pure digit and pure letter unless empty set): \(+0\).
Wait pure digit ∩ pure letter = empty for length 6. So \(62^6-10^6-52^6\).

Exercises

  1. Entropy bits of 12-char lowercase passwords.
  2. 6-char alphanumeric, at least one digit—expression.
  3. State space: 4 enums of sizes 3,3,5,2; one forbidden combo—count.
  4. \(n\) bits, Hamming weight ≤ 2: sum of binomials.
  5. Number of injections from 8 users to 100 user-IDs.
  6. Surjective assignment of 12 shards to 4 racks.
  7. Binary strings length 10 starting with 1 or containing 00 as suffix—careful.
  8. Estimate \(\log_2(52!)\) for a shuffled deck (approx OK).
  9. Message: 16-bit header free + 3-bit type; for types 0,1 payload 8 bits; type 2–7 payload 0—count valid messages.
  10. Feature flags 12 with at most 3 true: \(\sum_{k=0}^{3}\binom{12}{k}\).
  11. Compare \(2^{40}\) vs \(3^{25}\) via logs.
  12. CFG: 3 branches then 2 then 2—trace count if no merge.
  13. Hash: 365 days, 30 people—birthday count culture \(\binom{30}{2}/365\) approx expected colliding pairs.
  14. IPv6 address bits and \(\log_2\).
  15. Partial maps \([n]\to[m]\) count.
  16. Passwords length ≤ 4 from 26 letters (sum rule on length).
  17. Number of \(n\times n\) binary matrices; with all row sums 1 (permutation matrices if also cols).
  18. CS: count distinct git short hashes if 7 hex chars: \(16^7\).
  19. Protocol versioning: 2-bit major, 4-bit minor—how many?
  20. At least one of three error flags set in a byte of flags (8 flags)—set up.
  21. Why exhaustive test of \(2^{64}\) states is infeasible—time argument.
  22. Derangement secret santa for 10 engineers.
  23. Multiset of 5 config options from 3 modes (stars-bars).
  24. Challenge: count valid UTF-8 code units patterns lite—or count 4-byte sequences with high bit constraints you invent.
  25. Write a one-page “threat model entropy” for a 6-digit OTP vs 8-char base32 secret.

CS connection

This is the CS connection day:

  • Security: password/key space size.
  • Testing: combinatorial coverage.
  • Distributed systems: assignment and partition counts.
  • Networking: address and header spaces.
  • Languages: string constraints and automata-accepted counts (awareness).

Common pitfalls

Pitfall What to do instead
Counting syntax not semantics State whether invalid messages excluded
Entropy as character count Use \(\log_2\) of space
Birthday as PHP certainty PHP vs probability
Forgetting policies that shrink space Complement / IE
\(k^n\) vs \(n^k\) mix-up Domain→codomain: \(\|B\|^{\|A\|}\)

Checkpoint

  • Password + entropy calculation cold
  • Function space table from memory
  • One IE policy password
  • One protocol product/sum
  • \(\log_2\) comparison of two huge numbers
  • Exercises 1–15
  • Modeling checklist used on a system you know

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. \(12\log_2 26\approx 56.4\) bits.
  2. \(62^6-52^6\).
  3. \(\binom{n}{0}+\binom{n}{1}+\binom{n}{2}\).
  4. \(P(100,8)\).
  5. Stirling \(\approx 52\ln 52-52\) nats → convert; ~225.7 bits.
  6. \(1+12+66+220=299\).
  7. \(26+26^2+26^3+26^4\).
  8. \(16^7=268{,}435{,}456\).
  9. \(!10=1{,}334{,}961\).

Deepening notes

Entropy quick reference

\[ H_{\text{bits}}=\log_2|\text{search space}| \]

for uniform random secrets. Real user-chosen passwords are far from uniform—counts give upper bounds on attacker work only under uniform assumptions.

Occupancy and empty buckets

Throw \(n\) balls into \(k\) bins: expected empty bins \(k(1-1/k)^n\approx k e^{-n/k}\). Surjection count is exact but huge; occupancy asymptotics guide system design.

Protocol grammar counting

If messages are a disjoint union of formats \(F_i\) each a product of field alphabets, total syntactic messages \(=\sum_i\prod_j |A_{ij}|\). Semantic validity is a subset—state which you count.

CFG path explosion

A loop with \(b\) branches body and up to \(L\) iterations can contribute \(\sim b^L\) paths. Bounded model checking and coverage metrics exist because full path enumeration dies.

Extra drills

D1. Entropy of 6-digit OTP vs 128-bit key.
D2. \(2^{48}\) vs \(10^{14}\) via logs.
D3. Config: 3 enums (5,5,5) with 10 forbidden triples.
D4. Injections users→IDs: 50 users, 1000 IDs.
D5. Bit-strings length 12 weight ≤3.
D6. State machine 4 registers 2-bit each: state count.
D7. Git short hash 8 hex: collision PHP threshold.
D8. Partial functions \([8]\to[3]\).

Modeling card (carry forward)

  1. Name object 2. Alphabet 3. Order/rep 4. Constraints 5. Method 6. \(\log_2\) sanity.

Worked case study — API key design

Spec: live_ prefix + 24 chars from Base58 (58 symbols).
Space: \(58^{24}\).
Bits: \(24\log_2 58\approx 24\cdot 5.858\approx 140.6\) bits.
If no character repeats: \(P(58,24)\)—slightly smaller, harder to type-check.
Policy “must include digit”: Base58 includes digits; if separate classes, use complement.

Worked case study — feature rollout matrix

Browsers 4 × OS 3 × locales 5 = 60 configs.
Drop IE on Linux (1 browser × 1 OS × 5 locales = 5): 55.
Product then subtract—document the illegal rectangle.

Comparison table growth

Expression \(\log_2\) scale
\(2^n\) \(n\)
\(n!\) \(\sim n\log_2 n\)
\(n^n\) \(n\log_2 n\)
\(C_n\) \(\sim 2n - \tfrac32\log_2 n\) culture

Exam drill block

E1. Entropy bits of a 16-character password from 62 symbols (uniform).
E2. Compare \(2^{40}\) and \(10^{12}\) via \(\log_{10}\) or \(\log_2\).
E3. Config space: 5 booleans × enum of 4 × enum of 3, minus 6 illegal pairs.
E4. Number of injections from 8 users to 1000 IDs: \(P(1000,8)\).
E5. Bit-strings length 16 with weight ≤2.
E6. State machine: 3 registers, each 4 states—\(|S|\).
E7. Short hash 6 hex chars: birthday threshold \(\sim\sqrt{\pi 16^6/2}\) order-of-magnitude.
E8. Partial functions \([n]\to[k]\): count \((k+1)^n\).
E9. True/false: (i) \(\log_2\) of space is bits of uniform secret (ii) path explosion is always \(n!\) (iii) occupancy uses \(k^n\) as total throws.
E10. Protocol: 8-bit type field; if type \(<128\) payload is 16 bytes else 4 bytes—total message count.

Mini solutions

E1. \(16\log_2 62\approx 16\cdot 5.95\approx 95.3\) bits.
E2. \(2^{40}\approx 1.1\cdot 10^{12}\)—same order.
E3. \(2^5\cdot 4\cdot 3-6=384-6=378\) if illegal are single configs.
E5. \(\binom{16}{0}+\binom{16}{1}+\binom{16}{2}=1+16+120=137\).
E6. \(4^3=64\).
E8. Yes \((k+1)^n\) if “undefined” is extra image.
E9. T; F; T (each ball chooses a bin).
E10. \(128\cdot 2^{128}+128\cdot 2^{32}\) if payload is free bits—state bit model carefully.

Modeling card (reprise)

  1. Name the object (password, state, path, key).
  2. Alphabet / component sizes.
  3. Order? Repetition? Constraints?
  4. Product / sum / complement / IE / \(P(n,k)\) / \(\binom{n}{k}\).
  5. Sanity: \(\log_2\) and small-\(n\) check.

Synthesis

CS counting converts specs into search spaces: passwords and keys (entropy), configs (product − forbidden), hashes (birthday), programs (path trees), protocols (sum of products). Prefer exact formulas; use \(\log_2\) for scale. Uniformity assumptions are explicit—real systems often fall short.

S1. Design a token: prefix + Base64 body; report bits.
S2. Count feature-flag assignments with “at most 3 true.”
S3. Cold: \(62^8\) bits; surjective hash of 5 keys into 3 buckets.

Tomorrow

Day 54 — Recurrences intro: definitions, Fibonacci, Hanoi, merge-sort style setup, base cases.