Permutations & Combinations — The r! Error in Interviews

Permutations and combinations show up in more places than most engineers realize — password-strength calculations, lottery odds, generating test data sets, cryptography key-space analysis, scheduling problems, and any time someone asks 'how many ways can these items be arranged or selected?' They are not just academic curiosities from a discrete math course. When an interviewer asks you to count arrangements or selections, they are probing whether you can model a problem mathematically before writing a single line of code — because brute-force enumeration scales catastrophically while a formula runs in O(1) and requires no additional memory.

The core problem both concepts solve is counting without actually listing. If you have 20 candidates for 3 roles and you start enumerating every possibility by hand, you will be there for hours. A formula gives you the exact count in seconds. More importantly, understanding the structure of the formula tells you whether order matters — and that reasoning is what separates a senior engineer's answer from a junior one. Interviewers at top companies are not testing whether you memorized the formula. They are testing whether you understand why the formula has the shape it does.

After working through this guide you will be able to identify whether a problem needs permutations or combinations before touching a formula, apply the correct formula confidently with a mental calculation shortcut that works on a whiteboard without a calculator, handle the edge cases that trip up prepared candidates under pressure, write code that generates the actual permutations or combinations when a problem requires the full list rather than just a count, and decompose compound counting problems into independent sub-problems using the AND-multiply and OR-add rules. These are the skills that move a counting answer from technically correct to genuinely impressive.

Why Counting Arrangements Is Not the Same as Counting Selections

Permutations and combinations are the two fundamental ways to count distinct outcomes from a set. A permutation counts ordered arrangements — swapping two items produces a new permutation. A combination counts unordered selections — swapping items does not change the combination. The core mechanic is the factor of r! (r factorial) that divides the permutation count to get the combination count: C(n,r) = P(n,r) / r!. This single factor is the most common source of errors in interviews and production code.

In practice, permutations grow factorially: P(10,5) = 30,240, while combinations grow more slowly: C(10,5) = 252. The key property is that order matters for permutations but not for combinations. When solving problems, you must decide whether the sequence of elements matters. If it does, use permutations; if not, use combinations. A common trap is treating a selection problem as a permutation problem, which overcounts by a factor of r!.

Use permutations when order matters: ranking, scheduling, password generation. Use combinations when order does not matter: lottery draws, team selection, feature flag toggles. In real systems, misapplying these concepts leads to incorrect probability calculations, flawed A/B test sizing, and wrong combinatorial logic in recommendation engines or fraud detection models.

The Factorial Foundation — Why Everything Starts With n!

Before permutations or combinations make sense, you need to feel what a factorial means — not just know that n! is defined as n × (n-1) × ... × 1. Factorial n is the number of ways to arrange n distinct items in a sequence. Three books on a shelf: the first slot has 3 choices, the second has 2 remaining, the third has 1. Multiply them: 3 × 2 × 1 = 6. That is 3!.

The cascading multiplication is not arbitrary. Each step you commit one item to a position, which removes it from the pool for subsequent positions. That shrinking pool is exactly what 'without replacement' means — and it is the default assumption in virtually every interview problem unless the problem explicitly says 'repetition is allowed.' When you see a problem that does allow repetition, the formulas change: ordered selections with repetition become n^r, not n!/(n-r)!.

Two edge cases you must have in your reflexes. First: 0! = 1, not 0. There is exactly one way to arrange zero items: do nothing. This is not a convention someone invented for convenience — it is required for the formulas to produce correct results at their boundaries. C(n,0) = n!/(0! × n!) = 1, which must be true because there is exactly one way to choose nothing from a group. If 0! were 0, every combination formula would divide by zero. Second: 1! = 1, which is obvious but worth confirming mentally when you substitute numbers. These two base cases are responsible for the majority of interview edge case failures in this topic area.

package io.thecodeforge.math;

import java.math.BigInteger;

public class FactorialCalculator {

