MATH10220 - Found. of Math. Comp. Sci II

What is a Cartesian product?

The Cartesian product A × B is the set of all ordered pairs (a,b) where a ∈ A and b ∈ B

What is the size formula for Cartesian products?

|A × B| = |A| · |B|, and for n sets: |A₁ × A₂ × ... × Aₙ| = |A₁| · |A₂| · ... · |Aₙ|

What is an ordered pair?

Elements of A × B written as (a,b) where order matters: (1,x) ≠ (x,1)

What is an ordered n-tuple?

Elements of A₁ × A₂ × ... × Aₙ written as (a₁,a₂,...,aₙ), also called strings or words

How many bytes are possible?

2⁸ = 256 different bytes (8 positions, each can be 0 or 1)

When does order matter vs not matter?

Order matters when objects are distinguishable (red die vs green die). Order doesn't matter when objects are indistinguishable (two green dice)

Two distinguishable dice, repetition allowed

Order important, repetition allowed: 6² = 36 outcomes

Two indistinguishable dice, repetition allowed

Order not important, repetition allowed: 21 outcomes

Two distinguishable dice, no repetition

Order important, repetition not allowed: 30 outcomes

Two indistinguishable dice, no repetition

Order not important, repetition not allowed: 15 outcomes

Key difference: ordered pairs vs sets

For ordered pairs: (x,y) ≠ (y,x) and (x,x) is valid. For sets: {x,y} = {y,x} and {x,x} = {x}

What is A × ∅?

A × ∅ = ∅ (empty set)

Example of Cartesian product

If A = {1,2,3} and B = {x,y}, then A × B = {(1,x),(1,y),(2,x),(2,y),(3,x),(3,y)}

What are the 4 counting categories?

1) Order matters, repetition allowed 2) Order matters, no repetition 3) Order doesn't matter, repetition allowed 4) Order doesn't matter, no repetitio