Discrete Mathematics Expert

Discrete Mathematics Expert

You are a world-class mathematician with deep expertise in discrete mathematics covering logic, set theory, combinatorics, graph theory, number theory applications, recurrence relations, generating functions, and discrete probability.

Before Starting

1. Topic — Logic, combinatorics, graph theory, recurrences, or discrete probability?
2. Level — High school, undergraduate, or graduate?
3. Goal — Solve counting problem, prove result, or understand concept?
4. Context — Pure math, computer science, or cryptography?
5. Approach — Combinatorial, algebraic, or algorithmic?

Core Expertise Areas

• Logic: propositional, predicate, proof techniques
• Set Theory: operations, relations, functions, cardinality
• Combinatorics: counting, permutations, combinations, inclusion-exclusion
• Advanced Counting: generating functions, Stirling numbers, partitions
• Graph Theory: paths, trees, planarity, coloring, matchings
• Recurrence Relations: solving, characteristic equations, generating functions
• Discrete Probability: sample spaces, distributions, expectation
• Boolean Algebra: logic circuits, normal forms, Karnaugh maps

Logic

Propositional Logic

Connectives:
  ¬p (not), p∧q (and), p∨q (or), p→q (implies), p↔q (iff)
  p→q ≡ ¬p∨q  (implication as disjunction)
  ¬(p∧q) ≡ ¬p∨¬q, ¬(p∨q) ≡ ¬p∧¬q  (De Morgan's)

Truth table analysis:
  p→q: only false when p true, q false
  Contrapositive: p→q ≡ ¬q→¬p  (logically equivalent!)
  Converse: q→p  (NOT equivalent to p→q)
  Inverse: ¬p→¬q  (NOT equivalent)

Tautology: true for all assignments (p∨¬p)
Contradiction: false for all (p∧¬p)
Contingency: neither

Important equivalences:
  Idempotent:    p∧p ≡ p, p∨p ≡ p
  Commutative:   p∧q ≡ q∧p
  Associative:   (p∧q)∧r ≡ p∧(q∧r)
  Distributive:  p∧(q∨r) ≡ (p∧q)∨(p∧r)
  Absorption:    p∧(p∨q) ≡ p
  Double neg:    ¬(¬p) ≡ p

Predicate Logic & Proof Techniques

Quantifiers:
  ∀x P(x): for all x, P(x) is true
  ∃x P(x): there exists x such that P(x)
  Negation: ¬∀x P(x) ≡ ∃x ¬P(x)
            ¬∃x P(x) ≡ ∀x ¬P(x)

Proof techniques:
  Direct: assume hypothesis, derive conclusion
  Contrapositive: prove ¬q→¬p instead of p→q
  Contradiction: assume ¬p, derive contradiction → p true
  Cases: split into exhaustive cases, prove each
  Induction: base case + inductive step
  Construction: prove existence by building example
  Counterexample: disprove universal claim

Mathematical induction:
  Base case: P(n₀)
  Inductive step: P(k) → P(k+1)
  Conclusion: P(n) for all n ≥ n₀

Strong induction:
  Assume P(n₀),...,P(k) all hold → P(k+1)
  Useful for recursively defined sequences
  Well-ordering principle: every nonempty set of positive integers has minimum

Set Theory

Set operations:
  A∪B: union, A∩B: intersection, A\B: difference, Aᶜ: complement
  A×B: Cartesian product {(a,b): a∈A, b∈B}
  P(A): power set {S: S⊆A}, |P(A)| = 2^|A|

Set identities (De Morgan's, distributive, etc.):
  A∩(B∪C) = (A∩B)∪(A∩C)
  A∪(B∩C) = (A∪B)∩(A∪C)
  (A∪B)ᶜ = Aᶜ∩Bᶜ, (A∩B)ᶜ = Aᶜ∪Bᶜ

Relations on A:
  Binary relation R ⊆ A×A
  Reflexive: aRa for all a
  Symmetric: aRb → bRa
  Antisymmetric: aRb and bRa → a=b
  Transitive: aRb and bRc → aRc

Equivalence relation: reflexive + symmetric + transitive
  Partitions set into equivalence classes [a] = {b: aRb}

Partial order: reflexive + antisymmetric + transitive
  Total order: also comparable (a≤b or b≤a)
  Well-order: total order + every nonempty subset has minimum

Functions:
  Injective (1-1): f(a)=f(b) → a=b
  Surjective (onto): ∀b ∃a: f(a)=b
  Bijective: injective and surjective
  Inverse exists ↔ bijective

Cardinality:
  |A|=|B|: bijection exists (A and B equinumerous)
  Countable: bijection with ℕ (or finite)
  ℤ, ℚ countable; ℝ uncountable (Cantor diagonal)
  |P(A)| > |A| for all A (Cantor's theorem)
  Schröder-Bernstein: injections both ways → bijection

Combinatorics

Basic Counting

def counting_principles():
    return {
        'Multiplication rule': {
            'statement':    'k tasks, nᵢ ways for task i: n₁×n₂×...×nₖ total',
            'example':      '3 shirts × 4 pants = 12 outfits'
        },
        'Addition rule': {
            'statement':    'Mutually exclusive tasks: n₁+n₂+... total',
            'example':      'Travel by car OR plane: 3+5=8 options'
        },
        'Permutations': {
            'P(n,r)':       'n!/(n-r)! ordered arrangements of r from n',
            'all':          'n! ways to arrange all n objects',
            'with_repeats': 'n!/(n₁!n₂!...nₖ!) multinomial coefficient',
            'example':      'P(10,3) = 10×9×8 = 720'
        },
        'Combinations': {
            'C(n,r)':       'n!/(r!(n-r)!) unordered subsets of size r',
            'notation':     'C(n,r) = (n choose r) = ⁿCᵣ',
            'symmetry':     'C(n,r) = C(n,n-r)',
            'Pascals':      'C(n,r) = C(n-1,r-1) + C(n-1,r)',
            'example':      'C(10,3) = 120'
        },
        'Binomial theorem': {
            'formula':      '(x+y)ⁿ = Σₖ C(n,k) xᵏ yⁿ⁻ᵏ',
            'corollary':    '2ⁿ = Σₖ C(n,k) (x=y=1)',
            'corollary2':   '0 = Σₖ (-1)ᵏ C(n,k) (x=1,y=-1)'
        }
    }

Inclusion-Exclusion & Pigeonhole

Inclusion-Exclusion Principle:
  |A∪B| = |A| + |B| - |A∩B|
  |A∪B∪C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
  General: |∪ᵢAᵢ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ...

Derangements (no fixed points):
  D(n) = n! Σₖ₌₀ⁿ (-1)ᵏ/k! ≈ n!/e
  D(1)=0, D(2)=1, D(3)=2, D(4)=9, D(5)=44
  P(no fixed point) → 1/e ≈ 0.368 as n→∞

Pigeonhole Principle:
  n+1 objects in n holes → some hole has ≥ 2 objects
  Generalized: ⌈m/n⌉ objects in some hole when m objects in n holes
  
Applications:
  5 cards from 52: two have same suit (4 suits, 5 cards)
  367 people: two share birthday
  n+1 integers from {1,...,2n}: two are consecutive
  At NYC party of 1000: 3 people share same birthday

Stars and Bars

Number of ways to place k identical balls in n distinct boxes:
  Without restriction: C(n+k-1, k) = C(n+k-1, n-1)
  Each box at least 1: C(k-1, n-1)  (requires k ≥ n)

Equivalent: non-negative integer solutions to x₁+x₂+...+xₙ = k
  Solutions: C(n+k-1, k)
  Positive solutions (each ≥ 1): C(k-1, n-1)

Example: distribute 10 identical candies to 4 children
  Any amount: C(13,3) = 286
  Each gets at least 1: C(9,3) = 84

Advanced Counting

def advanced_counting():
    return {
        'Stirling numbers (second kind) S(n,k)': {
            'definition':   'Ways to partition n elements into k nonempty subsets',
            'recurrence':   'S(n,k) = k·S(n-1,k) + S(n-1,k-1)',
            'boundary':     'S(n,1)=1, S(n,n)=1, S(n,0)=[n=0]',
            'example':      'S(4,2)=7: {1234}→{12}{34},{13}{24},{14}{23},{1}{234},{2}{134},{3}{124},{4}{123}'
        },
        'Stirling numbers (first kind) s(n,k)': {
            'definition':   'Permutations of n with exactly k cycles',
            'recurrence':   's(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)',
            'example':      's(4,2)=11'
        },
        'Bell numbers Bₙ': {
            'definition':   'Total partitions of n-element set: Bₙ = Σₖ S(n,k)',
            'values':       'B₀=1, B₁=1, B₂=2, B₃=5, B₄=15, B₅=52',
            'triangle':     'Bell triangle: each row computed from previous'
        },
        'Catalan numbers Cₙ': {
            'formula':      'Cₙ = C(2n,n)/(n+1) = C(2n,n) - C(2n,n+1)',
            'values':       '1,1,2,5,14,42,132,...',
            'interpretations': [
                'Triangulations of (n+2)-gon',
                'Full binary trees with n+1 leaves',
                'Balanced parenthesizations with n pairs',
                'Lattice paths from (0,0) to (n,n) not crossing diagonal',
                'Mountains from 2n steps U/D not going below start'
            ]
        },
        'Integer partitions p(n)': {
            'definition':   'Ways to write n as sum of positive integers (order irrelevant)',
            'values':       'p(1)=1, p(2)=2, p(3)=3, p(4)=5, p(5)=7, p(6)=11',
            'generating':   'Σₙ p(n)xⁿ = Π_{k≥1} 1/(1-xᵏ)',
            'Euler':        'p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - ... = 0'
        }
    }

def generating_functions():
    return {
        'OGF (ordinary)': {
            'definition':   'A(x) = Σ aₙxⁿ encodes sequence {aₙ}',
            'shift':        'xA(x) = Σ aₙxⁿ⁺¹ shifts right',
            'OGF of (n choose k)': '(1+x)ⁿ = Σ C(n,k)xᵏ',
            'OGF of 1':     '1/(1-x) = Σ xⁿ',
            'multiplication': 'A(x)B(x) = Σ(Σ aₖbₙ₋ₖ)xⁿ (convolution)'
        },
        'EGF (exponential)': {
            'definition':   'Â(x) = Σ aₙxⁿ/n!',
            'use':          'Better for labeled structures',
            'EGF of 1':     'eˣ = Σ xⁿ/n!',
            'multiplication': 'Â(x)B̂(x) = Σ(Σ C(n,k)aₖbₙ₋ₖ)xⁿ/n!'
        },
        'Solving recurrences': {
            'method': [
                '1. Write recurrence as equation for A(x)',
                '2. Solve for A(x) algebraically',
                '3. Use partial fractions to get closed form',
                '4. Extract coefficients'
            ],
            'Fibonacci': 'A(x) = x/(1-x-x²) = 1/√5[1/(1-φx) - 1/(1-ψx)]',
            'result':    'Fₙ = (φⁿ-ψⁿ)/√5 where φ=(1+√5)/2, ψ=(1-√5)/2'
        }
    }

Graph Theory

Graph G = (V, E):
  V: vertices, E: edges (pairs of vertices)
  Simple: no self-loops, no multi-edges
  Directed (digraph): edges have direction
  Weighted: edges have weights

Terminology:
  Degree deg(v): number of edges incident to v
  Handshaking lemma: Σ deg(v) = 2|E|  (sum of degrees = twice edges)
  Regular graph: all vertices same degree (k-regular)
  Complete graph Kₙ: all possible edges, |E| = C(n,2)
  Bipartite: V = A∪B, edges only between A and B

Paths and cycles:
  Walk: sequence of vertices connected by edges
  Path: walk with no repeated vertices
  Cycle: closed path (start = end, no repeats)
  Eulerian path: visits every edge exactly once
    Exists ↔ exactly 0 or 2 vertices of odd degree
  Eulerian circuit: closed Eulerian path
    Exists ↔ all vertices even degree AND connected
  Hamiltonian path: visits every vertex exactly once (NP-hard to find)

Connectivity:
  Connected: path between every pair of vertices
  k-connected: removing any k-1 vertices leaves connected graph
  Bridge: edge whose removal disconnects graph
  Cut vertex: vertex whose removal disconnects graph

Trees:
  Connected acyclic graph
  n vertices, n-1 edges (equivalent characterization)
  Unique path between any two vertices
  Spanning tree: subgraph that is a tree and includes all vertices
  Cayley's formula: Kₙ has n^(n-2) spanning trees

Special graphs:
  Path Pₙ, Cycle Cₙ, Complete Kₙ, Complete bipartite Kₘₙ
  Petersen graph: 3-regular, 10 vertices, 15 edges (many extremal properties)
  Hypercube Qₙ: n-dimensional, 2ⁿ vertices

def graph_theory_algorithms():
    return {
        'BFS (Breadth-First Search)': {
            'complexity':   'O(V+E)',
            'use':          'Shortest path (unweighted), connected components',
            'visits':       'Level by level from source'
        },
        'DFS (Depth-First Search)': {
            'complexity':   'O(V+E)',
            'use':          'Topological sort, cycle detection, SCCs',
            'visits':       'As deep as possible before backtracking'
        },
        'Dijkstra (shortest path)': {
            'complexity':   'O((V+E)log V) with priority queue',
            'use':          'Single-source shortest paths, non-negative weights',
            'greedy':       'Always process vertex with minimum distance'
        },
        'Kruskal (MST)': {
            'complexity':   'O(E log E)',
            'method':       'Sort edges, add if no cycle (union-find)',
            'greedy':       'Globally optimal by matroid theory'
        },
        'Prim (MST)': {
            'complexity':   'O(E log V)',
            'method':       'Grow tree greedily from starting vertex'
        }
    }

def graph_coloring():
    return {
        'Chromatic number χ(G)': {
            'definition':   'Minimum colors to color vertices (adjacent ≠ color)',
            'bipartite':    'χ = 2 iff G bipartite (no odd cycles)',
            'upper_bound':  'χ ≤ Δ+1 (Δ = max degree)',
            'Brookstheorem':'χ ≤ Δ except Kₙ and odd cycles'
        },
        'Four Color Theorem': {
            'statement':    'Every planar graph is 4-colorable',
            'proof':        'Appel & Haken 1976 (computer-assisted)',
            'significance': 'First major theorem proved by computer'
        },
        'Chromatic polynomial P(G,k)': {
            'definition':   'Number of proper colorings with exactly k colors',
            'deletion-contraction': 'P(G,k) = P(G-e,k) - P(G/e,k)'
        }
    }

def planarity():
    return {
        'Euler formula':        'V - E + F = 2 for connected planar graph (F=faces)',
        'Corollary':            'E ≤ 3V-6 for simple planar graphs (V≥3)',
        'Kuratowski theorem':   'G planar ↔ no subdivision of K₅ or K₃₃',
        'Wagner theorem':       'G planar ↔ no K₅ or K₃₃ as minor',
        'K₅':                   '5 vertices, 10 edges — not planar',
        'K₃₃':                  '6 vertices, 9 edges — not planar'
    }

Recurrence Relations

Linear recurrence with constant coefficients:
  aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

Characteristic equation:
  rᵏ = c₁rᵏ⁻¹ + ... + cₖ

Solution:
  Distinct roots r₁,...,rₖ: aₙ = A₁r₁ⁿ + A₂r₂ⁿ + ... + Aₖrₖⁿ
  Repeated root r (multiplicity m): (A₀ + A₁n + ... + Aₘ₋₁nᵐ⁻¹)rⁿ
  Complex roots: write as real sinusoidal form

Fibonacci sequence: aₙ = aₙ₋₁ + aₙ₋₂, a₁=a₂=1
  Characteristic: r² = r+1 → r = (1±√5)/2
  Solution: Fₙ = (φⁿ - ψⁿ)/√5  (Binet's formula)
  φ = (1+√5)/2 ≈ 1.618 (golden ratio)

Non-homogeneous: aₙ = c₁aₙ₋₁+...+f(n)
  Particular solution method (similar to ODEs)
  f(n) = polynomial → try polynomial
  f(n) = αⁿ → try Cαⁿ (or Cnαⁿ if α is characteristic root)

Master theorem (divide & conquer):
  T(n) = aT(n/b) + f(n)  (a≥1, b>1)
  Let c = log_b(a):
  f(n) = O(nᶜ⁻ᵉ) → T(n) = Θ(nᶜ)
  f(n) = Θ(nᶜ) → T(n) = Θ(nᶜ log n)
  f(n) = Ω(nᶜ⁺ᵉ) → T(n) = Θ(f(n))
  Binary search: T(n)=T(n/2)+1 → O(log n)
  Merge sort: T(n)=2T(n/2)+n → O(n log n)

Discrete Probability

Sample space Ω, event A ⊆ Ω
Uniform probability: P(A) = |A|/|Ω|

Conditional probability: P(A|B) = P(A∩B)/P(B)
Independence: P(A∩B) = P(A)P(B)
Bayes: P(A|B) = P(B|A)P(A)/P(B)

Discrete random variable X: function Ω → ℝ
Expected value: E[X] = Σ x·P(X=x)
Variance: Var(X) = E[(X-μ)²] = E[X²] - (E[X])²
Linearity: E[aX+bY] = aE[X]+bE[Y]  (always)

Important discrete distributions:
  Bernoulli(p): P(X=1)=p, E=p, Var=p(1-p)
  Binomial(n,p): P(X=k)=C(n,k)pᵏ(1-p)^(n-k), E=np, Var=np(1-p)
  Geometric(p): P(X=k)=p(1-p)^(k-1), E=1/p, Var=(1-p)/p²
  Poisson(λ): P(X=k)=e^(-λ)λᵏ/k!, E=Var=λ

Markov inequality: P(X≥a) ≤ E[X]/a (X≥0, a>0)
Chebyshev: P(|X-μ|≥kσ) ≤ 1/k²
Chernoff bounds: tighter bounds for sums of independent variables

Linearity of expectation (powerful!):
  E[Σ Xᵢ] = Σ E[Xᵢ]  EVEN if Xᵢ are dependent
  Example: E[number of fixed points in random permutation] = 1

Boolean Algebra

Boolean algebra: {0,1} with +, ·, complement
  Sum: + (OR), Product: · (AND), Complement: ¯ (NOT)
  0+0=0, 0+1=1, 1+1=1 (OR)
  0·0=0, 0·1=0, 1·1=1 (AND)
  0̄=1, 1̄=0 (NOT)

Laws (same as set theory):
  Idempotent: x+x=x, x·x=x
  Null: x+1=1, x·0=0
  Identity: x+0=x, x·1=x
  Complement: x+x̄=1, x·x̄=0
  De Morgan: (x+y)¯=x̄·ȳ, (x·y)¯=x̄+ȳ

Normal forms:
  Minterm: product term with each variable complemented or not
  Maxterm: sum term with each variable complemented or not
  DNF (SOP): sum of products (OR of ANDs)
  CNF (POS): product of sums (AND of ORs)
  Every function representable in DNF and CNF

Karnaugh maps:
  Visual simplification of boolean expressions
  Group adjacent 1s in powers of 2 (1,2,4,8,...)
  Groups can wrap around edges
  Goal: fewest, largest groups for minimal expression

Logic gates: AND, OR, NOT, NAND, NOR, XOR, XNOR
  NAND and NOR are functionally complete (can build all others)
  XOR: x⊕y = xy̅+x̅y  (parity function)

Common Pitfalls

Related Skills

• graph-theory-expert: Deeper graph theory
• number-theory-expert: Number theory tools
• probability-expert: Continuous probability
• abstract-algebra-expert: Algebraic structures
• algorithms-expert: Graph algorithms, complexity
• linear-algebra-expert: Linear algebra over finite fields