Combinatorics.java

package Combinatorics;

public class Combinatorics {

    private static final int MOD = 1000000007;
    private long[] fact;
    private long[] invFact;
    private int n;

    // Constructor: precompute factorials and inverse factorials up to n
    public Combinatorics(int n) {
        this.n = n;
        fact = new long[n + 1];
        invFact = new long[n + 1];
        precompute();
    }

    // Precompute factorials and inverse factorials
    private void precompute() {
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[n] = modInverse(fact[n], MOD);
        for (int i = n - 1; i >= 0; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }
    }

    // Factorial of n
    public long factorial(int n) {
        if (n > this.n) throw new IllegalArgumentException("n exceeds precomputed range");
        return fact[n];
    }

    // nCr (Combinations) - choosing r items from n
    public long nCr(int n, int r) {
        if (r > n || r < 0) return 0;
        if (n > this.n) throw new IllegalArgumentException("n exceeds precomputed range");
        return (fact[n] * invFact[r] % MOD) * invFact[n - r] % MOD;
    }

    // nPr (Permutations) - arranging r items from n
    public long nPr(int n, int r) {
        if (r > n || r < 0) return 0;
        if (n > this.n) throw new IllegalArgumentException("n exceeds precomputed range");
        return (fact[n] * invFact[n - r]) % MOD;
    }

    // Modular inverse using Fermat's Little Theorem (works when MOD is prime)
    // a^(-1) ≡ a^(MOD-2) (mod MOD)
    public static long modInverse(long a, long mod) {
        return modPow(a, mod - 2, mod);
    }

    // Modular exponentiation: (base^exp) % mod
    public static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }

    // Generate Pascal's Triangle up to n rows
    public static long[][] pascalTriangle(int n) {
        long[][] pascal = new long[n][];
        for (int i = 0; i < n; i++) {
            pascal[i] = new long[i + 1];
            pascal[i][0] = pascal[i][i] = 1;
            for (int j = 1; j < i; j++) {
                pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
            }
        }
        return pascal;
    }

    // nth Catalan number
    // Formula: C(n) = (2n)! / ((n+1)! * n!)
    // Or: C(n) = nCr(2n, n) / (n+1)
    public long catalan(int n) {
        if (2 * n > this.n) throw new IllegalArgumentException("n exceeds precomputed range");
        long numerator = nCr(2 * n, n);
        long denominator = n + 1;
        return (numerator * modInverse(denominator, MOD)) % MOD;
    }

    // Compute Catalan numbers without precomputation (for small n)
    public static long catalanDirect(int n) {
        if (n <= 1) return 1;
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += catalanDirect(i) * catalanDirect(n - 1 - i);
        }
        return result;
    }

    // Compute nCr without modulo (for small values)
    public static long nCrDirect(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0 || r == n) return 1;

        // Optimize: C(n,r) = C(n, n-r)
        if (r > n - r) r = n - r;

        long result = 1;
        for (int i = 0; i < r; i++) {
            result *= (n - i);
            result /= (i + 1);
        }
        return result;
    }

    // Stars and Bars: distribute n identical items into k bins
    // Formula: C(n + k - 1, k - 1)
    public long starsAndBars(int n, int k) {
        return nCr(n + k - 1, k - 1);
    }

    // Derangements: permutations where no element appears in its original position
    // Formula: D(n) = n! * Σ((-1)^i / i!) for i = 0 to n
    public long derangements(int n) {
        if (n == 0) return 1;
        if (n == 1) return 0;
        if (n == 2) return 1;

        long[] d = new long[n + 1];
        d[0] = 1;
        d[1] = 0;
        d[2] = 1;

        for (int i = 3; i <= n; i++) {
            d[i] = ((i - 1) * (d[i - 1] + d[i - 2])) % MOD;
        }

        return d[n];
    }
}