Discrete Math · Lab 04 — Atom of Recursion

Module 01 · Combinatorics

Stirling — Factorial Approximation & Numbers of the 2nd Kind

Stirling Numbers · S(n,k) 2nd Kind

S(n,k) counts ways to partition an n-set into k non-empty unlabeled blocks. Recurrence: S(n,k) = k·S(n−1,k) + S(n−1,k−1).

n

5

k

2

S(n,k) = 25

Bell number B(5) = total partitions = 52

Factorial Approximation n!

n! ≈ √(2πn) · (n/e)ⁿ · log form is numerically stable for any n.

n

10

Exact n!

3,628,800

Stirling

—

Ramanujan

—

Stirling + 1/12n

—

Err Stirling

—

Err Ramanujan

—

Err Series

—

Ratio n!/Stirling

—

Relative Error · log scale

ln(n!) Growth

Bound

|ln(n!) − Stirling| / |ln(n!)| < 1 / (12n)

Module 02 · Computability

Ackermann — Recursion Beyond Primitive Loops

Interactive Heatmap A(m,n)

m

2

n

3

Multiplication

Closed Form

2n+3

A(m,n)

9

Recursive Calls

—

Growth · log₁₀ A(m,n)

Recursive Calls (no memo)

Step-by-Step Expansion

Press Visualize to expand the recursion tree.

Inverse Ackermann α(n) Tarjan Union-Find

α(n) = min { m : A(m, m) ≥ n } grows so slowly that for every n in our universe, α(n) ≤ 4.

Definition

A(0, n) = n + 1
A(m, 0) = A(m − 1, 1)
A(m, n) = A(m − 1, A(m, n − 1))

Module 03 · Game Theory

Nim — Sprague–Grundy Strategy Game

Variant

Difficulty

Score · You · AI

0 · 0

Configuration

Board

Take

1

Sprague–Grundy

A position is losing for the mover ⇔ XOR of all (Grundy) heap values = 0.
Classic: g(h) = h. Bounded(K): g(h) = h mod (K + 1).

Discrete MathematicsLaboratory04 · Complexity

Stirling — Factorial Approximation & Numbers of the 2nd Kind

Ackermann — Recursion Beyond Primitive Loops

Nim — Sprague–Grundy Strategy Game

Discrete Mathematics
Laboratory04 · Complexity