SME
Discrete Mathematics · Problem type
Counting functions
Use this for “How many functions are there from a 3-element set to a 4-element set, and how many of them are one-to-one?”
Diagram
3 places in order: 4 × 3 × 2 = 24 ways.
This is an example. Type your own values to start a new problem.
F
=
|Y|
I
=
!
(
−
)!
S
Onto functions
worked out (not typed)
Formulas
F
=
|Y|^|X|
64
=
4
3
I
=
|Y|!
÷
(|Y|
−
|X|)!
24
=
4!
(4 − 3)!
S
=
Σ
(−1)ⁱ
C(|Y|,
i)(|Y|
−
i)^|X|
0
=
Σ
(−1)ⁱ
C(4,
i)
(4 − i)
3
Assumptions
•
Each of the n inputs can go to any of the m outputs, so there are mⁿ functions.
•
One-to-one: each input takes an output no earlier input used, m × (m − 1) × … for n inputs, which is m! ÷ (m − n)!.
•
Onto: inclusion–exclusion takes away the functions that miss some output, Σ (−1)ⁱ C(m, i)(m − i)ⁿ.
•
The page takes up to 4 outputs, so the onto sum has at most 4 terms.
Step-by-step
WE KNOW
|X| = 3, |Y| = 4
FIND
functions (F), one-to-one functions (I), onto functions (S)
Step 1 · Find functions (F)
Use F = |Y|^|X|
Each input has m choices of output, and the n choices are made independently.
F
=
4
3
F
=
64
Step 2 · Find one-to-one functions (I)
Use I = |Y|! ÷ (|Y| − |X|)!
The first input has m outputs to pick from, the next one fewer, and so on for n inputs.
I
=
4!
(4 − 3)!
I
=
24
Step 3 · Find onto functions (S)
Use S = Σ (−1)ⁱ C(|Y|, i)(|Y| − i)^|X|
Take away the functions missing an output, add back those missing two, and so on; with fewer inputs than outputs it comes to 0.
S
=
|Y|^|X|
−
4
×
3^|X|
+
6
×
2^|X|
−
4
×
1^|X|
S
=
4
3
−
4
×
3
3
+
6
×
2
3
−
4
×
1
3
S
=
64
−
4
×
27
+
6
×
8
−
4
S
=
64
−
108
+
48
−
4
S
=
0
Check
Put the numbers back in. Both sides should match.
64
=
4
3
✓
24
=
4!
(4 − 3)!
✓
0
=
4
3
−
4
×
3
3
+
6
×
2
3
−
4
×
1
3
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.