Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 36 · Getting Started

Sets and Counting Notation

Learn the set language of combinatorics: elements, subsets, cardinality, union, intersection, Cartesian product and the symbols you will see in every counting formula.

Counting problems are really questions about sets: collections of distinct objects. Before you can count cleverly, you need a small vocabulary. This lesson introduces the notation used in every later chapter, and each symbol comes with a Python equivalent you can run.

Sets and cardinality

A set is an unordered collection with no repeats. We write it with braces: {2, 4, 6}. An object inside is an element, written 4 ∈ A ("4 belongs to A"). The number of elements is the cardinality, written |A|. So for A = {2, 4, 6}, |A| = 3. The empty set, written ∅ or {}, has |∅| = 0.

Two facts matter at once. Order does not matter ({1, 2} = {2, 1}), and repeats do not count ({1, 1, 2} = {1, 2}). If you want order or repeats, you need a different object, such as a list or a multiset, which later lessons cover.

Python Sets in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Subsets

B ⊆ A means every element of B is also in A; B is a subset of A. Every set has at least two subsets: the empty set and itself. A set with n elements has exactly 2^n subsets, which we prove in Counting Functions and Subsets. For now, check small cases: {a, b} has the four subsets ∅, , , {a, b}.

A subset with exactly k elements is a k-subset. Counting k-subsets is the job of combinations.

Union, intersection and difference

Given sets A and B:

Symbol Name Meaning
A ∪ B union elements in A or B (or both)
A ∩ B intersection elements in both
A \ B difference elements in A but not in B
A^c complement everything in the universe not in A

Two sets with A ∩ B = ∅ are disjoint. When sets overlap, simply adding their sizes counts the overlap twice. That is the seed of inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|.

Python Union, intersection and the overlap

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Cartesian product and ordered tuples

The Cartesian product A × B is the set of all ordered pairs (a, b) with a in A and b in B. Its size is |A| · |B|, the basis of the product rule. Order matters in a pair: (1, 2) ≠ (2, 1). A product of k copies, A^k, is the set of k-tuples.

Python's itertools.product builds exactly this set. You met it with the pizza menu earlier.

Python Cartesian product

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Useful number sets and notation

  • ℕ = {0, 1, 2, ...} or {1, 2, ...} depending on the book; we state which we use.
  • [n] = {1, 2, ..., n} is a handy shorthand: "the set of the first n positive integers".
  • n! ("n factorial") is n · (n-1) · … · 1, with 0! = 1.
  • Σ adds a list of terms, Π multiplies them.
  • ⌊x⌋ rounds down, ⌈x⌉ rounds up.

When a problem is hard, rewrite it as "count the elements of this set". Naming the set precisely, with its conditions, is half the solution.

Diagram: two overlapping sets

flowchart LR
    A["A only"] --- AB["A and B<br/>(intersection)"] --- B["B only"]

The middle region belongs to both sets, which is why simple addition counts it twice.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is |{3, 3, 5, 7}|?

    Repeats do not count in a set, so it is {3, 5, 7} with 3 elements.
  2. 2. If |A| = 6, |B| = 4 and |A ∩ B| = 2, what is |A ∪ B|?

    6 + 4 - 2 = 8. The overlap was counted twice, so subtract it once.
  3. 3. How many elements are in A × B when |A| = 3 and |B| = 5?

    Each of the 3 elements pairs with each of the 5, giving 15 ordered pairs.
  4. 4. Which statement is true for sets?

    The empty set vacuously satisfies the subset condition for every set.

Summary

  • A set is an unordered collection of distinct elements; |A| is its size.
  • Union, intersection, difference and complement combine sets.
  • Overlaps are double-counted by plain addition: |A ∪ B| = |A| + |B| - |A ∩ B|.
  • The Cartesian product has size |A| · |B|; Python's itertools.product builds it.

Next: Counting by Brute Force with Python