Modern Math Cheatsheet

Permutations & Combinations

1.0 Fundamentals of Counting

This section establishes the logical foundation for all counting problems. A strong grasp of these principles often allows for solving complex problems from scratch, a vital skill for the CAT exam.

1.1 Factorial Notation

Definition: The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$.

$$ n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1 $$

Base Cases:

$$ 0! = 1 $$

$$ 1! = 1 $$

1.2 The Multiplication Principle

Principle: If a task A can be performed in $m$ ways, and for each of these ways, a subsequent task B can be performed in $n$ ways, then the total number of ways to perform task A followed by task B is $m \times n$.

1.3 The Addition Principle

Principle: If a task A can be performed in $m$ ways and another task B can be performed in $n$ ways, and the two tasks are mutually exclusive (i.e., they cannot be performed simultaneously), then the number of ways to perform either task A or task B is $m + n$.

2.0 Permutations (Arrangements)

Permutations deal with arrangements where the order of objects is critical.

2.1 Permutation of Distinct Objects (No Repetition)

Definition: The number of ways to arrange (permute) $r$ distinct objects chosen from a set of $n$ distinct objects.

$$ ^n P_r = \frac{n!}{(n-r)!} $$

Arranging all n objects:

$$ ^n P_n = n! $$

2.2 Permutation of Items That Are Not All Distinct

Principle: When arranging $n$ items, if some are identical, the total number of permutations is reduced. We must divide by the factorial of the count of each group of identical items to eliminate overcounting.

$$ \text{Number of arrangements} = \frac{n!}{p_1! \times p_2! \times \dots \times p_k!} $$

2.3 Permutation with Repetition Allowed

Principle: If $r$ items are to be arranged from $n$ distinct items, and repetition is allowed, each of the $r$ positions can be filled in $n$ ways.

$$ \text{Number of arrangements} = n^r $$

2.4 Conditional Permutations

Items Always Together (Block Method): To arrange $n$ items where $m$ specific items must always be together, treat the $m$ items as a single "block". Arrange this block and the other $n-m$ items. Then, arrange the $m$ items within the block.

$$ \text{Total Ways} = (n-m+1)! \times m! $$

Items Never Together (Subtraction Method):

$$ \text{Total Arrangements} - \text{Arrangements where they are Together} $$

2.5 Circular Permutations

Arrangement of n distinct items (e.g., people at a table):

$$ \text{Number of ways} = (n-1)! $$

Arrangement of n distinct items where clockwise and anti-clockwise are indistinguishable (e.g., necklaces, garlands):

$$ \text{Number of ways} = \frac{(n-1)!}{2} \quad (\text{for } n > 2) $$

3.0 Combinations (Selections)

Combinations deal with selections where the order of objects is irrelevant.

3.1 Combination of Distinct Objects

Definition: The number of ways to select (choose) $r$ objects from a set of $n$ distinct objects, where order does not matter.

$$ ^n C_r = \frac{n!}{r!(n-r)!} $$

3.2 Key Properties of $^nC_r$

Symmetry: $ ^nC_r = ^nC_{n-r} $
Pascal's Identity: $ ^nC_r + ^nC_{r-1} = ^{n+1}C_r $
Boundary Cases: $ ^nC_0 = 1 $ and $ ^nC_n = 1 $

3.3 Conditional Combinations

k particular items are always included: Choose the remaining $r-k$ items from the remaining $n-k$ items. Ways = $ ^{n-k}C_{r-k} $
k particular items are never included: Choose all $r$ items from the remaining $n-k$ items. Ways = $ ^{n-k}C_r $

3.4 Total Selections

From Distinct Items: The total number of ways to select zero or more items from a set of $n$ distinct items is $2^n$.
Selecting at least one item: $ 2^n - 1 $
From Items Not All Distinct: If there are $p$ items of one kind, $q$ of a second kind, and $r$ of a third kind, the total number of ways to select one or more items is:

$$ \text{Ways} = (p+1)(q+1)(r+1) - 1 $$

4.0 Derangements

Definition: A derangement is a permutation of objects such that no object occupies its original position.
Full Derangement ($D_n$): The number of ways to derange $n$ items.

$$ D_n = n! \left[ \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!} \right] $$

Partial Derangement: The number of ways that exactly $k$ items are in their correct positions.

$$ \text{Total Ways} = ^nC_k \times D_{n-k} $$

Probability

5.0 Fundamentals of Probability

$$ P(E) = \frac{\text{Number of Favorable Outcomes}}{\text{Total Number of Possible Outcomes}} $$

Probability Range: For any event E, $ 0 \le P(E) \le 1 $.
Complementary Events: The probability that event E does not occur is $P(E')$.

$$ P(E') = 1 - P(E) $$

Addition Rule (Union of Events): For any two events A, B:

$$ P(A \cup B) = P(A) + P(B) - P(A \cap B) $$

Multiplication Rule (Intersection of Events): For independent events A, B:

$$ P(A \cap B) = P(A) \times P(B) $$

6.0 Conditional Probability & Bayes' Theorem

Conditional Probability: The probability of event A occurring, given that event B has already occurred.

$$ P(A|B) = \frac{P(A \cap B)}{P(B)}, \text{ where } P(B) \neq 0 $$

Bayes' Theorem: Used to "reverse" conditionality.

$$ P(B|A) = \frac{P(A|B) \times P(A)}{P(B)} $$

Binomial Distribution (Bernoulli Trials): Probability of exactly $r$ successes in $n$ trials.

$$ P(X=r) = ^nC_r \times p^r \times (1-p)^{n-r} $$