UNIVERSITY OF SOUTH AFRICA (UNISA)
College of Science, Engineering and Technology
⋄
Assignment 2
Discrete Mathematics: Combinatorics — 2026
⋄
Module Code: MAT3707
Module Name: Discrete Mathematics: Combinatorics
Assignment No.: Assignment 2
Due Date: 28 July 2026, 20:00
Semester: Semester 2, 2026
Total Marks: 100
Submitted in partial fulfilment of the requirements for Discrete Mathematics: Combinatorics
at the University of South Africa.
,UNISA | MAT3707 Discrete Mathematics: Combinatorics
Question 1
If A is a set of m elements and B is a set of n elements then: (i) find the number of elements in
the set (A × {A}) ∪ (B × {B}); how different is it from the set A ∪ B — explain with examples.
(ii) find the number of elements that the set A × B = {(x, y) : x ∈ A AND y ∈ B} has. (iii) find
the number of elements that the set 2A of all subsets of A has. (iv) find the number of elements
f
that the set B A = {f : A − → B} of all functions from A to B has. (v) find the number of
k-element subsets of B; in particular, prove: 0≤k≤n nk = 2n .
P
Let A be a set of m elements and B a set of n elements.
1.1 The set (A × {A}) ∪ (B × {B})
The set A × {A} pairs every element of A with the single symbol A, so it contains exactly one
ordered pair for each element of A:
|A × {A}| = m.
Likewise |B × {B}| = n. Every pair in A × {A} has second coordinate A, while every pair in
B × {B} has second coordinate B, so the two sets share no element and
|(A × {A}) ∪ (B × {B})| = m + n.
This set is fundamentally different from A ∪ B: A ∪ B is a set of m + n (or fewer, if A ∩ B =
̸ ∅)
individual elements drawn from A and B, whereas (A × {A}) ∪ (B × {B}) is a set of ordered
pairs, none of which is an element of A or B at all. Only the cardinalities coincide when A ∩ B =
∅; the objects themselves are of different types.
For example, with A = {1, 2} and B = {3, 4},
A ∪ B = {1, 2, 3, 4}, (A × {A}) ∪ (B × {B}) = {(1, A), (2, A), (3, B), (4, B)}.
The first set contains numbers; the second contains ordered pairs, so no element of one set
equals an element of the other, even though both have four members.
Page 1 of 19
,UNISA | MAT3707 Discrete Mathematics: Combinatorics
1.2 The set A × B
Every element of A may be paired with every element of B: there are m choices for the first
coordinate and, independently, n choices for the second coordinate. Hence
|A × B| = mn.
1.3 The set 2A
Each element of A either belongs to a given subset or does not, giving two independent
choices per element. With m elements this yields 2| × 2 × m
{z· · · × 2} = 2 , so
m
|2A | = 2m .
1.4 The set B A
A function f : A → B assigns to each of the m elements of A one of the n elements of B,
m
| ×n×
independently. This gives n {z· · · × n} = n functions, so
m
|B A | = nm .
Pn n
= 2n
1.5 k-element subsets of B and the identity k=0 k
The number of k-element subsets of B is
n n!
= .
k k!(n − k)!
n
X n
To prove = 2n , the total collection of subsets of B is counted in two ways. Directly,
k
k=0
each of the n elements is either included in a subset or excluded from it, giving 2n subsets
in total by part 1.3. Alternatively, the subsets may be grouped by size: there are n0 subsets
of size 0, n1 of size 1, and so on up to nn . Since every subset has exactly one size, these
Page 2 of 19
, UNISA | MAT3707 Discrete Mathematics: Combinatorics
groups partition the full collection of subsets, so their sizes add to the same total:
n
X n
= 2n .
k
k=0
Both expressions count the same collection of subsets of B, so they are equal.
n
X n
= 2n .
k
k=0
Page 3 of 19
College of Science, Engineering and Technology
⋄
Assignment 2
Discrete Mathematics: Combinatorics — 2026
⋄
Module Code: MAT3707
Module Name: Discrete Mathematics: Combinatorics
Assignment No.: Assignment 2
Due Date: 28 July 2026, 20:00
Semester: Semester 2, 2026
Total Marks: 100
Submitted in partial fulfilment of the requirements for Discrete Mathematics: Combinatorics
at the University of South Africa.
,UNISA | MAT3707 Discrete Mathematics: Combinatorics
Question 1
If A is a set of m elements and B is a set of n elements then: (i) find the number of elements in
the set (A × {A}) ∪ (B × {B}); how different is it from the set A ∪ B — explain with examples.
(ii) find the number of elements that the set A × B = {(x, y) : x ∈ A AND y ∈ B} has. (iii) find
the number of elements that the set 2A of all subsets of A has. (iv) find the number of elements
f
that the set B A = {f : A − → B} of all functions from A to B has. (v) find the number of
k-element subsets of B; in particular, prove: 0≤k≤n nk = 2n .
P
Let A be a set of m elements and B a set of n elements.
1.1 The set (A × {A}) ∪ (B × {B})
The set A × {A} pairs every element of A with the single symbol A, so it contains exactly one
ordered pair for each element of A:
|A × {A}| = m.
Likewise |B × {B}| = n. Every pair in A × {A} has second coordinate A, while every pair in
B × {B} has second coordinate B, so the two sets share no element and
|(A × {A}) ∪ (B × {B})| = m + n.
This set is fundamentally different from A ∪ B: A ∪ B is a set of m + n (or fewer, if A ∩ B =
̸ ∅)
individual elements drawn from A and B, whereas (A × {A}) ∪ (B × {B}) is a set of ordered
pairs, none of which is an element of A or B at all. Only the cardinalities coincide when A ∩ B =
∅; the objects themselves are of different types.
For example, with A = {1, 2} and B = {3, 4},
A ∪ B = {1, 2, 3, 4}, (A × {A}) ∪ (B × {B}) = {(1, A), (2, A), (3, B), (4, B)}.
The first set contains numbers; the second contains ordered pairs, so no element of one set
equals an element of the other, even though both have four members.
Page 1 of 19
,UNISA | MAT3707 Discrete Mathematics: Combinatorics
1.2 The set A × B
Every element of A may be paired with every element of B: there are m choices for the first
coordinate and, independently, n choices for the second coordinate. Hence
|A × B| = mn.
1.3 The set 2A
Each element of A either belongs to a given subset or does not, giving two independent
choices per element. With m elements this yields 2| × 2 × m
{z· · · × 2} = 2 , so
m
|2A | = 2m .
1.4 The set B A
A function f : A → B assigns to each of the m elements of A one of the n elements of B,
m
| ×n×
independently. This gives n {z· · · × n} = n functions, so
m
|B A | = nm .
Pn n
= 2n
1.5 k-element subsets of B and the identity k=0 k
The number of k-element subsets of B is
n n!
= .
k k!(n − k)!
n
X n
To prove = 2n , the total collection of subsets of B is counted in two ways. Directly,
k
k=0
each of the n elements is either included in a subset or excluded from it, giving 2n subsets
in total by part 1.3. Alternatively, the subsets may be grouped by size: there are n0 subsets
of size 0, n1 of size 1, and so on up to nn . Since every subset has exactly one size, these
Page 2 of 19
, UNISA | MAT3707 Discrete Mathematics: Combinatorics
groups partition the full collection of subsets, so their sizes add to the same total:
n
X n
= 2n .
k
k=0
Both expressions count the same collection of subsets of B, so they are equal.
n
X n
= 2n .
k
k=0
Page 3 of 19
