Mathematical Rules of Thumb, illustrated reader · Chapter 9

09Combinatorics

Counting Without Exhaustion

4 demonstrations follow the chapter's rules. Choose a value, watch the figure and the numbers change, and check your prediction. Every choice is precomputed from the notebook calculations.

Ask the chapter skill

“Help me use Chapter 9 for my question. Choose a rule, check its assumptions, and show how the result changes when an input changes.”

Use math-thumb-combinatorics from the companion's skill package. The demonstrations below also work on their own.

Examples use constructed inputs or the book's own values, disclosed in each panel. A picture illustrates a rule; its assumptions set its scope.

1Demonstration 1 of 4

Choose whether order changes the outcome

What creates the factorial multiplier?

Compare committees with assignments to distinct jobs using the same eight people.

P(n,k)=(nk)k! P(n,k)=\binom nk k!

Selected people k. Distinct people, no replacement; all selected jobs are labeled and filled.

Predict first. What creates the factorial multiplier?

Choose an example

Choose whether order changes the outcome. For 3 of eight people, 56 committees become 336 assignments to distinct jobs. Each committee has exactly 6 orderings.
Selected people k: 3
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Committee count
56
Job assignments
336
Multiplicity k!
6

For 3 of eight people, 56 committees become 336 assignments to distinct jobs. Each committee has exactly 6 orderings.

Use the idea

Use rule 9.2.2 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Distinct people, no replacement; all selected jobs are labeled and filled.

Check your understanding: What creates the factorial multiplier?
Every chosen committee has exactly k! bijections to the k distinct jobs.

Book source: Rule 9.2.2: Ask whether order changes the outcome. Demonstration C09-D01. Worked illustration.

2Demonstration 2 of 4

Check counts by exhaustive enumeration

How many strings contain at least one 1?

Enumerate a small space and count strings by their number of ones. The distribution verifies a binomial counting identity.

#{0,1}n=2n,#{k ones}=(nk) \#\{0,1\}^n=2^n,\quad\#\{\text{k ones}\}=\binom nk

Binary string length n. Finite binary strings with labeled positions; counts are not probabilities until a probability model is specified.

Predict first. How many strings contain at least one 1?

Choose an example

Check counts by exhaustive enumeration. Enumerating all 64 binary strings confirms the binomial counts. Excluding only the all-zero string leaves 63. The tallest bar is in the middle: 20 strings have exactly 3 ones.
Binary string length n: 6
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Total strings
64
At least one 1
63
Balanced count
20

Enumerating all 64 binary strings confirms the binomial counts. Excluding only the all-zero string leaves 63. The tallest bar is in the middle: 20 strings have exactly 3 ones.

Use the idea

Use rule 9.1.2 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Finite binary strings with labeled positions; counts are not probabilities until a probability model is specified.

Check your understanding: How many strings contain at least one 1?
There are 2ⁿ total strings and exactly one all-zero string, giving 2ⁿ−1.

Book source: Rule 9.1.2: Remember that an n-set has two to the n subsets. Demonstration C09-D02. Worked illustration.

3Demonstration 3 of 4

Expose unequal symmetry orbits

Why is dividing 2ⁿ by n generally wrong?

Explicitly form rotation orbits and inspect their sizes before attempting division by symmetry.

necklaces=#({0,1}n/rotations) \text{necklaces}=\#(\{0,1\}^n/\text{rotations})

Necklace length n. Binary necklaces identified by rotation only, not reflection.

Predict first. Why is dividing 2ⁿ by n generally wrong?

Choose an example

Expose unequal symmetry orbits. Rotation orbits do not all have size 4. Constant strings have orbit size one, so dividing 16 by 4 does not count the 6 distinct necklaces.
Necklace length n: 4
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Binary necklaces
6
Naive 2ⁿ/n
4
Distinct orbit sizes
1, 2, 4

Rotation orbits do not all have size 4. Constant strings have orbit size one, so dividing 16 by 4 does not count the 6 distinct necklaces.

Use the idea

Use rule 9.1.6 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Binary necklaces identified by rotation only, not reflection.

Check your understanding: Why is dividing 2ⁿ by n generally wrong?
Some patterns have rotational symmetry and shorter orbits. Constant strings already supply orbit size one.

Book source: Rule 9.1.6: Divide by symmetry only when every orbit has the same size. Demonstration C09-D03. Worked illustration.

4Demonstration 4 of 4

See the no-match probability lock onto 1/e

Is a no-match much rarer with 100 guests than with 8?

Hand n hats back at random. A derangement is a shuffle where nobody gets their own. The chance of that barely depends on n: it settles near 1/e≈0.368 almost at once.

Dn=round⁡(n!/e) D_n=\operatorname{round}(n!/e)

Number of people n. Uniform random shuffles of n labeled people; rounding n!/e is exact for every n≥1.

Predict first. Is a no-match much rarer with 100 guests than with 8?

Choose an example

See the no-match probability lock onto 1/e. With 5 people there are 120 ways to hand back hats and 44 leave nobody with their own. That is 0.3667, already within 0.0012 of 1/e. Rounding n!/e gives the exact count, so the shortcut is safe.
Number of people n: 5
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

People n
5
Derangements D(n)
44
Arrangements n!
120
Exact probability
0.366667
n!/e rounded
44

With 5 people there are 120 ways to hand back hats and 44 leave nobody with their own. That is 0.3667, already within 0.0012 of 1/e. Rounding n!/e gives the exact count, so the shortcut is safe.

Use the idea

Use rule 9.3.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Uniform random shuffles of n labeled people; rounding n!/e is exact for every n≥1.

Check your understanding: Is a no-match much rarer with 100 guests than with 8?
No. With 8 the chance is already 0.36788, and it stays within a hair of 1/e for any larger n.

Book source: Rule 9.3.3: Estimate derangements by factorial over e. Demonstration C09-D04. Worked illustration.

Bring the idea to a question of your own

Choose the relationship that answers your question, check its conditions, and compare the result with the accuracy or decision threshold you need.

The chapter skill can adapt these calculations to your inputs. It should name the assumptions, explain what the result supports, and say what still needs evidence. The chapter workbook adds a lab and three exercises with answers.