Skip to main content

Discrete Mathematics · Combinatorics and inclusion-exclusion

Four labs sharing ten hours cannot exceed a per-lab cap

Problem

Discrete Mathematics practice problem

Four teaching labs share ten identical instrument-hours in a week. Lab ii receives xix_i hours, where each xix_i is an integer satisfying 0≤xi≤40\le x_i\le 4, and x1+x2+x3+x4=10x_1+x_2+x_3+x_4=10.

1. First ignore the upper bounds. Prove that the number of nonnegative integer solutions of x1+⋯+xk=nx_1+\cdots+x_k=n is (n+k−1k−1)\binom{n+k-1}{k-1}. Then, for the uniform bound xi≤mx_i\le m, apply inclusion-exclusion: if a prescribed set of jj variables is at least m+1m+1, the change of variables yi=xi−(m+1)y_i=x_i-(m+1) produces an unrestricted nonnegative problem. Conclude that the number of feasible tuples is∑j≥0(−1)j(kj)(n−j(m+1)+k−1k−1),\sum_{j\ge 0}(-1)^j\binom{k}{j}\binom{n-j(m+1)+k-1}{k-1},with the usual convention that (ab)=0\binom{a}{b}=0 when a<ba<b or a<0a<0 (except (−1−1)\binom{-1}{-1} is never needed here) and (rk−1)=0\binom{r}{k-1}=0 for a negative upper index in this nonnegative setting.

2. Specialize to k=4k=4, n=10n=10, m=4m=4. Compute every surviving term explicitly and evaluate the sum.

3. The ordinary generating function for one lab is 1+x+⋯+x4=(1−x5)/(1−x)1+x+\cdots+x^4=(1-x^5)/(1-x). Extract [x10](1+x+⋯+x4)4[x^{10}](1+x+\cdots+x^4)^4 from the expansion (1−x5)4(1−x)−4(1-x^5)^4(1-x)^{-4} and confirm the same integer.

4. List the integer partitions of 1010 into exactly four parts, each part at most 44 (parts may be 00). For each type, count the distinct labellings of the four labs, and check that the type totals sum to the integer from parts 2 and 3. Explain why replacing the model by positive unknowns yi≥1y_i\ge 1 with the same cap, or by dropping the j=2j=2 term of inclusion-exclusion, produces a different number.

Do not convert the problem into a marked-subset binomial-moment identity, and do not treat the variables as indistinguishable.

Hint

Hint

Without the cap, four nonnegative unknowns summing to 1010 are counted by (133)\binom{13}{3}. A variable that is at least 55 leaves a residual sum of 55.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.

More Discrete Mathematics practice problems

Back to Discrete Mathematics

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.