Counting: Permutations & Combinations
Permutations count ordered arrangements; combinations count unordered selections. Both feed straight into binomial probability — and the GA section.
What you'll learn
- The multiplication rule: independent choices multiply
- Permutations nPr count ordered arrangements; combinations nCr count unordered selections
- When order matters and when it does not — the single decision that picks the formula
- Why nCr is the backbone of the binomial distribution
Before you start
How many 4-digit PINs use all distinct digits? How many ways can a 3-person committee form from 10 people? Probability is mostly “favourable outcomes over total outcomes” — so getting the count right is half the work. Two small ideas cover almost everything GATE asks here: the multiplication rule, and the choice between permutations (order matters) and combinations (order doesn’t).
The multiplication rule
If one choice has m options and a second independent choice has n options, the
two together have m × n outcomes. Choices in sequence multiply.
A 5-question multiple-choice test with 4 options each can be answered in
4 × 4 × 4 × 4 × 4 = 4^5 = 1024 ways. That’s the whole rule.
Permutations vs combinations — order is the only question
The one decision that picks your formula: does order matter?
- Permutation
nPr = n! / (n−r)!— ordered arrangements ofritems fromn. Arranging 5 distinct books on a shelf:5! = 120. - Combination
nCr = n! / (r!(n−r)!)— unordered selections ofrfromn. Choosing a 3-person committee from 10:C(10,3) = (10·9·8)/(3·2·1) = 720/6 = 120.
The combination is just the permutation with the r! orderings of each group
collapsed to one. That extra r! in the denominator is the entire difference.
How GATE asks this
Counting rarely appears alone. It shows up inside a probability question — “what
is the probability that a 4-digit PIN has all distinct digits?” needs 10·9·8·7
over 10^4 — and as the nCr factor in the binomial distribution, where the
number of ways to get k successes in n trials is exactly C(n,k). Master nCr
now and the binomial lesson becomes easy. (The same nCr quietly powers real data
work too: it counts how many feature subsets a model could try, or how many
train/test splits or cross-validation folds are possible.)
Two facts worth memorising: nC0 = nCn = 1, and the symmetry nCr = nC(n−r) (choosing
which 3 to include is the same as choosing which n−3 to leave out).
Quick check
Quick check
Practice this in an interview
All questionsPermutations count ordered arrangements: P(n,k) = n!/(n-k)!. Combinations count unordered selections: C(n,k) = n!/[k!(n-k)!]. The rule is simple — if the order of selection matters, permute; if it doesn't, combine. Combinations are always smaller by a factor of k!.
Each distribution has a natural generative story: Bernoulli is a single coin flip; Binomial sums Bernoullis; Poisson counts rare arrivals; Normal emerges from sums of many small effects; Exponential models waiting times between Poisson events; Uniform assigns equal probability across a range. Choosing correctly comes from matching that story to the data-generating process.
The law of total probability decomposes P(A) over a mutually exclusive, exhaustive partition of the sample space: P(A) = Σ P(A|Bᵢ)·P(Bᵢ). It is the engine behind the Bayes denominator and any calculation where you want an overall rate built from segment-level rates.
Binomial counts successes in a fixed number of independent trials with a fixed success probability. Poisson counts events in a continuous interval when events are rare and arrive independently at a constant average rate. Poisson is the limiting case of Binomial as n → ∞ and p → 0 with np = λ fixed.