UNIVERSITY OF SOUTH AFRICA
College of Science, Engineering and Technology
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
MAT3707: Discrete Math-
ematics: Combinatorics
Assignment 2 | 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
MAT3707
Module Code:
Discrete Mathematics: Combinatorics
Module Name:
Sets, Functions, Graphs, Probability, Recur-
Assignment Topic:
rence Relations and Counting
Assignment 2
Assignment Number:
28 July 2026, 20:00
Due Date:
100
Total Marks:
Submitted in partial fulfilment of the requirements for MAT3707, UNISA 2026
,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 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 that
n
X n
= 2n .
k
k=0
(i)
The set A × {A} contains one ordered pair for each element of A. Since A has m elements,
|A × {A}| = m × 1 = m.
Similarly,
|B × {B}| = n × 1 = n.
Every pair in A × {A} has second coordinate A, every pair in B × {B} has second coordinate B,
so the two sets are distinct.
|(A × {A}) ∪ (B × {B})| = m + n.
Difference from A ∪ B. A ∪ B contains elements. (A × {A}) ∪ (B × {B}) contains ordered pairs.
The two sets are different because one contains elements while the other contains ordered pairs.
Example. Let A = {1, 2}, B = {3, 4}. Then A ∪ B = {1, 2, 3, 4}, and
(A × {A}) ∪ (B × {B}) = {(1, A), (2, A), (3, B), (4, B)}.
The first set contains numbers. The second set contains ordered pairs.
Page 2 of 20
,UNISA | MAT3707 Discrete Mathematics: Combinatorics
(ii)
Each element of A can be paired with every element of B. There are m choices for the first coor-
dinate, n choices for the second coordinate.
|A × B| = m × n.
|A × B| = mn.
(iii)
Each element of A has two choices: belong to a subset, or not. Since there are m elements,
2 × 2 × · · · × 2 (m times) = 2m .
|2A | = 2m .
(iv)
Each element of A can be assigned to any one of the n elements of B. There are m independent
choices.
n × n × · · · × n (m times) = nm .
|B A | = nm .
(v)
Choosing k elements from n elements gives
n n!
= .
k k!(n − k)!
Pn n
= 2n . Each element of B has two choices: included, or excluded. Since
Proof that k=0 k
there are n elements,
2 × 2 × · · · × 2 (n times) = 2n .
n n
The subsets can also be grouped by size. There are 0 subsets with 0 elements, 1 subsets with
Page 3 of 20
, UNISA | MAT3707 Discrete Mathematics: Combinatorics
n
1 element, and so on until n . Adding all these subsets gives
n
X n
= 2n .
k
k=0
Page 4 of 20
College of Science, Engineering and Technology
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
MAT3707: Discrete Math-
ematics: Combinatorics
Assignment 2 | 2026
⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄ ⋄⋄
MAT3707
Module Code:
Discrete Mathematics: Combinatorics
Module Name:
Sets, Functions, Graphs, Probability, Recur-
Assignment Topic:
rence Relations and Counting
Assignment 2
Assignment Number:
28 July 2026, 20:00
Due Date:
100
Total Marks:
Submitted in partial fulfilment of the requirements for MAT3707, UNISA 2026
,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 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 that
n
X n
= 2n .
k
k=0
(i)
The set A × {A} contains one ordered pair for each element of A. Since A has m elements,
|A × {A}| = m × 1 = m.
Similarly,
|B × {B}| = n × 1 = n.
Every pair in A × {A} has second coordinate A, every pair in B × {B} has second coordinate B,
so the two sets are distinct.
|(A × {A}) ∪ (B × {B})| = m + n.
Difference from A ∪ B. A ∪ B contains elements. (A × {A}) ∪ (B × {B}) contains ordered pairs.
The two sets are different because one contains elements while the other contains ordered pairs.
Example. Let A = {1, 2}, B = {3, 4}. Then A ∪ B = {1, 2, 3, 4}, and
(A × {A}) ∪ (B × {B}) = {(1, A), (2, A), (3, B), (4, B)}.
The first set contains numbers. The second set contains ordered pairs.
Page 2 of 20
,UNISA | MAT3707 Discrete Mathematics: Combinatorics
(ii)
Each element of A can be paired with every element of B. There are m choices for the first coor-
dinate, n choices for the second coordinate.
|A × B| = m × n.
|A × B| = mn.
(iii)
Each element of A has two choices: belong to a subset, or not. Since there are m elements,
2 × 2 × · · · × 2 (m times) = 2m .
|2A | = 2m .
(iv)
Each element of A can be assigned to any one of the n elements of B. There are m independent
choices.
n × n × · · · × n (m times) = nm .
|B A | = nm .
(v)
Choosing k elements from n elements gives
n n!
= .
k k!(n − k)!
Pn n
= 2n . Each element of B has two choices: included, or excluded. Since
Proof that k=0 k
there are n elements,
2 × 2 × · · · × 2 (n times) = 2n .
n n
The subsets can also be grouped by size. There are 0 subsets with 0 elements, 1 subsets with
Page 3 of 20
, UNISA | MAT3707 Discrete Mathematics: Combinatorics
n
1 element, and so on until n . Adding all these subsets gives
n
X n
= 2n .
k
k=0
Page 4 of 20
