Permutations & Combinations

Permutations and Combinations deal with counting the number of ways to arrange or select objects from a collection. The fundamental distinction is: permutations count ordered arrangements, combinations count unordered selections.

Fundamental Principle of Counting (FPC):

• Multiplication Principle: If task 1 can be done in m ways and task 2 in n ways, both tasks together can be done in m * n ways (sequential/independent events).
• Addition Principle: If task 1 can be done in m ways OR task 2 in n ways (mutually exclusive), total ways = m + n.

Factorial Notation: n! = n * (n-1) * (n-2) * ... * 2 * 1, with 0! = 1 by convention. Key property: n! = n * (n-1)!

Permutations (nPr): The number of ways to arrange r objects from n distinct objects in a definite order. nPr = n!/(n-r)!, where 0 <= r <= n. Special cases: nPn = n! (arrange all n objects), nP₀ = 1, nP₁ = n.

Combinations (nCr or C(n,r)): The number of ways to select r objects from n distinct objects without regard to order. nCr = n!/[r!(n-r)!], where 0 <= r <= n. Key properties: nCr = nC(n-r), nC₀ = nCn = 1, nC₁ = n, nCr + nC(r-1) = (n+1)Cr (Pascal's identity).

Permutations with Repetition: If among n objects, p are of one kind, q of another, r of a third, then arrangements = n!/(p! * q! * r!).

Circular Permutations: n distinct objects in a circle = (n-1)! ways. If clockwise and anticlockwise are indistinguishable (e.g., necklace), it becomes (n-1)!/2.

Permutations with Restrictions:

• Objects always together: Treat the group as one unit, arrange, then arrange within the group.
• Objects never together: Total arrangements - arrangements with them together.
• Objects in specific positions: Fix those objects first, then arrange remaining.

Combinations with Repetition: Selecting r objects from n types with repetition allowed = C(n+r-1, r).

Distribution Problems:

• Distributing n identical objects into r distinct groups: C(n+r-1, r-1) (each group can be empty).
• Distributing n identical objects into r distinct groups (none empty): C(n-1, r-1).
• Distributing n distinct objects into r distinct groups: r^n ways.

Derangements: Arrangements where no object occupies its original position. D(n) = n! * [1 - $\frac{1}{1}$! + $\frac{1}{2}$! - $\frac{1}{3}$! + ... + (-1)^n/n!]

The key problem-solving concept is correctly identifying whether the problem requires permutation (order matters) or combination (order doesn't matter), accounting for identical objects, restrictions, and whether to use direct counting or complementary counting (total - unwanted).