Weak compositions, loop invariants and flowchart tracing
| English | Français |
|---|---|
| loop invariant/luːp ɪnˈveərɪənt/ | loop invariant |
| weak composition/wiːk ˌkɒmpəˈzɪʃn/ | weak composition |
A decision before an answer
- Allocating identical tokens to named boxes is different from choosing ordered recipients for distinct tokens. A small change in the counting model can change the answer by a large factor.
- Your goal: Count indistinguishable allocations with nonnegative or positive constraints.
Read the relationship
- The number of nonnegative integer solutions of x₁+⋯+x_k=n is C(n+k−1,k−1), for n≥0 and k≥1. Represent n identical stars separated into k named boxes by k−1 bars; adjacent bars and end bars allow zero entries. Boxes are distinguishable, objects are not. Counting distinct tokens would instead assign each token independently, giving k^n before other constraints. Decide the model from what the objects and recipients represent, not from a familiar-looking binomial coefficient.
- Trace a flowchart in statement order with correct reset behaviour.
How many ways put 11 identical tokens into 4 named boxes, allowing empty boxes?
There are 11 stars and 3 bars. Choose the 3 bar positions among 14 positions: C(14,3)=364.
Use the defining rule
- For positive allocations x_i≥1, put z_i=x_i−1; the remaining total is n−k, giving C(n−1,k−1) when n≥k. More general lower bounds x_i≥a_i are handled by subtracting each a_i. At least one zero is the complement of every entry positive: subtract C(n−1,k−1) from the nonnegative total. Overlapping cases such as exactly two empty boxes need a different count; subtracting each empty-box case independently double-counts their intersections.
- Use a loop invariant and a progress measure to justify an algorithm.
Starting from S=0, add successive odd numbers 1,3,5,… until S≥10. What is S at exit?
The successive sums are 1,4,9,16. The first sum at least 10 is 16, so the test overshoots rather than declaring 10 square.
Check the conditions
- Trace a flowchart one executed statement at a time, recording variables in a table. Distinguish assignment from a mathematical equality test; the right side of an assignment uses the old value before replacement. Record which branch executes next and which variables reset. A new outer-loop candidate may reset an inner sum without resetting the candidate itself. For a process that adds 1,3,5,… to S from zero, after m additions S=m² and the next addend is 2m+1.
- Use a loop invariant and a progress measure to justify an algorithm.
Distribute 11 identical tokens among 4 named boxes. Nonnegative allocations number C(14,3)=364; all-positive allocations number C(10,3)=120. Therefore 244 allocations have at least one empty box. For the odd-sum test with N=10, S progresses 0,1,4,9,16; it overshoots and rejects 10. For N=9 it exits at S=9 after three additions. The next addends are 1,3,5,7,9; sum and next-addend columns must not be confused.
Of the 364 nonnegative allocations of 11 tokens to 4 boxes, 120 have every box positive. The count with at least one empty box is ____.
Subtract the all-positive complement once: 364−120=244.
Apply the task format
- A loop invariant is true before and after each iteration. The square-sum invariant holds initially at m=0 and is preserved because m²+(2m+1)=(m+1)². An invariant alone does not prove termination. To test whether an integer N≥0 is square by adding odd numbers until S≥N, S grows without bound; equivalently m increases and must reach a bound such as N. At exit, equality means square and overshoot means nonsquare. A printed value must be reached on an actual execution path; a plausible numerical pattern alone is not a trace.
- Use a loop invariant and a progress measure to justify an algorithm.
Identical objects and distinct objects use different models. At least one empty box is not the same as exactly one. In a flowchart, preserve update order and reset only variables that the executed path actually resets.
Which answer fits this case?
Count indistinguishable allocations with nonnegative or positive constraints
A preserved loop invariant alone proves that every execution of the loop terminates.
An infinite loop can preserve a property forever. Termination also needs a progress argument or decreasing well-founded measure.
Keep the distinctions
- weak composition 弱组合分拆 — An ordered allocation of a total into nonnegative integer parts.
- loop invariant 循环不变量 — A property preserved before and after each iteration of a loop.
- Count indistinguishable allocations with nonnegative or positive constraints.
- Trace a flowchart in statement order with correct reset behaviour.
- Use a loop invariant and a progress measure to justify an algorithm.
Match each term with its precise meaning in this lesson.
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
The order follows the stated process; check each stage before the next.