MAT3707 Assignment 2 2026 Solutions Due 28 July 2026

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