    /**
     * Computes n! recursively for n up to 20 (fits within long).
     *
     * Base cases:
     *   0! = 1 — exactly one way to arrange nothing (do nothing)
     *   1! = 1 — trivially one arrangement
     *
     * Do NOT use this for n > 20 — long overflows silently at 21!.
     * For n > 20, use factorialBig() below.
     *
     * The negative-input guard is production hygiene — in an interview
     * context mention it verbally rather than adding a full exception.
     */
    public static long factorial(int n) {
        if (n < 0) throw new IllegalArgumentException("Factorial undefined for negative input: " + n);
        if (n == 0 || n == 1) return 1L;
        return (long) n * factorial(n - 1);
    }

    /**
     * BigInteger version for n > 20.
     * Iterative (no stack overflow risk for large n).
     * Slower than long arithmetic but correct for arbitrarily large n.
     */
    public static BigInteger factorialBig(int n) {
        if (n < 0) throw new IllegalArgumentException("Factorial undefined for negative input: " + n);
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    public static void main(String[] args) {
        // Show growth rate — critical for understanding overflow risk
        System.out.println("Factorial growth and type boundaries:");
        for (int i = 0; i <= 12; i++) {
            System.out.printf("%2d! = %,d%n", i, factorial(i));
        }
        System.out.println();
        System.out.println("13! = " + factorialBig(13) + "  <- overflows int (max ~2.1B)");
        System.out.println("20! = " + factorialBig(20) + "  <- still fits long");
        System.out.println("21! = " + factorialBig(21) + "  <- overflows long silently");
        System.out.println("25! = " + factorialBig(25) + "  <- BigInteger required");
    }
}

Permutations — When Order Is Everything

A permutation answers: in how many ways can I select r items from n distinct items where the order of selection matters?

Formula: P(n,r) = n! / (n-r)!

The intuition behind the formula is worth understanding, not just memorizing. You have n choices for the first position. After filling the first position, n-1 remain for the second. After that, n-2 remain for the third. You continue until r positions are filled, leaving n-r items unused. Multiplying the choices for each position gives n × (n-1) × (n-2) × ... × (n-r+1). The division by (n-r)! in the formula is just a compact notation for canceling the lower portion of n! — the part you never actually use.

Real example: assigning gold, silver, and bronze medals to 3 of 8 athletes. The medal type matters — gold is not silver — so Alice winning gold and Bob winning silver is a different outcome from Bob winning gold and Alice winning silver. P(8,3) = 8!/5! = 8 × 7 × 6 = 336.

Notice the mental calculation: you do not compute 8! = 40,320 and 5! = 120 and then divide. You simply write the top 3 terms of 8! and stop. 8 × 7 = 56, then 56 × 6 = 336. That takes about five seconds. This cancellation shortcut is what makes permutation problems solvable at a whiteboard without a calculator, and demonstrating it fluently signals mathematical maturity to interviewers.

Two special cases worth knowing explicitly. When r = n, P(n,n) = n! — you are arranging all items, and this is the maximum possible count for any permutation problem. When r = 0, P(n,0) = 1 — there is exactly one way to make no selection at all. Both follow directly from the formula and both appear in interview edge case questions.

package io.thecodeforge.math;

import java.util.*;

public class PermutationCalculator {

    /**
     * Counts P(n,r) using the top-r-terms cancellation approach.
     *
     * This avoids computing n! and (n-r)! separately (which would overflow
     * for moderate n) by multiplying only the r terms that survive cancellation.
     *
     * P(n,r) = n × (n-1) × ... × (n-r+1)
     *
     * The loop runs from n down to (n-r+1), which is exactly r iterations.
     * Overflow risk: for n=20, r=20, this computes 20! which fits in long.
     * For n > 20, switch to BigInteger.
     *
     * Time: O(r), Space: O(1).
     */
    public static long countPermutations(int n, int r) {
        if (r < 0 || r > n) return 0L;
        if (r == 0) return 1L;
        long result = 1L;
        // Multiply the top r terms of n!: n × (n-1) × ... × (n-r+1)
        for (int i = n; i > n - r; i--) {
            result *= i;
        }
        return result;
    }

