CombinatoricsExample.java

package Combinatorics;

public class CombinatoricsExample {

    public static void main(String[] args) {

        // Initialize with max n value you'll need
        Combinatorics comb = new Combinatorics(100);

        System.out.println("=== Factorials ===");
        System.out.println("5! = " + comb.factorial(5));  // 120
        System.out.println("10! (mod 10^9+7) = " + comb.factorial(10));

        System.out.println("\n=== Combinations (nCr) ===");
        System.out.println("C(5, 2) = " + comb.nCr(5, 2));  // 10 ways to choose 2 from 5
        System.out.println("C(10, 3) = " + comb.nCr(10, 3)); // 120 ways to choose 3 from 10
        System.out.println("C(20, 10) = " + comb.nCr(20, 10)); // large combination

        // Direct calculation (no modulo, for small values)
        System.out.println("C(10, 3) direct = " + Combinatorics.nCrDirect(10, 3)); // 120

        System.out.println("\n=== Permutations (nPr) ===");
        System.out.println("P(5, 2) = " + comb.nPr(5, 2));  // 20 ways to arrange 2 from 5
        System.out.println("P(10, 3) = " + comb.nPr(10, 3)); // 720 ways to arrange 3 from 10

        System.out.println("\n=== Modular Inverse ===");
        long a = 3, mod = 1000000007;
        long inv = Combinatorics.modInverse(a, mod);
        System.out.println("Inverse of 3 (mod 10^9+7) = " + inv);
        System.out.println("Verification: (3 * inv) mod 10^9+7 = " + ((a * inv) % mod)); // Should be 1

        System.out.println("\n=== Modular Exponentiation ===");
        System.out.println("2^10 mod 10^9+7 = " + Combinatorics.modPow(2, 10, mod));  // 1024
        System.out.println("3^100 mod 10^9+7 = " + Combinatorics.modPow(3, 100, mod));

        System.out.println("\n=== Pascal's Triangle (first 6 rows) ===");
        long[][] pascal = Combinatorics.pascalTriangle(6);
        for (int i = 0; i < pascal.length; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(pascal[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("\n=== Catalan Numbers ===");
        System.out.println("C(0) = " + comb.catalan(0));  // 1
        System.out.println("C(1) = " + comb.catalan(1));  // 1
        System.out.println("C(2) = " + comb.catalan(2));  // 2
        System.out.println("C(3) = " + comb.catalan(3));  // 5
        System.out.println("C(4) = " + comb.catalan(4));  // 14
        System.out.println("C(5) = " + comb.catalan(5));  // 42

        // Direct calculation (for small values, no modulo)
        System.out.println("\nCatalan(5) direct = " + Combinatorics.catalanDirect(5)); // 42

        System.out.println("\n=== Stars and Bars ===");
        // Distribute 5 identical items into 3 bins
        System.out.println("Ways to distribute 5 items into 3 bins = " + comb.starsAndBars(5, 3));
        // Distribute 10 identical items into 4 bins
        System.out.println("Ways to distribute 10 items into 4 bins = " + comb.starsAndBars(10, 4));

        System.out.println("\n=== Derangements ===");
        System.out.println("D(3) = " + comb.derangements(3));  // 2 (BCA, CAB)
        System.out.println("D(4) = " + comb.derangements(4));  // 9
        System.out.println("D(5) = " + comb.derangements(5));  // 44

        System.out.println("\n=== Common Interview Problems ===");

        // Problem 1: Ways to climb stairs (n steps, 1 or 2 steps at a time)
        // This is Fibonacci: F(n) = F(n-1) + F(n-2)
        System.out.println("Ways to climb 5 stairs = " + fibonacci(5)); // 8

        // Problem 2: Number of unique BSTs with n nodes = Catalan(n)
        System.out.println("Unique BSTs with 3 nodes = " + comb.catalan(3)); // 5

        // Problem 3: Valid parentheses combinations = Catalan(n)
        System.out.println("Valid parentheses with 3 pairs = " + comb.catalan(3)); // 5

        // Problem 4: Distribute n identical balls into k distinct boxes
        System.out.println("Ways to put 5 balls in 3 boxes = " + comb.starsAndBars(5, 3)); // 21
    }

    // Helper: Fibonacci (for stair climbing problem)
    private static long fibonacci(int n) {
        if (n <= 1) return 1;
        long a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            long temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}