Discrete Mathematics · Combinatorics and inclusion-exclusion
Four labs sharing ten hours cannot exceed a per-lab cap
Problem
Discrete Mathematics practice problemFour teaching labs share ten identical instrument-hours in a week. Lab receives hours, where each is an integer satisfying , and .
1. First ignore the upper bounds. Prove that the number of nonnegative integer solutions of is . Then, for the uniform bound , apply inclusion-exclusion: if a prescribed set of variables is at least , the change of variables produces an unrestricted nonnegative problem. Conclude that the number of feasible tuples iswith the usual convention that when or (except is never needed here) and for a negative upper index in this nonnegative setting.
2. Specialize to , , . Compute every surviving term explicitly and evaluate the sum.
3. The ordinary generating function for one lab is . Extract from the expansion and confirm the same integer.
4. List the integer partitions of into exactly four parts, each part at most (parts may be ). 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 with the same cap, or by dropping the 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
HintWithout the cap, four nonnegative unknowns summing to are counted by . A variable that is at least leaves a residual sum of .
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
- Let p, q, and r be propositionsPropositional and predicate logic with proof methods
- Let A={1,2,3,4} and B={3,4,5,6}Propositional and predicate logic with proof methods
- Let R be a relation on a set ASets, functions, relations, and equivalence classes
- Use strong induction to prove that every positive integer n can be written as n=2^k m…Sets, functions, relations, and equivalence classes
- (Honors) Let uₙ be defined by u₀=0, u₁=1, and uₙ=4uₙ₋₁-4uₙ₋₂+n for n ≥ 2Induction, recursion, and invariants
- [Honors] Using inclusion-exclusion, find the number of permutations π of {1,2,…,9} such…Induction, recursion, and invariants
- Let n be a positive integerRecurrences, generating functions, and discrete asymptotics
- RSA decryption needs Euler, and Euler needs a coprime messageDivisibility, modular arithmetic, and elementary number theory
- BFS two-coloring is the certificate that no odd cycle existsGraphs, trees, connectivity, and matchings