Editing Combinatorics (section)

== <span style="color: #FFFFFF;">Applying</span> ==
'''Graph algorithms and combinatorial computations:'''
<syntaxhighlight lang="python">
import heapq
from collections import defaultdict, deque
from typing import Optional

# === Core Graph Representation ===
class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(dict)  # adj[u][v] = weight
        self.directed = directed
    
    def add_edge(self, u, v, weight=1):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight
    
    @property
    def vertices(self): return set(self.adj.keys())
    def degree(self, v): return len(self.adj[v])

# === Dijkstra's Shortest Path ===
def dijkstra(graph: Graph, source) -> dict:
    """Shortest paths from source to all vertices. O((V+E) log V)."""
    dist = {v: float('inf') for v in graph.vertices}
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph.adj[u].items():
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# === Kruskal's Minimum Spanning Tree ===
class UnionFind:
    def __init__(self, n): self.parent = list(range(n)); self.rank = [0]*n
    def find(self, x):
        while self.parent[x] != x: x = self.parent[x] = self.parent[self.parent[x]]
        return x
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

def kruskal_mst(n: int, edges: list) -> tuple[list, float]:
    """Minimum spanning tree. edges = [(weight, u, v)]. O(E log E)."""
    edges = sorted(edges)
    uf = UnionFind(n)
    mst, total = [], 0
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w)); total += w
    return mst, total

# === Graph Coloring (Greedy) ===
def greedy_coloring(graph: Graph) -> dict:
    """Greedy vertex coloring. Not necessarily optimal, but fast."""
    color = {}
    for v in sorted(graph.vertices, key=lambda x: -graph.degree(x)):  # Largest first
        neighbor_colors = {color[u] for u in graph.adj[v] if u in color}
        for c in range(len(graph.vertices)):
            if c not in neighbor_colors:
                color[v] = c; break
    return color  # Chromatic number ≤ max_color + 1

# === Combinatorics ===
from math import comb, factorial

def binomial_coefficient(n: int, k: int) -> int: return comb(n, k)

def count_permutations(n: int, k: int) -> int:
    """P(n,k) = n!/(n-k)!"""
    return factorial(n) // factorial(n - k)

def inclusion_exclusion_union(*sets) -> int:
    """Count |A₁ ∪ A₂ ∪ ... ∪ Aₙ| using inclusion-exclusion."""
    from itertools import combinations
    n = len(sets)
    total = 0
    for r in range(1, n + 1):
        for combo in combinations(range(n), r):
            intersection = set.intersection(*[sets[i] for i in combo])
            total += ((-1)**(r+1)) * len(intersection)
    return total

# Pigeonhole: demonstrate that in any 13 people, 2 share a birth month
print(f"Pigeonhole: 13 people, 12 months → {13 // 12 + 1} guaranteed to share a month")
print(f"C(52,5) = {comb(52,5):,} possible poker hands")
print(f"Permutations of 8 queens on 8 columns: {count_permutations(8,8):,}")
</syntaxhighlight>

; Key results and open problems
: '''Graph theory''' → Four Color Theorem · Euler/Hamilton path conditions · Menger's theorem · Ramsey theory
: '''Extremal combinatorics''' → Turán's theorem · Szemerédi regularity lemma · Green-Tao theorem
: '''Enumerative combinatorics''' → Catalan numbers · Stirling numbers · Polya enumeration
: '''Open problems''' → R(5,5) unknown · Hadwiger conjecture · Graceful tree conjecture
</div>

<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">