Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works
Create a free account to open Production engineering. The free chapters of Connected Devices and the Internet of Things stay readable without one.

Chapter 0 wrap-up

Readiness: the counting toolkit

Closing thought

Counting rests on two moves. Multiply across stages that happen one after another, and add across cases that can't both happen. Permutations, combinations, and Pascal's triangle are those moves packaged for common shapes. A recurrence builds today's count from yesterday's. Graphs and trees are objects you will soon count, not just describe. The last two sections add a finishing step: once a count turns into a sum, you can reshape it until a known formula closes it.

You can now set up a basic count and finish it cleanly. Choosing 3 of 8 people gives \binom{8}{3} = 56 committees. A tree on 10 vertices always has 9 edges. The sum 1 + 2 + \cdots + 100 closes to \frac{100 \cdot 101}{2} = 5050. Chapter 1 turns from formulas to judgment. It asks how to read a word problem, decide what to count, and catch a count that counts something twice.

Chapter review

One practice set per topic this chapter taught — same fixed, ungraded ladders as the practice panels inside each section.

Practice: Product rule vs. sum rule, chapter review (4 problems · doesn’t affect your progress)

A sandwich shop lets you pick 1 bread (from 4) AND 1 filling (from 6) AND, separately, whether to add a side salad (yes or no). Which combination of rules counts the total number of order configurations?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Bread, filling, and side are all chosen together (AND), not as mutually exclusive alternatives -- the sum rule doesn't fit here.

Bread and filling aren't mutually exclusive alternatives -- both get chosen on every order -- so they multiply, not add.

The side choice is another independent AND stage, just like bread and filling -- it multiplies into the total instead of being added on afterward.

Why

All three choices happen together on every order (AND, not OR), and none restricts the others -- three independent stages multiply: 4 * 6 * 2 = 48.

Product rule throughout: 462

A raffle prize goes to one winner chosen from 15 students or 8 staff members, never both. How many people could win?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Mutually exclusive groups add: 15+8=23.

Correct answer

Also accepted:

Why

23

A bike shop has 5 frame colors and 3 wheel sizes, all combinations available -- OR a customer can instead pick from 4 pre-built display bikes as-is, never combining a custom build with a display bike. How many total options does a customer have?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Custom builds use the product rule (5*3=15 combinations); the display bikes are a separate mutually exclusive alternative (sum rule): 15+4=19.

Correct answer

Also accepted:

Why

Handle the custom-build stage with the product rule first, then add the separate display-bike alternative with the sum rule.

19

A survey of 50 people finds 30 like coffee and 22 like tea; a student computes 'likes coffee or tea' as 30+22=52, more than the 50 people surveyed. What does this signal?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Getting a total larger than the number of people surveyed is a red flag that the two groups overlap -- some people like both drinks and got counted twice. The sum rule requires disjoint groups; overlapping ones need inclusion-exclusion instead.

A count larger than the total number of people surveyed is a red flag -- think about what that signals about the two groups' overlap.

Ask whether a person who likes both coffee and tea got counted once or twice in 30+22.

The sum rule was misapplied -- the two groups overlap (some people like both), so simple addition double-counts them

Practice: Permutations and combinations, chapter review (5 problems · doesn’t affect your progress)

Awarding gold, silver, and bronze medals to 3 of 8 racers is:

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Only counting HOW MANY are chosen ignores that gold, silver, and bronze are different positions -- swapping which racer gets which medal changes the outcome.

Why

Gold, silver, and bronze are distinct ordered positions -- a permutation, P(8,3).

A permutation, since the 3 medal positions are distinct

How many ways can a 4-person study group be chosen from a class of 11, with no assigned roles?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

C(11,4) = 11!/(4!7!) = 330.

Correct answer

Also accepted:

Why

330

In how many ways can 1st and 2nd place be awarded among 9 finalists?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

P(9,2)=9*8=72.

Correct answer

Also accepted:

Why

Fill the two ordered positions one at a time, using one fewer finalist for the second position.

72

A code uses 3 digits chosen from 0-9, repeats allowed, order mattering. Which count applies?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

P(10,3) assumes no repeats -- but this code allows digits to repeat.

Combinations ignore order entirely, but a code's digit order matters.

That's the combination formula written out -- still ignores order and disallows repeats.

Why

With repetition allowed and order mattering, neither the permutation nor combination formula (both assume no repeats) applies directly -- it's the plain product rule, 101010=1000.

Check both assumptions the permutation and combination formulas share -- does this problem actually satisfy 'no repeats'?

10^3, the product rule directly, since repeats are allowed

