# Discrete Mathematics

> Discrete math fundamentals including combinatorics, graph theory, logic, set theory, algorithms, and number theory for computer science and cryptography.

- Skill: `neuralblitz/discrete-mathematics` (Agent Skill)
- Install (CLI): `npx skillmds@latest add neuralblitz/discrete-mathematics`
- Raw SKILL.md: https://api.skillmd.com/api/skills/neuralblitz/discrete-mathematics/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: AI & ML
- License: MIT
- Author: NeuralBlitz (https://skillmd.com/u/neuralblitz)
- Updated: 2026-09-22
- Page: https://skillmd.com/skills/neuralblitz/discrete-mathematics

---


# Discrete Mathematics

## What I Do

I provide comprehensive discrete mathematics tools including combinatorics, graph algorithms, logical reasoning, set operations, recurrence relations, and number theory operations essential for computer science and cryptography.

## When to Use Me

- Algorithm analysis and design
- Cryptography and security
- Network and graph problems
- Counting and combinatorics
- Logic and proof techniques
- Optimization problems

## Core Concepts

- **Combinatorics**: Permutations, combinations, binomial coefficients
- **Graph Theory**: Paths, cycles, connectivity, coloring
- **Logic**: Propositional logic, predicates, inference
- **Set Theory**: Operations, relations, functions
- **Number Theory**: Divisibility, primes, modular arithmetic
- **Recurrence Relations**: Linear recurrences, generating functions
- **Proof Techniques**: Induction, contradiction, direct proof
- **Asymptotic Analysis**: Big O, Omega, Theta notation

## Code Examples

### Combinatorics

```python
from math import comb, perm, factorial
import numpy as np

n, k = 10, 3

combinations = comb(n, k)
permutations = perm(n, k)
factorial_n = factorial(n)

print(f"C(10,3) = {combinations}")
print(f"P(10,3) = {permutations}")
print(f"10! = {factorial_n}")

def multinomial(n_list):
    total = sum(n_list)
    result = factorial(total)
    for n in n_list:
        result //= factorial(n)
    return result
```

### Graph Algorithms

```python
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(f"BFS order: {bfs(graph, 'A')}")
```

### Modular Arithmetic

```python
def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return (g, x, y)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None
    return x % m

print(f"Mod inverse of 17 mod 43: {mod_inverse(17, 43)}")
```

### Recurrence Relations

```python
from functools import lru_cache

@lru_cache(None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(f"Fibonacci(10): {fibonacci(10)}")

def solve_linear_recurrence(coeffs, initial, n):
    k = len(coeffs)
    dp = initial[:k]
    for i in range(k, n+1):
        next_val = sum(coeffs[j] * dp[i-j-1] for j in range(k))
        dp.append(next_val)
    return dp[n]
```

### Set Operations

```python
A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}
C = {1, 2}

union = A | B
intersection = A & B
difference = A - B
symmetric_diff = A ^ B

print(f"Union: {union}")
print(f"Intersection: {intersection}")
print(f"A - B: {difference}")
print(f"Symmetric diff: {symmetric_diff}")

def cartesian_product(set1, set2):
    return {(a, b) for a in set1 for b in set2}
```

## Best Practices

1. **Memoization**: Cache computed results for recursion
2. **Graph Representation**: Choose appropriate structure (adjacency list/matrix)
3. **Modular Arithmetic**: Use pow(a, -1, m) in Python 3.8+
4. **Combinatorial Growth**: Beware of factorial growth
5. **Algorithm Complexity**: Analyze time and space complexity

## Common Patterns

```python
# DFS with recursion
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# Topological sort (Kahn's algorithm)
def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    topo_order = []
    
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return topo_order
```

## Core Competencies

1. Combinatorics and counting
2. Graph algorithms and traversals
3. Modular arithmetic and number theory
4. Set operations and relations
5. Recurrence relations and dynamic programming