# Chapter 9 notebook: Combinatorics: Counting Without Exhaustion **Goal:** Define the sample space before choosing a counting formula. **Start with:** Rules 9.1.3, 9.2.2, 9.2.3. Use a calculator or the optional Python lab. Programming is optional for the workbook; the Jupyter version requires a Python 3 kernel. All lab numbers are constructed practice inputs, not observed data. **Source:** [Finished Chapter 9](../skills/math-thumb-combinatorics/references/chapter.md) from *Mathematical Rules of Thumb*. Numbered rules, classifications, and the decision path come from the book. The lab, exercises, answer key, and worksheet prompts are companion additions. ## 1. Frame your decision Write a question in which an answer would change something you do. Gather: What makes outcomes distinct; whether order matters; replacement; capacities; identical versus distinct objects; symmetry action. - My question and intended decision: - Known inputs and units: - Required accuracy or threshold: - What I expect before calculating: - What I still need to find out: Use the lab as a worked starting point if you do not yet have your own problem. For notation or prerequisites, ask the chapter skill to explain only the concept blocking the next step. ## 2. Choose a route - **Can the answer be forced without enumeration?** Define boxes and try pigeonhole, or identify unrestricted binary membership. - **Are identical units being distributed?** Use stars and bars only when recipients are labeled and capacities are unlimited. - **Are several cases being combined?** Add disjoint alternatives, multiply staged choices, and subtract intersections when alternatives overlap. - **What makes outcomes distinct?** Decide whether order matters and whether rotation, reflection, or another symmetry identifies descriptions. - **Is a restriction awkward?** Count its complement, or design recurrence states that remember precisely what legal extension depends on. - **Is the object random?** Express the target count as indicators before trying to analyze dependencies. - **Is an identity the goal?** Define one incidence set and count it in two orders. - **Is the exact count enormous?** Use adjacent ratios, logarithms, or a regime-appropriate approximation to expose scale. - **Does the construction split recursively or add component sizes?** Look for Catalan structure or encode the components with a generating function. **Chapter-specific stop check:** Do not divide by a symmetry count unless every orbit has that size. Re-check independence of choices and capacity restrictions before multiplying. ## 3. Work the lab Choose three reviewers from eight people. A committee has C(8,3)=56 possibilities. Three distinct jobs assigned to different people have 8 × 7 × 6=336 possibilities. The ratio is 3!=6 because each committee has exactly six job assignments. State the outcome definition before using either answer. Predict the sign and scale before running the code. Then change one input and explain why the result moves. The code checks the constructed example; it does not prove the rule for every possible input. Code assertions may describe the example's chosen regime, so inspect them before changing that regime. ```python import math people, selected = 8, 3 assert 0 <= selected <= people committees = math.comb(people, selected) assignments = math.perm(people, selected) print(f"Committees: {committees}; distinct job assignments: {assignments}") assert assignments == committees*math.factorial(selected) ``` **My prediction, observed result, and explanation:** _Record your work here._ ## 4. Practise without the answers ### Exercise 1 Distribute five identical tokens among three labeled boxes with no capacity limits. **My approach, assumptions, calculation, and check:** _Write your attempt here._ ### Exercise 2 How many four-bit strings contain at least one 1? **My approach, assumptions, calculation, and check:** _Write your attempt here._ ### Exercise 3 Can you count binary necklaces of length four by dividing 16 strings by four rotations? **My approach, assumptions, calculation, and check:** _Write your attempt here._ **Coaching prompt:** “Use the Chapter 9 skill to help me with Exercise 2. Ask for my attempt, give one useful hint if I need it, and help me check the assumptions before showing the answer.” ## 5. Answer key and reasoning Read this after attempting the exercises, or use it immediately if you prefer a complete walkthrough. An answer is complete only when its assumptions and stopping point are clear. ### Answer 1 Stars and bars gives C(5+3-1,3-1)=C(7,2)=21 nonnegative allocations. ### Answer 2 Count the complement: 2^4-1=15. The only excluded string is 0000. ### Answer 3 No: orbit sizes differ. 0000 is fixed by all rotations, whereas 0001 has four distinct rotations. A valid orbit count must account for stabilizers; Burnside's count is (16+2+4+2)/4=6. ## 6. Build the complete chapter toolkit The new lab samples the chapter; the following checklist covers all 18 rules. Study one thematic group at a time. A large group can take several sessions. - **Counts That Stand on Their Own:** work with rules 9.1.1, 9.1.2, 9.1.3, 9.1.4, 9.1.5, 9.1.6. - **Decisions That Organize a Counting Workflow:** work with rules 9.2.1, 9.2.2, 9.2.3, 9.2.4, 9.2.5, 9.2.6. - **Scale and Pattern Recognition:** work with rules 9.3.1, 9.3.2, 9.3.3, 9.3.4, 9.3.5, 9.3.6. For each selected rule, read its equation, explanation, and worked use in the source. Reproduce that example; change one input; then change one assumption so the rule is no longer justified. Record the result and what check catches the failure. Historical examples remain labeled and qualified as in the source. Read each complete numbered profile in the [chapter reference](../skills/math-thumb-combinatorics/references/chapter.md) before applying it. The cues below abbreviate the graph metadata; they are not complete conditions. Change the status only after doing the practice described below. | Rule | Book role | First assumptions to inspect | Practice status | |---|---|---|---| | 9.1.1: Use the ceiling form of pigeonhole | Independent | finite objects and boxes; every object assigned to a box | new | | 9.1.2: Remember that an n-set has two to the n subsets | Independent | finite set of distinct elements; independent include exclude choices | new | | 9.1.3: Use stars and bars for identical items in labeled boxes | Independent | indistinguishable items; labeled boxes | new | | 9.1.4: Approximate choose n k by n to the k over k factorial | Independent | k fixed or much smaller than n; nonnegative integers | new | | 9.1.5: Subtract overlap after adding two sets | Independent | finite event or set family; pairwise intersections available | new | | 9.1.6: Divide by symmetry only when every orbit has the same size | Independent | uniform orbit size; finite group action or equivalent symmetry | new | | 9.2.1: Decide first between the sum and product principles | Workflow | disjoint alternative cases for sum; well defined sequential choices for product | new | | 9.2.2: Ask whether order changes the outcome | Workflow | finite distinct objects or adjusted multiplicities | new | | 9.2.3: Count the complement when the restriction is awkward | Workflow | finite universe or known total; desired and forbidden partition universe | new | | 9.2.4: Choose recurrence states that remember exactly what the future needs | Workflow | future behavior determined by state | new | | 9.2.5: Count with indicator variables and linearity | Workflow | well defined indicator events; finite sum or justified interchange | new | | 9.2.6: Prove identities by counting the same incidences twice | Workflow | same finite incidence set; both counts include equal multiplicity | new | | 9.3.1: Expect the largest binomial coefficient in the middle | Independent | fixed nonnegative integer n | new | | 9.3.2: Expect one binary-search step per bit of search space | Independent | roughly equal halving; successful monotone decision test | new | | 9.3.3: Estimate derangements by factorial over e | Independent | permutations of distinct objects; no fixed points | new | | 9.3.4: Estimate multinomial counts on the log scale | Independent | large counts; category proportions sum to one | new | | 9.3.5: Use generating functions to turn convolution into multiplication | Workflow | well defined formal or convergent series; correct indexing | new | | 9.3.6: Look for Catalan numbers in balanced recursive structures | Workflow | recursive two part structure; noncrossing or prefix constraint | new | For a completed row, record: **rule number / my new input / mathematical claim type / verified assumptions / calculation / check / valid use / rejected use / next step**. “Practised” means you worked an example. “Demonstrated” means you can explain a valid use, transfer it, and reject a misuse without the answer key. ## 7. Apply it to your own problem Return to your opening question. Choose the smallest rule set that can settle it. Use the book's independent/workflow/specialized classification separately from the claim type (exact, approximate, bound, diagnostic, or heuristic). - Selected rule number(s) and reason: - Assumptions that hold, fail, or remain uncertain: - Substitution with units: - Result and error, uncertainty, or bound: - Independent check or limiting case: - Decision this supports: - Stop here, do a named next calculation, or gather missing information: ## 8. Transfer and continue Useful nearby chapters: Chapter 8: number theory; Chapter 12: probability; Chapter 15: information theory. Bring the question, units, assumptions, result type, and uncertainty to the next chapter. Choose a bridge only when it supplies an operation you actually need. **Completion check:** Explain this chapter's lab in your own words; solve one changed-input exercise; reject one invalid use; and produce a decision record for your own problem. If one check fails, revisit that part of the chapter rather than marking every rule complete.