Distribution Problems with Constraints
What You'll Learn
You'll learn how to systematically count the ways to distribute objects (distinct or identical) into labeled groups when specific size or occupancy restrictions apply.
The Core Idea
Distribution problems ask: "In how many ways can we place objects into boxes?" The challenge intensifies when constraints enter the picture—boxes must contain a certain number of items, some boxes must be non-empty, or objects must be allocated in specified amounts.
The key is identifying four fundamental scenarios:
- Distinct objects → Labeled boxes (unrestricted): Each object independently chooses a box → n^k ways for k objects into n boxes
- Distinct objects → Labeled boxes (specified sizes): Use multinomial coefficients when box 1 gets n₁ items, box 2 gets n₂, etc. → n!/(n₁!n₂!...nₖ!)
- Identical objects → Labeled boxes (each gets at least 1): This is the "stars and bars with constraint" problem → C(k-1, n-1) for k objects into n boxes
- Identical objects → Labeled boxes (unrestricted): Standard stars and bars → C(k+n-1, n-1)
Working with Constraints
When problems specify "Box A must have exactly 3 items" or "No box can be empty," you:
- Use multinomial coefficients for distinct objects with fixed allocations
- Apply complementary counting (total ways minus violating ways)
- Transform "at least one per box" problems via substitution (give each box one item first, then distribute the rest)
Example
Distribute 5 distinct books into 3 labeled shelves with 2, 2, and 1 books respectively: This is 5!/(2!·2!·1!) = 120/4 = 30 ways.
Key Takeaway: Distribution problems with constraints require identifying whether objects are distinct or identical, whether containers are labeled, and then selecting the appropriate counting formula—often multinomial coefficients or adjusted combinations—to respect the restrictions.