SME
Discrete Mathematics
Combinatorics
Use this for “How many ways can a club of 10 choose a president, secretary and treasurer? A 3-person committee?”
Diagram
Row 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1; they add to 2¹⁰ = 1,024.
Entry 3 of row 10: C(10, 3) = 120.
The two above add to it: C(9, 2) + C(9, 3) = 36 + 84 = 120.
3 places in order: 10 × 9 × 8 = 720 orders.
Each
group
of
3
comes
in
3!
=
6
orders:
720
6
=
120
groups.
This is an example. Type your own values to start a new problem.
P(
n
,
r
)
=
P(n, r)
C(
n
,
r
)
=
C(n, r)
W
In order, repeats allowed
worked out (not typed)
M
Groups, repeats allowed
worked out (not typed)
Formulas
P(
n
,
r
)
=
n
!
(
n
−
r
)!
720
=
10!
(10 − 3)!
C(
n
,
r
)
=
P(
n
,
r
)
r
!
120
=
P(10, 3)
3!
W
=
n
r
1,000
=
10
3
M
=
(
n
+
r
− 1)!
r
! × (
n
− 1)!
220
=
(10 + 3 − 1)!
3! × (10 − 1)!
Assumptions
•
Order counts in an arrangement (president, then secretary) and not in a group (a committee).
•
Without repeats each item is used once, so P(n, r) and C(n, r) need r ≤ n.
•
With repeats an item can be picked again: n choices for each of the r places.
•
A group with repeats is r stars and n − 1 bars in a row: C(n + r − 1, r).
Step-by-step
WE KNOW
n = 10, r = 3
FIND
in order, no repeats (P(n, r)), groups, no repeats (C(n, r)), in order, repeats allowed (W), groups, repeats allowed (M)
Step 1 · Find in order, no repeats (P(n, r))
Use P(n, r) = n! ÷ (n − r)!
n
choices
for
the
first
place,
n
−
1
for
the
next,
and
so
on
for
r
places.
P(
n
,
r
)
=
10!
(10 − 3)!
P(10,
3)
=
10!
7!
=
10
×
9
×
8
=
720
P(
n
,
r
)
=
720
Step 2 · Find groups, no repeats (C(n, r))
Use C(n, r) = P(n, r) ÷ r!
Each
group
of
r
was
counted
once
for
each
of
its
r
!
orders,
so
divide
them
out.
C(
n
,
r
)
=
P(10, 3)
3!
C(10,
3)
=
P(10, 3)
3!
=
720
6
=
120
C(
n
,
r
)
=
120
Step 3 · Find in order, repeats allowed (W)
Use W = nʳ
Each
of
the
r
places
takes
any
of
the
n
items,
so
multiply
n
by
itself
r
times.
10
3
=
1,000
W
=
1,000
Step 4 · Find groups, repeats allowed (M)
Use M = (n + r − 1)! ÷ (r! × (n − 1)!)
Line
up
r
stars
(the
picks)
and
n
−
1
bars
(the
walls
between
kinds);
choose
the
stars’
places.
M
=
(10 + 3 − 1)!
3! × (10 − 1)!
C(12,
3)
=
12!
3! × 9!
=
220
M
=
220
Check
Put the numbers back in. Both sides should match.
720
=
10!
(10 − 3)!
✓
120
=
P(10, 3)
3!
✓
1,000
=
10
3
✓
220
=
(10 + 3 − 1)!
3! × (10 − 1)!
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
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?”
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?”