A 5-person committee is chosen from 12 people, and then, separately, one of those 5 is designated chair. How many committee-with-chair outcomes are possible?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Choose the 5-person committee first (C(12,5)=792), then choose the chair from within it (5 ways): 792*5=3960.

Correct answer

Also accepted:

Why

Break this into two stages: choosing the unordered committee, then choosing the one distinguished role from within it.

Multiply the combination count for the committee by the number of ways to pick a chair from among its 5 members.

3960
Practice: Pascal's triangle and binomial coefficients, chapter review (4 problems · doesn’t affect your progress)

Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) is proven by:

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Fixing one item, every k-subset either includes it (choose k-1 more from the rest) or excludes it (choose all k from the rest) -- a clean two-case split, not brute-force computation.

A case split on whether one fixed item is included in the k-subset

How many individual entries does row 8 of Pascal's triangle have (values of k running from 0 through 8)?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Row n has one entry for each k from 0 through n, giving n+1 entries; row 8 has 8+1=9 entries.

Correct answer

Also accepted:

Why

9

Given C(9,4) = 126, use the symmetry identity to find C(9,5) with no further computation.

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

C(n,k)=C(n,n-k): here n-k=9-4=5, so C(9,5)=C(9,4)=126 directly, by symmetry alone.

Correct answer

Also accepted:

Why

Compute n-k for C(9,5) and compare it to the k-value already given in C(9,4).

126

A student computes C(15,0) as 0, reasoning that choosing zero items gives nothing to select. What is the actual value, and why?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

C(n,0)=1 for every n: there is exactly one way to select zero items -- the empty selection -- not zero ways. 'Nothing to select' still describes one specific outcome, not an impossible one.

Think about how many distinct ways there are to select absolutely nothing from a set -- is that count zero outcomes, or one specific outcome?

1, since there is exactly one way to choose nothing at all -- the single empty selection

Practice: Recurrence relations and iteration, chapter review (4 problems · doesn’t affect your progress)

Which of these is a genuine recurrence relation with everything needed to compute every term?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Without an initial value, the rule alone describes infinitely many different sequences -- it's incomplete.

A formula with no reference to a_(n-1) or earlier terms isn't a recurrence at all -- it's already a closed form.

An initial value alone, with no rule linking it to later terms, doesn't define a sequence beyond that one term.

Why

A complete recurrence needs both the rule relating a_n to earlier terms AND an initial condition to anchor it -- only this option has both.

a_n = a_(n-1) + 2, a_1 = 5

A sequence starts at 3, and each next term is 4 more than the one before it. What is the 8th term?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Unfolding gives term_n = 3 + 4(n-1); the 8th term is 3+4(7)=31.

Correct answer

Also accepted:

Why

31

Starting from 2, each new term in a sequence adds three times the new term's own position to the previous term: term 2 adds 32, term 3 adds 33, and so on. What is the 4th term?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

term_1=2, term_2=2+6=8, term_3=8+9=17, term_4=17+12=29.

Correct answer

Also accepted:

Why

Compute each term in order, adding a fresh increment of 3 times that term's position at each step -- don't reuse the previous step's increment.

29

A recurrence a_n = a_(n-1) + a_(n-2) + a_(n-3) is unfolded for a few terms, and a student guesses a closed form on that basis. What is still missing before trusting it?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

This particular recurrence needs three initial conditions (a_1, a_2, a_3) to anchor it, which is a separate issue from whether a guessed closed form is actually verified.

Converting a higher-order recurrence's form isn't a required step before pattern-verification -- iteration and induction work directly on it as given.

Why

A pattern glimpsed from a few unfolded terms remains an unverified conjecture, no matter how many previous terms the recurrence references -- induction (or an equivalent proof) is what actually confirms it holds for every n.

A pattern from a handful of terms is a conjecture regardless of the recurrence's order -- think about what step turns a conjecture into a proven closed form.

Verification that the guessed closed form satisfies the recurrence for every n, typically by induction

Practice: Graphs, degree, and connectedness, chapter review (4 problems · doesn’t affect your progress)

In a graph, a vertex's degree is:

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

That describes reachability across the whole graph, not degree -- degree only counts DIRECTLY touching edges.

Why

Degree counts edges incident to (touching) that one vertex -- a purely local count, not a statement about the whole graph's reachability.

The number of edges touching it

A graph's vertices have degrees 3, 3, 2, 2. How many edges does it have?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Sum the degrees (3+3+2+2=10) and divide by 2: 10/2=5.

Correct answer

Also accepted:

Why

