SME
Discrete Mathematics · Problem type
Identical items into boxes
Use this for “In how many ways can 10 identical balls go into 4 boxes? With at least one in each box?”
This is an example. Type your own values to start a new problem.
A
=
C(
n
+
k
−
1,
k
−
1)
B
=
C(
n
−
1,
k
−
1)
Formulas
A
=
(
n
+
k
− 1)!
n
! × (
k
− 1)!
286
=
(10 + 4 − 1)!
10! × (4 − 1)!
B
=
(
n
− 1)!
(
k
− 1)! × (
n
−
k
)!
84
=
(10 − 1)!
(4 − 1)! × (10 − 4)!
Assumptions
•
The items are identical and the boxes are different, so a way is just how many go in each box.
•
Stars and bars: n stars and k − 1 bars in a row; the bars split the stars into k boxes.
•
For at least one in each box, put one in each first, then share the n − k left.
Step-by-step
WE KNOW
n = 10, k = 4
FIND
ways, any box may be empty (A), ways, at least one in each (B)
Step 1 · Find ways, any box may be empty (A)
Use A = (n + k − 1)! ÷ (n! × (k − 1)!)
Of
the
n
+
k
−
1
spots
in
the
row,
choose
the
k
−
1
that
hold
bars.
A
=
(10 + 4 − 1)!
10! × (4 − 1)!
C(13,
3)
=
13!
3! × 10!
=
286
A
=
286
Step 2 · Find ways, at least one in each (B)
Use B = (n − 1)! ÷ ((k − 1)! × (n − k)!)
No
box
may
be
empty,
so
the
k
−
1
bars
go
in
the
n
−
1
gaps
between
stars,
one
per
gap.
B
=
(10 − 1)!
(4 − 1)! × (10 − 4)!
C(9,
3)
=
9!
3! × 6!
=
84
B
=
84
Check
Put the numbers back in. Both sides should match.
286
=
(10 + 4 − 1)!
10! × (4 − 1)!
✓
84
=
(10 − 1)!
(4 − 1)! × (10 − 4)!
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Combinatorics
Main lesson
The pigeonhole principle
Use this for “Among 50 people, at least how many share a birth month? How many people force 5 in one month?”
Derangements
Use this for “4 letters go into their 4 envelopes at random. In how many ways does no letter reach its own envelope?”
Words with repeated letters
Use this for “How many different words can be made from all 11 letters of MISSISSIPPI?”