Course contentsShow
← Mathematics
Lesson 2614 of 3,12152. CombinatoricsFree lesson

Distribution Problems with Constraints

Solve problems involving distributing distinct or identical objects into labeled groups with specified sizes.

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:

  1. Distinct objects → Labeled boxes (unrestricted): Each object independently chooses a box → n^k ways for k objects into n boxes
  2. Distinct objects → Labeled boxes (specified sizes): Use multinomial coefficients when box 1 gets n₁ items, box 2 gets n₂, etc. → n!/(n₁!n₂!...nₖ!)
  3. 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
  4. 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.