Permutations and Combinations

Permutations and Combinations deal with counting arrangements and selections. These concepts are fundamental to probability.

Overview

graph TD
    A[Counting] --> B[Fundamental Principle]
    A --> C[Permutations]
    A --> D[Combinations]
    C --> C1[With Repetition]
    C --> C2[Without Repetition]
    D --> D1[Selection]
    D --> D2[Distribution]

Fundamental Principle of Counting

Multiplication Principle

If one task can be done in $m$ ways and another in $n$ ways, then both tasks can be done in $m \times n$ ways.

Addition Principle

If one task can be done in $m$ ways OR another in $n$ ways (mutually exclusive), then either task can be done in $m + n$ ways.

Factorial

$$n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1$$

Special cases:

• $0! = 1$
• $1! = 1$

Properties:

• $n! = n \times (n-1)!$
• $(n+1)! = (n+1) \times n!$

Permutations

Definition: Arrangement of objects where order matters.

Without Repetition

Number of ways to arrange $r$ objects from $n$ distinct objects:

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

Special cases:

• $^nP_n = n!$ (arrange all n objects)
• $^nP_1 = n$
• $^nP_0 = 1$

With Repetition

$$n^r$$

(each of r positions has n choices)

Circular Permutations

$$\boxed{(n-1)!}$$

If clockwise and anticlockwise are same (like necklace):

$$\frac{(n-1)!}{2}$$

Permutations with Repeated Objects

Arrangements of $n$ objects where $p$ are alike of one kind, $q$ alike of another:

$$\frac{n!}{p! \cdot q! \cdot ...}$$

Combinations

Definition: Selection of objects where order doesn’t matter.

$$\boxed{^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}}$$

Properties

1. $^nC_r = ^nC_{n-r}$ (symmetry)
2. $^nC_0 = ^nC_n = 1$
3. $^nC_1 = ^nC_{n-1} = n$
4. $^nC_r + ^nC_{r-1} = ^{n+1}C_r$ (Pascal’s triangle)

Relation

$$^nP_r = ^nC_r \times r!$$

Important Results

Selection from Different Groups

To select $r$ objects from $n$ different objects where $p$ are of one kind, $q$ of another (all alike within kind):

Use coefficient of $x^r$ in:

$$(1 + x + x^2 + ... + x^p)(1 + x + x^2 + ... + x^q)...$$

Division into Groups

Equal groups (distinguishable):

$$\frac{n!}{(r!)^k}$$

where $n = kr$

Equal groups (indistinguishable):

$$\frac{n!}{(r!)^k \cdot k!}$$

Derangements

Number of ways to arrange $n$ objects so that no object is in its original position:

$$D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + \frac{(-1)^n}{n!}\right)$$

Sum of All Numbers

Sum of all $n$-digit numbers formed using digits $d_1, d_2, ..., d_n$ (without repetition):

$$= (n-1)! \times (d_1 + d_2 + ... + d_n) \times \underbrace{111...1}_{n \text{ ones}}$$

Applications

Distribution of Objects

Objects	Boxes	Formula
Distinct	Distinct	$n^r$ (r objects, n boxes)
Identical	Distinct	$^{n+r-1}C_{r-1}$
Distinct	Identical	Stirling numbers

Handshakes/Diagonals

Handshakes among n people: $^nC_2 = \frac{n(n-1)}{2}$

Diagonals in n-gon: $^nC_2 - n = \frac{n(n-3)}{2}$

Points and Lines

Lines from n points (no 3 collinear): $^nC_2$

Triangles from n points (no 3 collinear): $^nC_3$

Practice Problems

1. In how many ways can letters of “ARRANGE” be arranged?

2. How many 4-digit numbers can be formed using digits 1, 2, 3, 4, 5 without repetition?

3. In how many ways can 8 people be seated around a circular table?

4. How many diagonals does a decagon have?

5. In how many ways can 12 identical balls be distributed in 3 distinct boxes?

Further Reading

• Binomial Theorem
• Probability