5

A graph has 4 components. What's the minimum number of degree-0 (isolated) vertices it could have?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

A component doesn't need an isolated vertex to exist -- a component can be a single edge, a cycle, or a larger connected piece where every vertex has degree at least 1.

Why

A component is just a maximal connected piece -- it can be a single isolated vertex (degree 0), or a larger piece where every vertex has degree at least 1. As long as each of the 4 components has at least one internal edge, zero isolated vertices are needed.

Think about whether a component is required to be a single isolated vertex, or whether it can be a larger connected piece with no degree-0 vertices at all.

0 -- every component could have internal edges and no isolated vertex

A graph has 7 vertices, 5 edges, and 1 component (fully connected). Is this possible?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Linking n vertices into a single connected piece needs at least n-1 edges (a tree's worth); for 7 vertices that's a minimum of 6. Five edges can connect at most 6 vertices into one piece, leaving at least one vertex stranded -- 1 component is impossible here.

Think about the fewest edges that could possibly connect n vertices into a single piece, with none wasted on a repeat connection.

Compare that minimum, for 7 vertices, against the 5 edges actually given.

No -- connecting 7 vertices into one piece needs at least 6 edges, and 5 is one too few

Practice: Trees and spanning trees, chapter review (4 problems · doesn’t affect your progress)

A spanning tree of a connected graph G is best described as:

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

A spanning tree reaches every one of G's vertices using exactly n-1 edges -- the fewest possible while staying connected -- and, being a tree, contains no cycles.

A subgraph that reaches every vertex of G using the fewest possible edges, with no cycles

A tree with 14 vertices has one additional edge added between two of its existing vertices, creating exactly one cycle. How many edges does the resulting graph have?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

The original tree has 14-1=13 edges; adding one more edge gives 13+1=14 edges total (and exactly one cycle, since the result is no longer a tree).

Correct answer

Also accepted:

Why

Find the original tree's edge count first, then add the one new edge on top of it.

14

A connected graph has 20 vertices. How many edges does any spanning tree of it have, regardless of how many edges the original graph has?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Spanning tree edge count depends only on vertex count: 20-1=19.

Correct answer

Also accepted:

Why

Apply the tree edge-count theorem directly to the vertex count, ignoring the original graph's own edge count entirely.

19

Removing one edge from a spanning tree of a 10-vertex graph leaves:

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Every edge in a tree is a bridge -- removing any single edge from a spanning tree splits it into exactly two components, since a tree has no alternate path around any edge.

Recall that a tree has exactly one path between any two vertices -- think about what removing one edge of that unique path does.

Two separate pieces -- the tree splits into exactly two components

Practice: Manipulating and closing finite sums, chapter review (5 problems · doesn’t affect your progress)

Before applying a memorized closed form, a sum sum_{i=3}^{n+2} i^2 needs to be rewritten to start at i=1. Which technique accomplishes that?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Relabeling the index (e.g. j=i-2) so the sum starts at j=1 is exactly what an index shift does, without changing which numbers get added.

Index shift

Using the arithmetic series closed form, what is 1+2+3+...+40?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

n(n+1)/2 with n=40: 40*41/2=820.

Correct answer

Also accepted:

Why

820

Evaluate sum_{i=1}^{9} (1/i - 1/(i+1)).

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Telescoping collapses the sum to 1 - 1/10 = 0.9.

Correct answer

Also accepted:

Why

Recognize the telescoping pattern, then collapse to just the first and last surviving pieces.

0.9

A finite geometric sum has first term 1, common ratio 5, and 4 terms total (r^0 through r^3). Using the closed form, what is its value?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

(5^4-1)/(5-1)=624/4=156, matching the closed form for a finite geometric sum with r=5 across 4 terms.

Correct answer

Also accepted:

Why

Apply (r^{n+1}-1)/(r-1) with r=5, matching the 4 terms to the exponent n+1=4.

156

A sum is split as sum_{i=1}^{n}(5i^2 - 3i), then evaluated at n=4 using the appropriate closed forms. What is the result?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

Split into 5sum(i^2) - 3sum(i). At n=4: sum(i^2)=30 so 530=150; sum(i)=10 so 310=30. 150-30=120.

Correct answer

Also accepted:

Why

Split the sum into two pieces first -- 5sum(i^2) and 3sum(i) -- each with its own closed form at n=4.

Compute each closed-form piece separately with n=4, then subtract, keeping track of each piece's coefficient.

120
Take the chapter quiz On to Chapter 1 →
← Closed forms for finite sums Counting strategies →
  • No matches.