🧠Thinking Like a Mathematician Unit 7 – Combinatorics and Graph Theory

Key Concepts and Definitions

• Combinatorics involves the study of counting, arranging, and selecting elements from finite sets
• Fundamental principle of counting states that if an event can occur in $m$ ways and another independent event can occur in $n$ ways, then the two events can occur together in $m \times n$ ways
• Permutations are arrangements of objects in a specific order, where the order matters
• Combinations are selections of objects from a set, where the order does not matter
• Graph theory studies the relationships and connections between objects, represented by vertices (nodes) and edges (lines or arcs)
• Degree of a vertex represents the number of edges connected to it
  • In-degree refers to the number of incoming edges
  • Out-degree refers to the number of outgoing edges
• Path is a sequence of vertices connected by edges, where no vertex is repeated
• Cycle is a path that starts and ends at the same vertex

Counting Principles and Techniques

• Addition principle applies when dealing with mutually exclusive events, where the total number of outcomes is the sum of the individual outcomes
• Multiplication principle applies when dealing with independent events, where the total number of outcomes is the product of the individual outcomes
• Inclusion-exclusion principle is used to count the number of elements in the union of two or more sets, accounting for overlaps
  • For two sets $A$ and $B$, $|A \cup B| = |A| + |B| - |A \cap B|$
  • For three sets $A$, $B$, and $C$, $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$
• Pigeonhole principle states that if $n$ items are placed into $m$ containers, with $n > m$, then at least one container must contain more than one item
• Binomial theorem expands the power of a binomial expression $(a + b)^n$, where the coefficients of the expansion are given by the binomial coefficients $\binom{n}{k}$

Permutations and Combinations

• Permutations count the number of ways to arrange $n$ distinct objects, taking $r$ at a time, denoted as $P(n, r)$ or $_{n}P_{r}$
  • Formula: $P(n, r) = \frac{n!}{(n-r)!}$, where $n!$ represents the factorial of $n$
• Combinations count the number of ways to select $r$ objects from a set of $n$ distinct objects, where the order does not matter, denoted as $C(n, r)$, $_{n}C_{r}$, or $\binom{n}{r}$
  • Formula: $C(n, r) = \frac{n!}{r!(n-r)!}$
• Permutations with repetition count the number of ways to arrange $n$ objects, where some objects may be repeated, denoted as $n^r$
• Combinations with repetition (stars and bars method) count the number of ways to select $r$ objects from $n$ distinct objects, allowing repetitions, denoted as $\binom{n+r-1}{r}$

Introduction to Graph Theory

• Graphs are mathematical structures used to model pairwise relationships between objects
• Undirected graphs have edges that do not have a specific direction, representing symmetric relationships
• Directed graphs (digraphs) have edges with specific directions, representing asymmetric relationships
• Weighted graphs have edges associated with weights or costs, representing the strength or value of the relationship
• Adjacent vertices are directly connected by an edge
• Incident edges are edges that connect to a specific vertex
• Complete graph is a graph where every pair of distinct vertices is connected by a unique edge
• Bipartite graph is a graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex from one set to a vertex in the other set

Types of Graphs and Their Properties

• Simple graph has no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices
• Multigraph allows multiple edges between the same pair of vertices
• Pseudograph allows both loops and multiple edges
• Regular graph has all vertices with the same degree
  • Complete graph is an example of a regular graph
• Connected graph has a path between every pair of vertices
• Disconnected graph has at least one pair of vertices with no path between them
• Tree is a connected graph with no cycles
  • Rooted tree has a designated root vertex, and the edges are directed away from the root
• Planar graph can be drawn on a plane without any edges crossing
• Euler's formula for planar graphs: $v - e + f = 2$, where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces

Graph Algorithms and Applications

• Breadth-first search (BFS) explores a graph level by level, visiting all neighbors of a vertex before moving to the next level
  • Applications include shortest path problems and web crawling
• Depth-first search (DFS) explores a graph by going as deep as possible along each branch before backtracking
  • Applications include topological sorting and detecting cycles
• Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights
• Kruskal's algorithm finds a minimum spanning tree in a weighted, connected graph by greedily selecting the edges with the smallest weights
• Prim's algorithm finds a minimum spanning tree by starting with a single vertex and greedily adding the nearest vertex to the tree
• Graph coloring assigns colors to vertices such that no two adjacent vertices have the same color
  • Applications include scheduling problems and map coloring

Problem-Solving Strategies

• Identify the type of counting problem (permutations, combinations, or other principles)
• Break down complex problems into smaller, manageable subproblems
• Use complementary counting when it is easier to count the complement of the desired set
• Utilize recurrence relations to solve problems involving sequences or recursive structures
• Apply graph theory concepts to model and solve real-world problems
• Look for patterns and symmetries in the problem to simplify the solution
• Consider using generating functions to solve counting problems involving sequences
• Utilize the binomial theorem and Pascal's triangle when dealing with binomial expansions and coefficients

Real-World Applications and Examples

• Combinatorics in cryptography (password strength, key space analysis)
• Graph theory in social networks (friend recommendations, influence propagation)
• Permutations in task scheduling and resource allocation
• Combinations in lottery and gambling probability calculations
• Graph algorithms in GPS navigation systems and route optimization
• Counting principles in probability theory and statistics
• Graph coloring in frequency assignment for mobile phone networks
• Minimum spanning trees in network design and optimization (power grids, communication networks)