📚 Permutations & Combinations – Advanced University‑Level Study Notes
Prepared for MAT – Quantitative Ability (MIT‑style, first principles)
1. Foundations
| Symbol | Definition | Example |
|---|---|---|
| (n) | Total number of distinct objects | 5 letters in “APPLE” |
| (r) | Number of objects chosen/arranged | 3 letters out of 5 |
| (\mathcal{P}(n,r)) | Number of ordered arrangements (permutations) | (\mathcal{P}(5,3) = 5·4·3 = 60) |
| (\mathcal{C}(n,r)) | Number of unordered selections (combinations) | (\mathcal{C}(5,3) = 10) |
1.1 Counting Principle (Rule of Product)
If an experiment consists of (k) independent stages, where stage (i) has (n_i) possible outcomes, the total number of outcomes is
[
N = \prod_{i=1}^{k} n_i.
]
Proof: By induction on (k).
Base case (k=1): trivial.
Inductive step: For (k+1) stages, combine last two stages: (n_k n_{k+1}) choices for the last two stages; multiply by (\prod_{i=1}^{k-1} n_i). ∎
2. Permutations
2.1 Basic Formula
For (n) distinct objects, the number of permutations of all (n) objects is [ n! = n \cdot (n-1) \cdot \dots \cdot 1. ]
For partial permutations (choosing (r) of the (n) objects and ordering them): [ \boxed{\mathcal{P}(n,r)=\frac{n!}{(n-r)!}} \tag{1} ]
Derivation:
- Choose first element: (n) choices.
- Choose second: (n-1) choices.
- …
- Choose (r)th: (n-r+1) choices.
Multiply: (n(n-1)\dots(n-r+1) = \frac{n!}{(n-r)!}).
2.2 Edge Cases
| Scenario | Formula | Remarks |
|---|---|---|
| (r=0) | (\mathcal{P}(n,0)=1) | Empty permutation (one way to do nothing). |
| (r=n) | (\mathcal{P}(n,n)=n!) | All objects used. |
| (r>n) | (\mathcal{P}(n,r)=0) | Impossible to select more than available. |
2.3 Repetition Allowed
If repetition is allowed and we still choose (r) items, each of the (r) positions can be filled in (n) ways: [ n^r. ] (See Section 3.2 for details.)
2.4 Restricted Permutations (Derangements)
A derangement is a permutation with no element in its original position.
Let (D_n) be the number of derangements of (n) distinct objects.
Using inclusion–exclusion:
[
D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \tag{2}
]
Key property: ( D_n = \left\lfloor \frac{n!}{e} + \frac12 \right\rfloor ).
3. Combinations
3.1 Basic Formula
Number of ways to choose (r) unordered objects from (n) distinct objects: [ \boxed{\mathcal{C}(n,r)=\frac{n!}{r!,(n-r)!}} \tag{3} ] Derivation: Every combination corresponds to (r!) permutations; divide (1) by (r!).
3.2 Edge Cases
| Scenario | Formula | Remarks |
|---|---|---|
| (r=0) or (r=n) | (\mathcal{C}(n,0)=\mathcal{C}(n,n)=1) | Exactly one way. |
| (r>n) | (\mathcal{C}(n,r)=0) | Impossible. |
3.3 Repetition Allowed (Multiset Combinations)
Choosing (r) items from (n) types with repetition: [ \boxed{\mathcal{C}_{\text{rep}}(n,r)=\binom{n+r-1}{r}} \tag{4} ] Proof: Stars‑and‑bars argument: represent (r) selected items as (r) stars and (n-1) bars.
3.4 Restricted Combinations
- At least one of each type: ( \binom{r-1}{n-1} ) (stars‑and‑bars after giving each type one).
- No two adjacent in a line: use combinatorial bijections or inclusion–exclusion.
4. Advanced Topics
4.1 Multinomial Coefficient
When distributing (n) distinct objects into (k) labeled boxes with counts (n_1,\dots,n_k) ((\sum n_i = n)): [ \boxed{\binom{n}{n_1,n_2,\dots,n_k} = \frac{n!}{n_1!,n_2!\dots n_k!}} \tag{5} ] This generalizes both permutations and combinations.
4.2 Binomial Theorem (Connection)
[ (1+x)^n = \sum_{r=0}^{n} \binom{n}{r} x^r. ] The coefficients (\binom{n}{r}) are exactly the combinations.
4.3 Stirling Numbers
- Stirling numbers of the second kind (S(n,k)): number of ways to partition (n) distinct elements into (k) non‑empty unlabeled subsets. Recurrence: [ S(n,k) = k,S(n-1,k) + S(n-1,k-1). ]
- Stirling numbers of the first kind (s(n,k)): number of permutations of (n) elements with exactly (k) cycles.
These appear when counting permutations with cycle restrictions.
4.4 Inclusion–Exclusion Principle (General)
For finite sets (