Count allocations with bounds

Try

Distribute eight identical tokens among three labeled boxes, requiring at least one token in each. Place two separators among the seven gaps between tokens; their positions determine three positive parts. There are C(7, 2)=21 allocations. The boxes are labeled, so (1, 2, 5) and (5, 2, 1) differ even though they have the same multiset of occupancies. Integer partitions, studied later, forget that ordering.

Predict

Predict how an upper capacity changes the problem. Ordinary stars and bars counts allocations that may overfill a box. Subtracting each overfill count separately subtracts allocations with two overfilled boxes twice. Inclusion–exclusion repairs this overlap. Before calculating, check feasibility: with k boxes and capacity b, totals above kb are impossible, and totals below zero are impossible under nonnegative occupancies.

Experiment

For three boxes of capacity two and total four, organize the valid tuples by shape.

Shape	Distinct labeled arrangements
(2, 2, 0)	3
(2, 1, 1)	3
Total	6

The unrestricted count is C(6, 2)=15. A specified box with at least three tokens leaves one token after a shift, giving C(3, 2)=3 possibilities. Subtract 3·3 to obtain six; two capacity violations cannot fit into total four. Verify that impossibility rather than adding a spurious overlap term.

Understand

For k≥1, weak compositions are tuples of nonnegative integers summing to n. A word with n stars and k−1 separators gives a bijection, so the count is C(n+k−1, k−1). Lower bounds ℓ_i are removed by writing y_i=x_i−ℓ_i and replacing the total by n−Σℓ_i. For a common upper bound b, define violation A_i by x_i≥b+1. If a selected set J of j boxes violates the bound, subtract b+1 from each selected coordinate. The remaining weak composition has total n−j(b+1). Inclusion–exclusion therefore gives Σ_j(−1)^j C(k, j)C(n−j(b+1)+k−1, k−1), with negative remaining totals contributing zero. Distinct capacities work similarly, but the shifted total depends on the actual subset J rather than only its size.

Encode a spaced arrangement, then count the encoding

Place three indistinguishable marked objects and five indistinguishable unmarked objects in a row. Require the first object marked, the last unmarked, and at least one unmarked object between consecutive marks. The pattern M U M U M U U U is valid. Its unmarked-gap vector is (0,1,1,3): before the first mark, between the two successive pairs, and after the last mark. The first gap is forbidden, not another free box.

Which gaps may receive the remaining objects?

Choose exactly k marked positions. The first position must be marked, the last unmarked, with at least d unmarked positions between successive marks. Predict the gaps before inspecting the residual allocation.

Length n 45678910 Marks k 1234 Minimum internal gap d 012 Reset

1: Marked2: Unmarked3: Marked4: Unmarked5: Marked6: Unmarked7: Unmarked8: Unmarked

3/3 selected. All constraints pass.

Free unmarked objects after mandatory gaps: 2. Valid positional arrangements: 6. If a leading gap were wrongly permitted: 10.

Gap	Actual unmarked count	Requirement
Before first mark	0	Exactly zero
Between marks 1 and 2	1	At least 1
Between marks 2 and 3	1	At least 1
After last mark	3	At least 1

Residual weak-composition vector: (0, 0, 2), summing to 2. Reinsert the mandatory gaps to reconstruct this arrangement uniquely.

At most10 positions; no random sampling or learner code. Marks of the same kind are indistinguishable here. Label permutations require a separate stated rule. Temporary exploration does not establish independent proof quality.

For a general length n and k≥1 marks, let g₀,…,gₖ count unmarked objects in the gaps. Reading the row gives a unique gap vector, and rebuilding M symbols separated by those gaps recovers the row. Thus this is a bijection, not merely a convenient drawing. Starting marked means g₀=0. With minimum internal spacing d≥0 and at least one trailing unmarked object, the other constraints are gᵢ≥d for1≤i≤k−1 and gₖ≥1. The gaps sum to n−k.

Subtract the mandatory objects: hᵢ=gᵢ−d for internal gaps and hₖ=gₖ−1. There are k, not k+1, free nonnegative variables, and their sum is M=n−k−d(k−1)−1. If M<0 there is no arrangement. Otherwise stars and bars counts C(M+k−1,k−1) possibilities. For n=8,k=3,d=1, M=2 and the answer is C(4,2)=6. Allowing an extra leading gap would instead give C(5,3)=10, counting arrangements that violate the first-position rule.

At k=1 there are no internal gaps; the first mark is forced and all n−1 unmarked objects trail it, giving one arrangement whenever n≥2. When M=0 every gap is forced and there is again exactly one arrangement. These boundaries test the number of free boxes and the feasibility condition. Do not assign a binomial coefficient with a negative top argument to an impossible allocation and call it a count.

General spacing and labels require separate choices

The same bijection works with distinct lower bounds d₁,…,dₖ₋₁ in the internal gaps and a trailing lower bound e. Keep the leading gap fixed at zero and subtract the sum of these mandatory bounds; there are still k free gap variables. For example, length10 with three marks, internal lower bounds1 and2, and trailing lower bound2 leaves M=10−3−1−2−2=2, hence C(4,2)=6 positional patterns.

If the marked objects are distinct but their relative order is prescribed, each positional pattern still gives one arrangement. If their relative order is unrestricted and the constraints refer only to marked versus unmarked, each pattern has k! labelings. If all unmarked objects are also distinct with unrestricted relative order, multiply separately by (n−k)!. Those factorial factors require a constant number of labelings for every allowed pattern; restrictions involving specific labels can break that argument. Counting gaps alone does not decide which labeling model the problem intends.

Apply

Generating functions encode the same choices: the coefficient of z^n in (1+z+…+z^b)^k counts bounded tuples. Each factor represents one labeled box; selecting a monomial records its occupancy. Rewriting each factor as (1−z^(b+1))/(1−z) yields the inclusion–exclusion formula after expansion. This is a formal coefficient argument, so no real value of z or analytic convergence is needed. If objects have different weights, use factors whose exponents reflect those weights rather than applying unweighted stars and bars.

Unequal upper bounds give a useful transfer test. For x+y=7 with 0≤x≤2 and 0≤y≤6, direct inspection leaves x=1 or 2. Inclusion–exclusion starts with eight unrestricted solutions, subtracts five with x≥3 and one with y≥7, and adds no double violation. The result two agrees. Writing the shifted intersection totals explicitly catches errors that a symmetric capacity formula can hide.

Continue

For a resource-allocation report, state which items are identical, which recipients are labeled, whether empty allocations are allowed, and whether capacities are hard constraints. An integer count does not determine a probability unless a sampling rule is supplied. A uniform choice among all token placements can induce a nonuniform distribution on occupancy tuples. The inclusion–exclusion prerequisite supplies the basic sign rule; here the substantive step is the bijection that counts each intersection.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with track inversions with a generating polynomial.