Combinatorics • Topic 5

Sets

Set theory provides the language for all modern mathematics. In combinatorics, we focus on the size of sets (cardinality) and the relationships between subsets.

Notation

$x \in A$ : $x$ is an element of set $A$ .
$A \subseteq B$ : $A$ is a subset of $B$ (every element of $A$ is in $B$ ).
$\emptyset$ : The empty set (contains no elements).
$∣ A ∣$ : The cardinality (number of elements) of $A$ .

Subsets and Power Sets

Definition (Power Set)

The power set of

S

, denoted

P (S)

, is the set of all subsets of

S

Theorem (Number of Subsets)

∣ S ∣ = n

, then the number of subsets of

S

∣ P (S) ∣ = 2^{n}

Proof (Combinatorial Proof). To form a subset, we make a binary choice for each of the $n$ elements: either include it or exclude it. $2 \times 2 \times \dots \times 2 = 2^{n}$ choices. ∎

Disjoint Sets and Partitions

Disjoint: $A \cap B = \emptyset$ .
Partition: A collection of disjoint non-empty subsets $S_{1}, \dots, S_{k}$ whose union is the original set $S$ .

Example: Even and Odd integers partition $Z$ .

Practice Problems

Exercise (Problem 1)

Let

S = {1, 2, 3, 4, 5}

. How many subsets of

S

contain the element 1?

Exercise (Problem 2)

How many subsets of

{1, 2, \dots, 10}

have an odd number of elements?

Exercise (Problem 3)

Let

A

and

B

be subsets of a set

U

with

∣ U ∣ = 100

. If

∣ A ∣ = 50

and

∣ B ∣ = 70

, what are the minimum and maximum possible values for

∣ A \cap B ∣