Permutations and Combinations

• Fundamental Principle of Counting

  • Multiplication Principle (Fundamental Counting Principle)
    • If an operation can occur in $m$ ways, and a second in $n$ ways, both occur in $m \times n$ ways.
  • Addition Principle
    • If an operation can occur in $m$ ways or $n$ ways (mutually exclusive), it occurs in $m + n$ ways.

• Factorial Notation

  • Definition: Product of first $n$ natural numbers, denoted as $n!$ or $\lfloor n$.
  • Formula: $n! = n \times (n-1) \times (n-2) \times \dots \times 1$.
  • Special Case: $0! = 1$.
  • Property: $n! = n \times (n-1)!$.

• Permutations

  • Definition: Arrangement of objects in a definite order.
  • Linear Permutation
    • Formula for $r$ objects out of $n$: $^{n}P_r = \frac{n!}{(n-r)!}$.
    • Permutation of all $n$ objects: $^{n}P_n = n!$.
  • Permutations with Repetition
    • Total arrangements when objects are repeated: $n^r$.
    • Permutation with identical objects: $\frac{n!}{p! q! r!}$.
  • Circular Permutations
    • Arrangements around a circle: $(n-1)!$.
    • Necklaces/Garlands (clockwise/anticlockwise same): $\frac{(n-1)!}{2}$.

• Combinations

  • Definition: Selection of objects where order does not matter.
  • Formula: $^{n}C_r = \frac{n!}{r!(n-r)!}$.
  • Relation between Permutation and Combination: $^{n}P_r = ^{n}C_r \times r!$.
  • Important Properties of Combinations
    • Complementary Rule: $^{n}C_r = ^{n}C_{n-r}$.
    • Pascal's Identity: $^{n}C_r + ^{n}C_{r-1} = ^{n+1}C_r$.
    • Equality Property: If $^{n}C_a = ^{n}C_b$, then $a = b$ or $a + b = n$.

• Important Problem Types & Applications

  • Formation of words (with and without meaning).
  • Seating arrangements (row and circle).
  • Selection of teams/committees.
  • Geometric problems (points on a plane, diagonals of polygons).
  • Division and distribution of objects into groups.