    /**
     * Generates all P(n,r) permutations of items using backtracking.
     *
     * Key difference from combination generation:
     *   - No startIndex parameter — every item is considered at every level
     *   - used[] array tracks which items are currently in the selection
     *   - Backtrack by removing from current and resetting used[i] = false
     *
     * Why used[] instead of startIndex?
     * Permutations allow [A,B] and [B,A] as distinct outputs — both must
     * appear. If we used startIndex (the combination approach), we would
     * skip B when A is first, preventing [B,A] from being generated.
     *
     * Time: O(P(n,r) × r) — P(n,r) permutations, each of size r to copy.
     * Space: O(r) recursion depth + O(P(n,r) × r) for stored results.
     */
    public static void generate(
        List<String> items,
        int r,
        List<String> current,
        boolean[] used,
        List<List<String>> results
    ) {
        if (current.size() == r) {
            results.add(new ArrayList<>(current)); // Copy — current is mutated
            return;
        }
        for (int i = 0; i < items.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                current.add(items.get(i));
                generate(items, r, current, used, results);
                // Backtrack: undo the choice made above
                current.remove(current.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        // Count-only: the formula approach, no generation
        System.out.println("P(8,3) = " + countPermutations(8, 3));  // 336
        System.out.println("P(10,0) = " + countPermutations(10, 0)); // 1 (edge case)
        System.out.println("P(5,5) = " + countPermutations(5, 5));  // 120 = 5!

        // Generate all P(3,2) permutations of [A, B, C]
        List<String> items = List.of("A", "B", "C");
        List<List<String>> results = new ArrayList<>();
        generate(items, 2, new ArrayList<>(), new boolean[items.size()], results);
        System.out.println("\nP(3,2) = " + results.size() + " permutations:");
        results.forEach(System.out::println);
    }
}

Combinations — When Order Doesn't Matter

A combination answers: in how many ways can I select r items from n distinct items where the order of selection is irrelevant?

Formula: C(n,r) = n! / (r! × (n-r)!)

The r! in the denominator is the only structural difference from the permutation formula — and it is the entire conceptual point. Every group of r selected items can be internally arranged in r! different sequences. Since we do not care about internal order, all r! of those sequences represent the same outcome and should be counted only once. Dividing by r! removes those duplicates. This is the precise mathematical meaning of 'order does not matter.'

Real example: a development team of 3 chosen from 8 candidates. You are building a group, not assigning roles, so a team of {Alice, Bob, Carol} is the same outcome regardless of the order in which you selected them. C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 336 / 6 = 56.

Two properties worth having in your reflexes. Symmetry: C(n,r) = C(n,n-r). Choosing 3 items from 8 is identical in count to leaving 5 items unchosen — the items you pick and the items you reject are mirror images of each other. This means C(20,18) should never be computed as choosing 18 from 20. It should immediately collapse to C(20,2) = (20 × 19) / (2 × 1) = 190. The symmetry property is a free performance win and a demonstration of mathematical fluency.

Boundary values: C(n,0) = 1 (one way to choose nothing) and C(n,n) = 1 (one way to choose everything). These follow directly from the formula and are worth verifying once mentally so the edge case handling in your code is not a surprise.

package io.thecodeforge.math;

import java.util.*;

public class CombinationCalculator {

    /**
     * Counts C(n,r) using incremental division to prevent overflow.
     *
     * The key insight: instead of computing numerator = n×(n-1)×...×(n-r+1)
     * and denominator = r! separately and dividing at the end (which overflows
     * for moderate n), we interleave the division inside the loop.
     *
     * At step i:
     *   - Multiply by (n - i + 1)  [next numerator term]
     *   - Divide by i               [divide by next denominator term]
     *
     * This works because C(n,r) is always an integer — the intermediate
     * values remain exact integers throughout the loop.
     *
     * Symmetry optimization: C(n,r) = C(n,n-r).
     * If r > n/2, we flip to n-r which has fewer iterations.
     * C(20,18) becomes C(20,2) — 2 iterations instead of 18.
     *
     * Safe for long up to approximately n = 62 with incremental division.
     * For n > 62, use BigInteger variant.
     *
     * Time: O(min(r, n-r)), Space: O(1).
     */
    public static long countCombinations(int n, int r) {
        if (r < 0 || r > n) return 0L;
        if (r == 0 || r == n) return 1L; // C(n,0) = C(n,n) = 1
        if (r > n / 2) r = n - r;         // Symmetry: always use smaller r
        long result = 1L;
        for (int i = 1; i <= r; i++) {
            result *= (n - i + 1); // Next numerator term
            result /= i;           // Divide by next denominator term
            // Division is exact at every step because C(n,r) is always integer
        }
        return result;
    }

    /**
     * Generates all C(n,r) combinations using backtracking with startIndex.
     *
     * The startIndex parameter is the key difference from permutation generation:
     *   - We only consider items at index >= startIndex
     *   - This ensures items are selected in strictly increasing index order
     *   - [A,B] appears exactly once; [B,A] is never generated
     *
     * Why does this prevent duplicates?
     * By enforcing forward-only selection, each unique subset can only be
     * constructed in one order — the one where lower-index items appear first.
     * All other orderings of the same subset are structurally unreachable.
     *
     * Contrast with permutation generation which uses used[] and no startIndex,
     * allowing [A,B] and [B,A] both to appear.
     *
     * Time: O(C(n,r) × r), Space: O(r) stack depth + O(C(n,r) × r) results.
     */
    public static void generate(
        List<String> items,
        int r,
        int startIndex,          // Only consider items at or after this position
        List<String> current,
        List<List<String>> results
    ) {
        if (current.size() == r) {
            results.add(new ArrayList<>(current));
            return;
        }
        for (int i = startIndex; i < items.size(); i++) {
            current.add(items.get(i));
            generate(items, r, i + 1, current, results); // i+1: never revisit earlier items
            current.remove(current.size() - 1);           // Backtrack
        }
    }

    public static void main(String[] args) {
        // Count-only: formula results
        System.out.println("C(8,3) = " + countCombinations(8, 3));   // 56
        System.out.println("C(52,5) = " + countCombinations(52, 5)); // 2,598,960 (poker hands)
        System.out.println("C(20,18) = " + countCombinations(20, 18)); // 190 via symmetry as C(20,2)
        System.out.println("C(10,0) = " + countCombinations(10, 0));  // 1 (edge case)
        System.out.println("C(10,10) = " + countCombinations(10, 10)); // 1 (edge case)

        // Generate all C(4,2) combinations of [A,B,C,D]
        List<String> items = List.of("A", "B", "C", "D");
        List<List<String>> results = new ArrayList<>();
        generate(items, 2, 0, new ArrayList<>(), results);
        System.out.println("\nC(4,2) = " + results.size() + " combinations:");
        results.forEach(System.out::println);
    }
}

Cracking the Interview Problem — Identify First, Formula Second

The most common interview failure in counting problems is not getting the formula wrong — it is applying the wrong formula because the order-matter diagnostic never happened. The formula you choose is a downstream consequence of the problem structure you identify. Train yourself to ask one question before touching any formula: does swapping the order of two selected items produce a different valid outcome?

If yes, it is a permutation. If no, it is a combination. Write this on the whiteboard. Say it out loud. Not because the interviewer needs you to explain basic reasoning, but because articulating the check makes it impossible to skip — and skipping it is exactly how candidates end up with answers that are 6x too large or 6x too small.

Let's work through a layered problem that interviewers use because it tests decomposition, not just formula recall: 'A company has 5 backend engineers and 4 frontend engineers. A project team must include exactly 2 backend and 2 frontend engineers. How many unique teams can be formed?'

Step 1 — Does order matter? No. A team is an unordered group. Swapping Alice and Bob within the backend selection produces the same team. Combination.

Step 2 — How many independent choices are there? Two: the backend selection AND the frontend selection. They are independent because the backend pool and frontend pool are separate — choosing from one does not affect the other.

Step 3 — Independent choices multiply. C(5,2) × C(4,2) = 10 × 6 = 60.

The AND-multiply rule is the key tool for compound problems. When choices are independent, the total count is the product of individual counts. When scenarios are mutually exclusive — either scenario A happens OR scenario B happens, never both — the total count is the sum. This AND-multiply / OR-add distinction resolves about 80% of compound counting problems without requiring any new conceptual machinery.

A harder variant: 'At least one of the two backend engineers chosen must be the team lead.' This adds a constraint. The most reliable approach for 'at least one' constraints is complementary counting — total teams minus teams with no team lead. Total: C(5,2) × C(4,2) = 60. Teams with no team lead (choosing 2 from the 4 non-lead backend engineers): C(4,2) × C(4,2) = 6 × 6 = 36. Answer: 60 - 36 = 24.

Complementary counting often produces simpler arithmetic than direct enumeration of the constrained cases. Recognize it as a pattern: whenever a problem says 'at least one' or 'at least two,' consider whether counting the complement (the cases where the condition fails) is easier.

package io.thecodeforge.math;

public class TeamFormationSolver {

    /**
     * Solves the compound team formation problem:
     *   - 5 backend engineers, choose exactly 2
     *   - 4 frontend engineers, choose exactly 2
     *   - Order does not matter in either group (combination, not permutation)
     *   - Choices are independent (AND condition → multiply)
     *
     * Demonstrates: decompose first, classify each sub-problem, combine results.
     */
    public static long uniqueTeams(
        int backendPool, int backendNeeded,
        int frontendPool, int frontendNeeded
    ) {
        long backendWays = CombinationCalculator.countCombinations(backendPool, backendNeeded);
        long frontendWays = CombinationCalculator.countCombinations(frontendPool, frontendNeeded);
        // AND condition between independent groups: multiply individual counts
        return backendWays * frontendWays;
    }

    /**
     * Variant with constraint: at least one backend engineer must be the team lead.
     *
     * Direct approach: count teams WITH team lead (fix team lead, choose 1 more from 4)
     * Complementary approach: total teams - teams WITHOUT team lead
     *
     * Both approaches give the same answer. Complementary is often simpler
     * arithmetic for 'at least one' problems — recognize this pattern.
     */
    public static long teamsWithTeamLead(
        int backendPool, int backendNeeded,
        int frontendPool, int frontendNeeded
    ) {
        long totalTeams = uniqueTeams(backendPool, backendNeeded, frontendPool, frontendNeeded);
        // Teams where team lead is NOT selected: choose backendNeeded from (backendPool - 1)
        long teamsWithoutLead = CombinationCalculator.countCombinations(backendPool - 1, backendNeeded)
                               * CombinationCalculator.countCombinations(frontendPool, frontendNeeded);
        // Complementary counting: at least one team lead = total - none
        return totalTeams - teamsWithoutLead;
    }

    public static void main(String[] args) {
        long total = uniqueTeams(5, 2, 4, 2);
        System.out.println("Total unique teams (no constraint): " + total);
        // C(5,2) = 10, C(4,2) = 6, total = 10 x 6 = 60

        long withLead = teamsWithTeamLead(5, 2, 4, 2);
        System.out.println("Teams with at least one team lead: " + withLead);
        // Total 60 - teams without lead C(4,2)*C(4,2) = 6*6 = 36 -> 60 - 36 = 24

        // Additional example: exclusive scenario counting (OR)
        // How many teams have EITHER all backend OR all frontend engineers (4-person team)
        long allBackend = CombinationCalculator.countCombinations(5, 4);
        long allFrontend = CombinationCalculator.countCombinations(4, 4);
        // OR between mutually exclusive scenarios: add individual counts
        System.out.println("4-person teams that are entirely one discipline (OR): "
            + (allBackend + allFrontend));
        // C(5,4)=5, C(4,4)=1, total = 5 + 1 = 6
    }
}

The Silent Killer: When Identical Items Break Your Count

You nailed the formula once you spot order matters. But here's where production incidents happen — when items aren't unique. New engineers treat 'ARRANGE' as a pure permutation, then ship the wrong answer that costs hours of debugging.

Why? Because n! assumes every element is distinguishable. Real-world data has duplicates: repeated letters in passwords, identical test fixtures, duplicate keys in distributed systems. Your formula must account for them.

How to fix: When you see identical items, divide by the factorial of each duplicate count. The formula becomes n! / (k1! × k2! × ...). The 'why' is symmetry — swapping two identical items doesn't change the arrangement. Your code must reflect that.

Interviewers love this. They'll throw 'MISSISSIPPI' or 'BOOKKEEPER' at you. Don't reach for n! like it's a hammer. Check for duplicates first. It's the difference between 3628800 and 34650 for 'MISSISSIPPI'.

// io.thecodeforge
public class PermutationWithDuplicates {
    // Compute permutations of "MISSISSIPPI" with duplicate letters
    public static long permuteWithDuplicates(String word) {
        int n = word.length();
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : word.toCharArray()) freq.merge(c, 1, Integer::sum);
        
        long total = factorial(n);
        for (int count : freq.values()) total /= factorial(count);
        return total;
    }
    
    private static long factorial(int x) {
        long result = 1;
        for (int i = 2; i <= x; i++) result *= i;
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(permuteWithDuplicates("MISSISSIPPI")); // Output: 34650
    }
}

The 'At Least' Trap — Why Complement Counting Saves Your Sanity

I've seen devs panic on 'how many ways to select a committee with at least 3 women from 10 men and 8 women'. They start enumerating cases: 3 women, 4 women, 5 women... up to 8. That works, but it's brittle and error-prone — exactly like hardcoding config files.

Here's the senior move: when you hear 'at least', think complement. Total possibilities minus the cases you don't want. It collapses 6 separate calculations into one subtraction.

Why it works: Combinations sum to 2^n. The complement ('less than 3 women') is usually fewer terms — 0, 1, or 2 women in our example. That's three terms instead of six. Half the code, half the bugs.

How to execute: Compute total selections (C(18, k) for committee size k). Subtract selections with 0, 1, 2 women. Done. The interviewers who watch you do this will know you've fought production fires.

Use this technique when the problem says 'at least', 'at most', or 'not all'. It's the difference between a fragile loop and a one-line expression that survives code review.

// io.thecodeforge
public class CommitteeSelection {
    // Ways to select 5-person committee from 10 men, 8 women with at least 3 women
    public static long selectAtLeast3Women() {
        int total = 18;
        int size = 5;
        
        long totalWays = nCr(total, size);
        long invalidWays = 0;
        // Women count 0, 1, 2
        for (int w = 0; w <= 2; w++) {
            int m = size - w;
            if (m >= 0 && m <= 10) {
                invalidWays += nCr(8, w) * nCr(10, m);
            }
        }
        return totalWays - invalidWays;
    }
    
