Permutations & Combinations

Fundamental Principle of Counting

• Multiplication Principle: If one operation can be done in m ways and the next in n ways, then total ways = m × n.
• Addition Principle: If two operations are mutually exclusive and can be done in m and n ways, total ways = m + n.

Factorials

• n! = n × (n−1) × (n−2) × … × 1
• 0! = 1

Permutations

• Arrangement of objects where order matters.
• Permutations of n objects taken r at a time: ⁿPᵣ = n! / (n−r)!
• Permutations of n objects taken all at a time: nPn = n!

Permutations with Repetition

• When p objects are alike, q alike, r alike: n! / (p! q! r!)
• Permutations of n objects taken r at a time with repetition: nʳ

Permutations under Conditions

• r specified objects fixed at r places: (n−r)!
• m specified objects fixed at given places (m < r): ⁿ⁻ᵐPᵣ⁻ᵐ
• A particular object always included: r · ⁿ⁻¹Pᵣ⁻¹
• A particular object never included: ⁿ⁻¹Pᵣ
• m specified objects always together: m! × (n−m+1)!
• m specified objects never together: n! − m!(n−m+1)!

Circular Permutations

• Around a round table (clockwise ≠ anticlockwise): (n−1)!
• Necklace/garland (clockwise = anticlockwise): (n−1)! / 2
• Circular permutations of n objects taken r at a time:
  • Clockwise ≠ anticlockwise: ⁿPᵣ / r
  • Clockwise = anticlockwise: ⁿPᵣ / (2r)

Combinations

• Selection of objects where order does not matter.
• Combinations of n objects taken r at a time: ⁿCᵣ = n! / [r!(n−r)!]
• ⁿCᵣ = ⁿCₙ₋ᵣ

Combinations with Repetition

• Selections of r objects from n objects with repetition: ⁿ⁺ʳ⁻¹Cᵣ

Restricted Combinations

• k particular objects always included: ⁿ⁻ᵏCᵣ⁻ᵏ
• k particular objects never included: ⁿ⁻ᵏCᵣ
• Arrangements with k fixed objects: ⁿ⁻ᵏCᵣ⁻ᵏ × r!

Selections from Identical Objects

• Selections from n identical objects (r ≤ n): 1
• Selections from p alike and q alike objects: (p+1)(q+1) − 1
• Selections from p, q, r alike objects: (p+1)(q+1)(r+1) − 1

Division & Distribution

• Divide (m+n) distinct objects into groups of m and n: (m+n)! / (m!n!)
• Divide n identical objects among r persons:
  • No restriction: ⁿ⁺ʳ⁻¹Cʳ⁻¹
  • Each gets at least one: ⁿ⁻¹Cʳ⁻¹

Derangement

• Number of derangements of n objects: !n = n! (1 − 1/1! + 1/2! − 1/3! + …)
• Exactly r objects at correct positions: n! / r! × [1 − 1/1! + 1/2! − … + (−1)^n−r / (n−r)!]

Important Results

• 1 + ⁿC₁ + ⁿC₂ + … + ⁿCₙ = 2ⁿ
• ⁿC₁ + ⁿC₂ + … + ⁿCₙ = 2ⁿ − 1
• Number of diagonals in n-gon: n(n−3)/2
• Exponent of prime p in n!: Eₚ(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + …

JEE Main Focus Areas

• Circular permutations
• Derangements
• Distribution of identical objects
• Exponent of prime in factorial
• Restricted arrangements