Ch. 6 Notes: Sets, Cardinality, Multiplication, and Permutations

Sets and Set Operations

• A set is a well-defined collection of objects. Example: {1, 2, 3, 4} is a set; a list like ①31.2.3.44 is not a well-defined set in the notes but should be read as a collection of elements {1,2,3,4}.
• Set-builder notation: A = { x | x is a non-negative integer }. Also written as A = { x ∈ ℕ | x ≥ 0 }.
• A set consists of elements; an element is denoted by x, and x ∈ A means x is an element of A.
• Finite vs infinite sets: A finite set has finitely many elements; an infinite set has infinitely many elements (e.g., A = {0, 1, 2, 3, …}).
• The empty set: ∅ is a set with no elements.
• Well-defined object: An object must be clearly definable to be a set (e.g., a beautiful flower may not be well-defined as an object in some contexts).

Membership, Subsets, and Empty Set

• Membership: x ∈ A means x is an element of A. If y is not an element of A, y ∉ A.
• Subset relation: For sets A and B, B is a subset of A if every element of B is an element of A. Denoted as B ⊆ A (or A ⊇ B).
• The empty set ∅ is a subset of every set: ∅ ⊆ A for any A.
• Equality of sets: Two sets A and B are equal if they have exactly the same elements; order does not matter:
  • A = B iff every element of A is in B and every element of B is in A.

Universal Set, Complement, and Basic Identities

• The universal set U is the set that contains all the objects under consideration.
• The complement of A with respect to U is A^c = { x ∈ U | x ∉ A }.
• Fundamental identities:
  • A ∪ A^c = U
  • A ∩ A^c = ∅
• Notation variants: A^c is also written as U \ A or { x ∈ U | x ∉ A }.

Union, Intersection, and Venn Diagrams

• Union: A ∪ B = { x | x ∈ A or x ∈ B }.
• Intersection: A ∩ B = { x | x ∈ A and x ∈ B }.
• Subsets by example: If A = {1, 2, 3, 4, 5} and B = {1, 3, 4}, then B ⊆ A.
• Venn diagrams denote sets with regions; use U as the universe; you can shade A, B, A^c, A ∪ B, A ∩ B, and A^c ∩ B^c to visualize relations.
• Important: If A ⊆ B and B ⊆ A, then A = B.

Cardinality and Finite Sets (n(A))

• The number of elements of a finite set A is denoted by n(A).
• If A is finite, n(A) is a nonnegative integer. If A is infinite, n(A) is not defined in this context.
• Examples:
  • A = {1, 2, 3, 4, 5} ⇒ n(A) = 5.
  • B = {1, 4, 3, 6} ⇒ n(B) = 4.
  • U = {1, 2, 3, 4, 5, 6, 7, 8, 9} ⇒ n(U) = 9.

Cardinality: Union and Intersections (Inclusion-Exclusion for Two Sets)

• For finite sets A and B:
  • n(A ∪ B) = n(A) + n(B) − n(A ∩ B).
• Also, A ∪ A^c = U and A ∩ A^c = ∅, which reinforces the idea of a full coverage and disjoint complement.
• Example (illustrative): If U = {1,2,3,4,5,6,7,8,9}, A = {1,3,5,7,9}, B = {3,5,6,7,8}, then n(A ∪ B) and n(A ∩ B) can be computed via the formula above.

More on Venn Diagrams and Sets (Common Exercises)

• Given U and subsets A, B, compute A ∪ B, A ∩ B, A^c, B^c, and the complement relationships.
• Practice problems include: finding A, B, A ∩ B, A ∪ B, U, A^c, B^c, A ∪ B ∪ C, and A ∩ B ∩ C from Venn diagrams.

Homework and Practice Ideas (Representative Problems)

• Examples often involve finite U and subsets A, B, C to compute unions, intersections, complements and totals from a Venn diagram.
• Typical objectives:
  • Find A ∪ B, A ∩ B, A^c, B^c, U, and various combinations like A ∪ B ∪ C, A ∩ B ∩ C.
  • Verify identities like n(A ∪ A^c) = n(U) and n(A ∪ B) formulas.

Chapter 6.3: The Multiplication Principle (Product Rule)

• If there are m ways to perform task T1 and n ways to perform task T2, then there are m × n ways to perform T1 followed by T2.
• General idea: If there are N1 ways for T1, N2 ways for T2, …, Nm ways for Tm, then there are N1 × N2 × … × Nm ways to perform all tasks in sequence (generalized multiplication principle).

Concrete Examples (Multiplication Principle)