    private static long nCr(int n, int r) {
        if (r > n) return 0;
        long result = 1;
        for (int i = 1; i <= r; i++) {
            result = result * (n - i + 1) / i;
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(selectAtLeast3Women()); // Output: 9016
    }
}

Permutations with Repetition, Without Repetition, and Restrictions

Permutations are arrangements where order matters. The simplest case is permutations without repetition: given n distinct items, the number of ways to arrange r of them is P(n, r) = n! / (n-r)!. For example, arranging 3 books from 5 on a shelf: 5!/(2!) = 60. When repetition is allowed (e.g., PIN codes), the number of arrangements is n^r. For a 4-digit PIN from digits 0-9, that's 10^4 = 10,000. Restrictions often involve forced adjacency or separation. For instance, arranging 5 people such that two specific people sit together: treat them as a block, giving 4! * 2! = 48 arrangements. If they must not sit together, subtract the block count from total: 5! - 48 = 72. Another common restriction is arranging items with identical objects, which leads to dividing by factorials of repeated items. For example, arranging the letters of 'MISSISSIPPI': 11!/(4!4!2!) = 34,650. Always check whether repetition is allowed and whether items are distinct or identical.

import math

def permutations_no_repetition(n, r):
    return math.factorial(n) // math.factorial(n - r)

def permutations_with_repetition(n, r):
    return n ** r

def permutations_with_identical(n, counts):
    # counts is a list of frequencies of identical items
    denom = 1
    for c in counts:
        denom *= math.factorial(c)
    return math.factorial(n) // denom

# Example: arranging 5 people, 2 must sit together
n = 5
block_ways = math.factorial(4) * math.factorial(2)
total_ways = math.factorial(5)
restricted_ways = total_ways - block_ways
print(f"Total: {total_ways}, Together: {block_ways}, Not together: {restricted_ways}")

Combinations: Selection from Groups, Committees, Handshakes

Combinations count selections where order does not matter. The number of ways to choose r items from n distinct items is C(n, r) = n! / (r! (n-r)!). For example, forming a committee of 3 from 10 people: C(10,3) = 120. Handshake problems are classic: if each person shakes hands with every other exactly once, total handshakes = C(n,2). For 20 people, that's 190. When selecting from multiple groups, use the multiplication principle. For instance, choose 2 men from 5 and 3 women from 6: C(5,2) C(6,3) = 10 20 = 200. If a committee must include at least one woman from a group, use complement counting: total ways minus ways with no women. For 5 men and 6 women, committee of 4 with at least one woman: C(11,4) - C(5,4) = 330 - 5 = 325. Another variation is selecting items with restrictions like 'must include a specific person'. Then fix that person and choose the rest: C(n-1, r-1). For example, a committee of 4 that must include John from 10 people: C(9,3) = 84. Combinations are fundamental in probability, such as calculating lottery odds.

import math

def combinations(n, r):
    return math.comb(n, r)

# Example: committee of 3 from 10
print(f"Committee: {combinations(10, 3)}")

# Handshake: 20 people
print(f"Handshakes: {combinations(20, 2)}")

# At least one woman: 5 men, 6 women, committee of 4
total = combinations(11, 4)
no_women = combinations(5, 4)
print(f"At least one woman: {total - no_women}")

# Must include John: choose 3 from remaining 9
print(f"Include John: {combinations(9, 3)}")

Circular Permutations and Seating Arrangement Algebra

In circular permutations, arrangements are considered up to rotation. For n distinct items in a circle, the number of distinct arrangements is (n-1)!. This is because rotating the entire circle doesn't create a new arrangement. For example, seating 5 people around a round table: (5-1)! = 24. If the circle has fixed positions (like chairs labeled 1 to n), then it's linear: n!. But typical 'round table' problems imply unlabeled seats. When there are restrictions, like two people must sit together, treat them as a block, then arrange the block and remaining people in the circle: (n-1)! 2! for the block's internal order. For example, 6 people, two must sit together: (5-1)! 2! = 4! * 2 = 48. If they must not sit together, subtract from total: (6-1)! - 48 = 120 - 48 = 72. Another variation is arranging beads on a necklace, which can be flipped (reflection symmetry). For a necklace with n distinct beads, the number is (n-1)!/2. For example, 6 distinct beads: 5!/2 = 60. Always clarify whether rotations and reflections are considered distinct. In interviews, 'circular table' usually means rotations are same, reflections are distinct unless stated otherwise.

import math

def circular_permutations(n):
    return math.factorial(n - 1)

def necklace_permutations(n):
    return math.factorial(n - 1) // 2

# Example: seating 5 people around a table
print(f"Seating 5: {circular_permutations(5)}")

# 6 people, two together
n = 6
together = circular_permutations(5) * 2  # treat block as one, then internal order
print(f"Together: {together}")
not_together = circular_permutations(6) - together
print(f"Not together: {not_together}")

# Necklace with 6 beads
print(f"Necklace: {necklace_permutations(6)}")