🎲 Permutations, Combinations & Probability

Day 3 | ⏱️ Part of 3-Hour Advanced Quant Block | TCS Interview Prep

📌 Subtopics

Permutations

• Arrangements of objects (order matters)
• Permutations with repetition
• Circular permutations

Combinations

• Selections of objects (order doesn’t matter)
• Combinations with restrictions

Probability

• Basic probability (favorable/total outcomes)
• Addition and multiplication rules
• Independent & dependent events
• Conditional probability basics

📖 Comprehensive Notes

1. Permutations (Arrangements)

Permutation is an arrangement of a set of objects in a specific order. Order matters.

• Without Repetition: Number of ways to arrange $r$ objects from a set of $n$ distinct objects: $nPr = \frac{n!}{(n-r)!}$
  • Arrangement of $n$ distinct objects in a row: $n!$.
• With Repetition: Number of arrangements of $n$ objects where $p$ are of one kind, $q$ of another, and $r$ of another: $\text{Arrangements} = \frac{n!}{p! \times q! \times r!}$
• Circular Permutations: Number of ways to arrange $n$ distinct objects in a circle: $\text{Circular arrangements} = (n - 1)!$
  • If the direction (clockwise vs. counter-clockwise) does not matter (e.g., beads in a necklace): $\text{Arrangements} = \frac{(n-1)!}{2}$

Example: In how many ways can the letters of the word “APPLE” be arranged? Total letters $n = 5$. ‘P’ is repeated $2$ times ($p = 2$). $\text{Ways} = \frac{5!}{2!} = \frac{120}{2} = 60$ ways.

2. Combinations (Selections)

Combination is a selection of items from a group. Order does not matter.

• Formula: Number of ways to select $r$ items from $n$ distinct items: $nCr = \frac{n!}{r!(n-r)!} = \frac{nPr}{r!}$
• Properties:
  • $nCr = nC(n-r)$
  • $nC0 = nCn = 1$
  • $nC1 = n$

Example: In how many ways can a committee of $3$ members be chosen from a group of $8$ people? $n = 8$, $r = 3$. $8C3 = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$ ways.

3. Probability Basics & Rules

Probability is the measure of the likelihood that an event will occur. $\text{Probability of an event } P(E) = \frac{\text{Favorable Outcomes}}{\text{Total Outcomes}}$

• Range: $0 \le P(E) \le 1$.
• Complement: $P(E) + P(E') = 1$ (where $E'$ is the event that $E$ does not occur).
• Addition Rule: For any two events $A$ and $B$: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
  • For mutually exclusive events ($P(A \cap B) = 0$): $P(A \cup B) = P(A) + P(B)$.
• Multiplication Rule: For independent events $A$ and $B$: $P(A \cap B) = P(A) \times P(B)$

Example: A card is drawn at random from a pack of $52$ cards. Find the probability that it is a King or a Heart. Total cards $= 52$. $P(\text{King}) = 4/52$, $P(\text{Heart}) = 13/52$. $P(\text{King } \cap \text{ Heart}) = 1/52$ (the King of Hearts). $P(\text{King } \cup \text{ Heart}) = \frac{4}{52} + \frac{13}{52} - \frac{1}{52} = \frac{16}{52} = \frac{4}{13}$.

4. Conditional Probability

Conditional probability is the probability of event $A$ occurring, given that event $B$ has already occurred. $P(A | B) = \frac{P(A \cap B)}{P(B)}$

Example: A die is rolled. If the number shown is odd (event B), what is the probability that it is a prime number (event A)? Out of $6$ outcomes:

• Odd numbers $\{1, 3, 5\} \implies P(B) = 3/6 = 1/2$.
• Prime numbers $\{2, 3, 5\}$.
• Odd and Prime $\{3, 5\} \implies P(A \cap B) = 2/6 = 1/3$.
• $P(A | B) = \frac{1/3}{1/2} = \frac{2}{3}$.

🌐 Learning Resources

✅ Practice Links

📝 Key Formulas

PERMUTATIONS:
  nPr = n! / (n-r)!
  Circular = (n-1)!
  With repetition: n! / (p! × q! × r!)

COMBINATIONS:
  nCr = n! / (r! × (n-r)!)
  nCr = nC(n-r)
  nC0 = nCn = 1

PROBABILITY:
  P(E) = Favorable outcomes / Total outcomes
  0 ≤ P(E) ≤ 1
  P(E) + P(E') = 1
  P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
  P(A ∩ B) = P(A) × P(B)  [if independent]

🔗 Related Topics

• Logical Venn Diagrams — Union and intersection sets map directly to probability addition rules
• Statistics — Standard deviation and expected values of distributions are built on probability
• Dynamic Programming — Combinatorial counting problems (e.g., unique paths) are solved using DP
• Arrays and Hashing — Algorithms for generating permutations and subsets of arrays
• Greedy Number Theory and Bit Manipulation — Binary counting and combinatorics concepts