• Road problem: If there are 2 roads from Whitewater to Milwaukee and 3 roads from Milwaukee to Chicago, then the number of Whitewater→Milwaukee→Chicago routes is 2 × 3 = 6.
• Pasta and sauce: 6 varieties of pasta and 28 sauces ⇒ 6 × 28 = 168 combinations with one of each.
• Coin tossed three times: sequences of heads/tails; number of outcomes = $2^3 = 8$; tree diagram can illustrate all sequences.
• Coin tossed four times: number of outcomes = $2^4 = 16$; draw a tree diagram to list all sequences.
• Combination lock (3-number sequence): digits on a dial, first left, then right, then left again.
  • With 10 digits and allowing repetition: $10 imes 10 imes 10 = 1000$.
  • Without repetition: $10 imes 9 imes 8 = 720$.
  • If there are 15 digits on the dial, the number of possible 3-digit sequences without repetition is 15 imes 14 imes 13
    ight) and with repetition is $15^3$.
• Travel planning example: NY to PC (outward) has 7 options (5 planes + 2 trains); return has 3 options; total ways = $7 imes 3 = 21$.
• License plates (digits then letters): three digits followed by three letters. With repetition allowed: $10^3 imes 26^3$; Without repetition: $10 imes 9 imes 8 imes 26 imes 25 imes 24$.

Chapter 6.4: Permutations

• A permutation is an arrangement of objects in a definite order.
• The number of permutations of n distinct objects is n! (factorial). The number of permutations of n objects taken r at a time is
  • $P(n,r) = \frac{n!}{(n-r)!}.$
• Basic small-case examples:
  • For 2 elements {a,b}, there are 2! = 2 permutations: (a,b) and (b,a).
  • For 3 elements {a,b,c}, there are 3! = 6 permutations.
  • For P(4,2) = 4 × 3 = 12, e.g., list: ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc.
• Permutations with repeated elements (multiset permutations): If among n objects, n1 are of type 1, n2 of type 2, …, nk of type k (where n1 + n2 + … + nk = n), the number of distinct permutations is
  • $\frac{n!}{n<em>1! \, n</em>2! \, \cdots \, n_k!}.$
• Classic word examples:
  • WHITEWATER has 10 letters with W appearing 2 times, T appearing 2 times, and E appearing 2 times. Number of distinct permutations:
  • $\frac{10!}{2! \, 2! \, 2!}.$
  • ATLANTA has 7 letters with A appearing 3 times and T appearing 2 times. Number of distinct permutations:
  • $\frac{7!}{3! \, 2!}.$
• Applications and problems:
  • Number of permutations of a set A taken two at a time: $P(n,2) = n(n-1)$.
  • Number of ways to arrange a committee with 4 distinct positions from 8 members: $P(8,4) = 8\cdot 7\cdot 6\cdot 5 = 1680$.
  • General line-up problems: For a group photo of 6 people, number of arrangements in a row is $6! = 720$.
• Additional notes from exercises:
  • The factorial notation: $n! = n \times (n-1) \times \cdots \times 2 \times 1.$
  • The relation between permutations and combinations, and how to count with repeated letters in words.

Summary of Key Formulas (Quick Reference)

• Membership and sets:
  • x ∈ A, x ∉ A
• Complements and universals:
  • A^c = { x ∈ U | x ∉ A }
  • A ∪ A^c = U, A ∩ A^c = ∅
• Unions and intersections:
  • A ∪ B = { x | x ∈ A or x ∈ B }
  • A ∩ B = { x | x ∈ A and x ∈ B }
• Cardinalities (finite sets):
  • n(A): number of elements in A
  • If A finite, n(A) is finite; if infinite, n(A) is not defined here.
• Inclusion-Exclusion for two sets:
  • n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
• Product principle (multiplication rule):
  • If there are N1 ways for T1, N2 ways for T2, …, then total = N1 × N2 × … × Nm
• Permutations:
  • P(n,r) = \frac{n!}{(n-r)!}
  • n! = n × (n-1) × ⋯ × 1
• Permutations with repetition of objects with duplicates:
  • If there are n objects total with multiplicities n1, n2, …, nk (sum n), then
  • Distinct permutations = \frac{n!}{n1! n2! \cdots n_k!}
• Examples (words):
  • WHITEWATER: distinct permutations = $\frac{10!}{2!\,2!\,2!}$
  • ATLANTA: distinct permutations = $\frac{7!}{3!\,2!}$
• Applications and problems: everyday counting with Venn diagrams, coins, locks, licenses, and team lineups.

// End of summary notes