🔶Intro to Abstract Math Unit 6 – Combinatorics and Discrete Math Basics

Key Concepts and Definitions

• Combinatorics involves the study of counting, arranging, and selecting elements from finite sets
• Discrete mathematics focuses on mathematical structures that are countable and distinct, such as integers, graphs, and logical statements
• Sets are collections of distinct objects, denoted using curly braces {a, b, c}
• Permutations refer to the different ways of arranging a set of objects in a specific order
• Combinations deal with the number of ways to select a subset of objects from a larger set, where order does not matter
• The binomial theorem expands the power of a binomial expression (a + b)^n
• Pascal's triangle is a triangular array of numbers that embodies the coefficients of the binomial expansion
• Probability quantifies the likelihood of an event occurring, expressed as a value between 0 and 1

Set Theory Fundamentals

• Sets are the foundation of modern mathematics and play a crucial role in combinatorics and discrete math
• Elements of a set are the distinct objects that make up the set (numbers, letters, symbols)
• Set notation includes curly braces {}, where elements are separated by commas
• The empty set, denoted as {} or ∅, contains no elements
• Subsets are sets entirely contained within another set (A is a subset of B if every element in A is also in B)
• Set operations include union (∪), intersection (∩), and complement (A')
  • Union combines elements from two or more sets (A ∪ B = {x | x ∈ A or x ∈ B})
  • Intersection includes elements common to all sets (A ∩ B = {x | x ∈ A and x ∈ B})
• Venn diagrams visually represent sets and their relationships using overlapping circles

Counting Principles

• The fundamental counting principle states that if an event can occur in m ways and another independent event can occur in n ways, the two events together can occur in m × n ways
• The sum rule applies when dealing with mutually exclusive events (events that cannot occur simultaneously)
  • If event A can occur in m ways and event B can occur in n ways, and A and B are mutually exclusive, then either A or B can occur in m + n ways
• The product rule is used when events are independent and can occur in succession
  • If event A can occur in m ways and event B can occur in n ways, and the events are independent, then the sequence of events A followed by B can occur in m × n ways
• The pigeonhole principle asserts that if n items are placed into m containers and n > m, then at least one container must contain more than one item
• Inclusion-exclusion principle calculates the number of elements in the union of two or more sets, accounting for overlaps
  • For two sets A and B: |A ∪ B| = |A| + |B| - |A ∩ B|

Permutations and Combinations

• Permutations count the number of ways to arrange n distinct objects in a specific order
  • The formula for permutations is: P(n, r) = n! / (n - r)!, where n is the total number of objects and r is the number of objects being arranged
• Combinations count the number of ways to select r objects from a set of n objects, where order does not matter
  • The formula for combinations is: C(n, r) = n! / (r! × (n - r)!), also written as $\binom{n}{r}$
• Permutations with repetition occur when objects can be repeated in the arrangement
  • The number of permutations with repetition is calculated as n^r, where n is the number of distinct objects and r is the number of positions
• Combinations with repetition count the number of ways to select r objects from n distinct objects, allowing for repetition and disregarding order
  • The formula for combinations with repetition is: $\binom{n+r-1}{r}$

Binomial Theorem and Pascal's Triangle

• The binomial theorem expands the power of a binomial expression (a + b)^n into a sum of terms
  • The general form is: $(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k$
• Pascal's triangle is a triangular array of numbers that represents the coefficients of the binomial expansion
  • Each number in the triangle is the sum of the two numbers directly above it
  • The nth row of Pascal's triangle contains the coefficients of the expansion of (a + b)^n
• The binomial coefficients $\binom{n}{k}$ can be found in Pascal's triangle at the intersection of the nth row and the kth diagonal
• Properties of Pascal's triangle include symmetry and the sum of entries in each row equaling a power of 2
• The binomial theorem and Pascal's triangle have applications in probability, algebra, and combinatorics

Probability Basics

• Probability is a measure of the likelihood that an event will occur, expressed as a number between 0 and 1
  • 0 represents an impossible event, while 1 represents a certain event
• The sample space (S) is the set of all possible outcomes of an experiment or random process
• An event (E) is a subset of the sample space, representing one or more outcomes of interest
• The probability of an event E is denoted as P(E) and calculated as the number of favorable outcomes divided by the total number of possible outcomes
• The complement of an event E, denoted as E' or E^c, consists of all outcomes in the sample space that are not in E
  • P(E') = 1 - P(E)
• Conditional probability P(A|B) is the probability of event A occurring given that event B has already occurred
  • Calculated as: P(A|B) = P(A ∩ B) / P(B)
• Independent events are events where the occurrence of one does not affect the probability of the other
  • For independent events A and B: P(A ∩ B) = P(A) × P(B)

Graph Theory Introduction

• A graph is a mathematical structure consisting of vertices (nodes) connected by edges (lines)
• Vertices represent objects or entities, while edges represent relationships or connections between them
• Graphs can be undirected (edges have no specific direction) or directed (edges have a specific direction, indicated by arrows)
• The degree of a vertex is the number of edges incident to it
  • In a directed graph, the in-degree is the number of incoming edges, and the out-degree is the number of outgoing edges
• A path is a sequence of vertices connected by edges, with no repeated vertices
• A cycle is a path that starts and ends at the same vertex
• A connected graph has a path between every pair of vertices
• A complete graph has an edge between every pair of vertices
• Trees are connected graphs with no cycles
  • A spanning tree is a subgraph that includes all vertices of the original graph and is a tree

Problem-Solving Strategies

• Break down complex problems into smaller, more manageable subproblems
• Look for patterns and similarities to previously solved problems
• Use concrete examples to understand abstract concepts and generalize solutions
• Employ visualization techniques like diagrams, graphs, or tables to represent and analyze data
• Consider multiple approaches and evaluate their efficiency and feasibility
• Utilize known formulas, theorems, and properties to simplify calculations and proofs
• Work backwards from the desired outcome to determine the necessary steps
• Apply the principle of mathematical induction for problems involving sequences or recursion
  • Base case: Prove the statement holds for the initial value (usually n = 0 or n = 1)
  • Inductive step: Assume the statement holds for n = k and prove it holds for n = k + 1
• Collaborate with peers to exchange ideas, insights, and alternative perspectives on challenging problems