The number of balls to distribute
The number of boxes to distribute into
Result
-
=
-
About Balls and Boxes Problems
Balls and Boxes problems are fundamental in combinatorics, dealing with different ways to distribute objects (balls) into containers (boxes).
Cases and Formulas
1. Distinct Balls, Distinct Boxes
- With empty boxes allowed: \(k^n\)
- No empty boxes allowed: \(S(n,k) \cdot k!\) (Surjective functions)
2. Distinct Balls, Identical Boxes
- No empty boxes allowed: \(S(n,k)\) (Stirling number of the second kind)
- Empty boxes allowed: \(\sum_{i=1}^{\min(n,k)} S(n,i)\) (Sum of Stirling numbers)
3. Identical Balls, Distinct Boxes
- Empty boxes allowed: \(\binom{n+k-1}{k-1}\) (Stars and Bars)
- No empty boxes allowed: \(\binom{n-1}{k-1}\) (Modified Stars and Bars)
4. Identical Balls, Identical Boxes
- Empty boxes allowed: \(p(n,{\leq}k)\) (Sum of partition numbers \(p(n,i)\) for \(i=1\) to \(\min(n,k)\))
- No empty boxes allowed: \(p(n,k)\) (Number of partitions of n into exactly k parts)
Examples
Consider n=3 balls and k=2 boxes:
- Distinct balls (1,2,3), Distinct boxes (A,B), Empty allowed:
8 ways: (123,∅), (12,3), (13,2), (1,23), (23,1), (2,13), (3,12), (∅,123) - Identical balls (●●●), Distinct boxes (A,B), Empty allowed:
4 ways: (●●●,∅), (●●,●), (●,●●), (∅,●●●)
Applications
- Resource allocation problems
- Probability theory and statistics
- Computer science (process scheduling)
- Chemistry (molecule arrangements)
- Operations research
Note: Some combinations of constraints may not be implemented or may result in very large numbers for bigger inputs.