MAT /Quantitative Ability

Permutation & combination

Modern Maths · free study notes

📚 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 (

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.