1.2 Set Theory and Combinatorial Structures

Set theory and combinatorics form the foundation of discrete mathematics. These concepts help us understand and manipulate collections of objects, from simple counting to complex problem-solving in various fields.

Mastering set operations and counting principles is crucial for tackling more advanced topics. These tools allow us to analyze and solve problems in computer science, probability, and other areas where discrete structures are fundamental.

Set Theory Fundamentals

Basics of set theory

Top images from around the web for Basics of set theory

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

• 

  Set Theory Basics | MA 124 Contemporary Mathematics View original

  Is this image relevant?

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

1 of 3

Top images from around the web for Basics of set theory

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

• 

  Set Theory Basics | MA 124 Contemporary Mathematics View original

  Is this image relevant?

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Set language and notation :: Maths View original

  Is this image relevant?

1 of 3

• Sets represent collections of distinct objects enclosed in curly braces {} (books on a shelf, numbers)
• Empty set contains no elements denoted by ∅ or {} (an empty box, a set of prime numbers between 12 and 14)
• Union combines elements from either or both sets using ∪ (fruits from two different baskets, students in two classes)
• Intersection finds elements common to both sets using ∩ (shared hobbies between friends, overlapping course requirements)
• Difference includes elements in the first set but not the second using \ (removing sold-out items from inventory, subtracting expenses from income)
• Complement contains elements not in a given set denoted by superscript ᶜ (non-members of a club, numbers outside a specified range)
• Subsets have every element contained within another set using ⊆ (even numbers within integers, a company's employees among a city's population)
  • Proper subsets ⊂ are subsets that are not equal to the original set (a soccer team's starters among all players, a strict subset of tools needed for a project)
• Cardinality counts the number of elements in a set denoted by |A| (number of cards in a deck, size of a class roster)
• Power set contains all subsets of a given set denoted by P(A) or 2^A (all possible combinations of toppings on a pizza, subsets of club members for committee assignments)
  • Power set cardinality equals 2 raised to the original set's cardinality |P(A)| = 2^|A| (a set of 3 elements has 2^3 = 8 subsets in its power set)

Combinatorial Structures and Counting

Types of combinatorial structures

• Permutations arrange objects in a specific order denoted by $P(n, r)$ or $nPr$ (arranging books on a shelf, ordering toppings on a pizza)
  • Permutation formula: $P(n, r) = \frac{n!}{(n-r)!}$ (calculating possible ways to select and arrange r objects from a set of n objects)
• Combinations select objects without regard to order denoted by $C(n, r)$, $nCr$, or $\binom{n}{r}$ (choosing team members from a group, selecting fruits for a basket)
  • Combination formula: $C(n, r) = \frac{n!}{r!(n-r)!}$ (calculating possible ways to select r objects from a set of n objects without considering order)

Application of counting principles

• Multiplication principle states that if event A can occur in m ways and event B can occur in n ways for each occurrence of A, then "A and B" can occur in m × n ways (outfit combinations with 3 shirts and 4 pants yields 3 × 4 = 12 possibilities)
• Addition principle states that if mutually exclusive events A and B can occur in m and n ways respectively, then "A or B" can occur in m + n ways (the number of ways to roll either an even or odd sum on two dice is 18 + 18 = 36)

Proof of combinatorial identities

• Binomial theorem expands $(x + y)^n$ using the formula $\sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$ (expanding $(2x + 3y)^4$ yields the sum of terms with coefficients determined by combinations)
• Pascal's identity relates combinations with consecutive parameters: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (calculating $\binom{7}{4}$ using $\binom{6}{3} + \binom{6}{4}$)
• Vandermonde's identity sums products of combinations: $\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$ (proving the number of ways to select a team of 5 from a group of 12 women and 8 men equals $\binom{20}{5}$)