Distributing Objects

Combinatorics · Axiom Academy

Master the four fundamental cases of distribution problems and learn to choose the right counting technique Every distribution problem falls into one of four categories based on two binary questions: Are the objects distinct (labeled, unique) or identical (indistinguishable)? Are the bins distinct (labeled recipients) or identical (unlabeled groups)? 2. Case 1: Distinct Objects → Distinct Bins Problem: Distribute n distinct objects into k distinct bins. Each object must go into exactly one bin. Example: Assign 3 distinct tasks (A, B, C) to 2 workers (Worker 1, Worker 2). Each task has 2 choices, giving us 2³ = 8 possible assignments: (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2) 3. Case 2: Identical Objects → Distinct Bins Problem: Distribute n identical objects into k distinct bins. Only the count in each bin matters. Example: Distribute 5 identical cookies to 3 children. We need non-negative integers x₁ + x₂ + x₃ = 5. Using stars and bars: C(5+3-1, 3-1) = C(7, 2) = 21 ways. 4. Case 3: Distinct Objects → Identical Bins Problem: Partition n distinct objects into k non-empty, indistinguishable groups. Example: Partition A, B, C into 2 non-empty groups. S(3,2) = 3: The partitions are A , B,C , B , A,C , C , A,B Each object either goes alone in a new bin or joins one of the existing k bins. 5. Case 4: Identical Objects → Identical Bins Problem: Partition n identical objects into k non-empty, indistinguishable groups.

This is the written version of the interactive lesson above. See the full Combinatorics course.