CombinatoricsLib Reference

CombinatoricsLib.Combinatorics — discrete mathematics and combinatorics for Free Pascal.

Learning routes

Beginner route

Copy and run the counting quick start. It prints C(10,3) = 120 using an integer-returning static call. Small scalar counting operations do not allocate; generated permutations/combinations return managed arrays.

Common tasks and algorithm choice

Advanced route

Run example 08 for overflow-aware counts, prime factorisation, modular arithmetic, iterator-style permutations, and managed result arrays. It uses the same zero-based integer arrays introduced by the beginner route.

---

Quick Start

uses CombinatoricsLib.Combinatorics;



begin

  WriteLn('C(10,3) = ', TCombinatoricsKit.Combination(10, 3));

end.

Expected output:

C(10,3) = 120

All methods are class static — no Create/Free needed.

---

Counting & Combinations

Catalan numbers — what they count

The n-th Catalan number counts many equivalent things:

• Valid sequences of n pairs of brackets: ((())), (()()), …
• Full binary trees with n+1 leaves
• Triangulations of a convex (n+2)-gon
• Monotone lattice paths from (0,0) to (n,n) that don't cross the diagonal

Stirling numbers — cheat sheet

• StirlingFirst(n,k) — number of permutations of n with exactly k cycles
• StirlingSecond(n,k) — number of ways to partition n elements into k non-empty subsets
• BellNumber(n) = sum of StirlingSecond(n, k) for k = 1..n

---

Sequences & Pascal's Triangle

TCombinatoricsKit.Fibonacci(10)       // 55  (F_0=0, F_1=1, F_2=1, ...)

TCombinatoricsKit.Lucas(6)            // 18  (L_0=2, L_1=1, L_2=3, ...)

TCombinatoricsKit.PascalRow(5)        // [1, 5, 10, 10, 5, 1]

TCombinatoricsKit.PascalTriangle(4)   // rows 0..4

PascalTriangle(N)[i][k] = C(i, k). Row i sums to 2^i.

Fibonacci uses fast doubling — O(log N) multiplications, safe up to N=92. The largest safe Lucas index is 90.

---

Number Theory

GCD, LCM, Extended GCD

TCombinatoricsKit.GCD(12, 8)              // 4

TCombinatoricsKit.LCM(4, 6)              // 12



var X, Y: Int64;

G := TCombinatoricsKit.ExtendedGCD(35, 15, X, Y);

// G=5, and 35*X + 15*Y = 5  (Bezout's identity)

Modular arithmetic

TCombinatoricsKit.ModPow(2, 10, 1000)    // 24   (2^10 mod 1000)

TCombinatoricsKit.ModInverse(3, 11)      // 4    (3*4 ≡ 1 mod 11)

ModInverse raises ECombinatoricsError when GCD(A,M) ≠ 1.

Primality

TCombinatoricsKit.IsPrime(999999937)     // True

TCombinatoricsKit.NextPrime(100)         // 101

IsPrime uses Miller-Rabin with bases 2, 3, 5, 7, 11, 13, and 17. This witness set is deterministic for N < 341,550,071,728,321. Do not extrapolate the guarantee to the full Int64 range.

Factorisation & Sieve

// 360 = 2³ × 3² × 5

factors := TCombinatoricsKit.PrimeFactors(360);

// factors[0] = (Prime=2, Exponent=3)

// factors[1] = (Prime=3, Exponent=2)

// factors[2] = (Prime=5, Exponent=1)



primes := TCombinatoricsKit.Sieve(100);  // all 25 primes <= 100

Sieve stores one Boolean per integer through Limit; its memory use is O(Limit), not a packed one-bit-per-number representation.

Euler's Totient

TCombinatoricsKit.EulerTotient(12)   // 4   (1, 5, 7, 11 are coprime to 12)

TCombinatoricsKit.EulerTotient(7)    // 6   (prime: φ(p) = p-1)

---

Permutation & Combination Generation

Enumerate all permutations

// Option 1 — get all at once (only practical for N <= 10)

perms := TCombinatoricsKit.Permutations(TIntegerArray.Create(1,2,3));

// 6 permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]



// Option 2 — step one at a time (memory efficient, any N)

perm := TIntegerArray.Create(1, 2, 3, 4);

repeat

  ProcessPermutation(perm);

until not TCombinatoricsKit.NextPermutation(perm);

NextPermutation uses Knuth's Algorithm L and returns False (resetting to first) when the last permutation is reached. Permutations allocates Length(Items)! rows. Repeated input values therefore produce repeated rows rather than only the distinct permutations.

All K-combinations

// All 2-element subsets of {0,1,2,3}

combos := TCombinatoricsKit.Combinations(4, 2);

// [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]

Power set

subsets := TCombinatoricsKit.PowerSet(3);

// 8 subsets of {0,1,2}: [], [0], [1], [0,1], [2], [0,2], [1,2], [0,1,2]

Limited to N <= 24 (produces 16M subsets at N=24 — use a generator for larger N).

---

Error Handling

try

  TCombinatoricsKit.Factorial(21);   // overflows Int64

except

  on E: ECombinatoricsError do

    WriteLn(E.Message);

end;

ECombinatoricsError is raised for:

• negative N or K on counting/generation functions whose domain requires them
• K > N for Permutation, Combination
• Factorial(N > 20) or CatalanNumber(N > 30) or BellNumber(N > 18) — Int64 overflow
• ModInverse when GCD(A,M) ≠ 1
• ModPow with M <= 0
• PrimeFactors(N <= 1)
• Sieve(Limit < 2)
• Sieve limits that exceed the platform's addressable dynamic-array size
• PowerSet(N > 24)

ModPow rejects negative exponents and uses overflow-safe modular multiplication across the accepted Int64 modulus range. LCM, multinomial, Stirling, derangement, Fibonacci, Lucas, and prime-bound arithmetic perform explicit overflow checks and raise ECombinatoricsError rather than wrapping. These APIs still return fixed-width integers; they are not arbitrary-precision arithmetic routines.

---

Overflow Reference

For larger values use LogFactorial / LogCombination which return Double.

---

Dependencies

• MathBase.SharedTypes — TIntegerArray
• MathBase.Precision — GammaLn, used by LogFactorial

No other external libraries required.