Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Permutations and combinations

Permutations and combinations count ordered and unordered selections from finite sets; engineers use them in counting states, resource allocations, testing combinations, and analysing algorithms.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Counting how many ways things can be arranged or chosen is a basic engineering skill. In computer engineering you use this when analysing algorithmic state spaces, estimating number of test cases, designing communication codes, and solving resource-allocation problems. Permutations and combinations give precise answers for ordered and unordered choices.

Key ideas

  • Permutation: a permutation is an arrangement of items where order matters. A full permutation of n distinct items has n! possible orders.

  • r-permutation (also called arrangement or partial permutation): the number of ordered selections of r items chosen without replacement from n distinct items. Denoted P(n, r) or nPr. The exact formula is derived by the multiplication (product) rule: choose first element in n ways, second in (n−1) ways, ... until r elements. So P(n, r) = n·(n−1)·...·(n−r+1) = n!/(n−r)!, valid for integer n ≥ r ≥ 0.

  • Combination: a combination is a selection of items where order does not matter. The number of ways to choose r items from n distinct items is denoted C(n, r) or nCr and equals n!/(r!(n−r)!). Derivation: count ordered r-permutations and divide by r! because each unordered set corresponds to r! orders.

  • Permutations with repetition allowed: when each selection position can be any of n types and positions are independent (order matters), number = n^r. Example: strings of length r from alphabet of size n.

  • Combinations with repetition allowed (multicombinations): selecting r items from n types where order does not matter and repetitions allowed. Equivalent to distributing r identical balls into n distinct boxes. Formula: C(n+r−1, r). Derivation uses stars-and-bars argument.

  • Permutations of multisets (identical objects present): If total n items include n1 of type1, n2 of type2, ..., nk of typek with sum n = n1+...+nk, then number of distinct permutations = n!/(n1! n2! ... nk!). This corrects for over-counting caused by identical items.

  • Circular permutations: seating n distinct people around a round table where only relative order matters (rotations considered identical) gives (n−1)! arrangements. Derivation: fix one person to break rotational symmetry, then permute remaining (n−1).

  • Multinomial coefficient: generalisation of nCr. The coefficient for splitting n labeled items into k labeled groups with sizes n1,...,nk (sum n) is n!/(n1! n2! ... nk!). It appears in multinomial expansion and in counting distributions where group labels matter.

  • Exact assumptions: we always assume items of the same type are indistinguishable only when specified; otherwise items are distinct. When drawing without replacement, items removed cannot be chosen again; with replacement means independent draws. Quick mapping of the four basic sampling models (memorize for exams):

    • Order matters, without replacement → P(n, r) = n!/(n−r)!.
    • Order matters, with replacement → n^r.
    • Order does not matter, without replacement → C(n, r).
    • Order does not matter, with replacement → C(n+r−1, r) = C(n+r−1, n−1).
  • Where related topics help: Inclusion–exclusion principle is used when counting with overlapping conditions; generating functions can derive combination-with-repetition results and partition counts.

Diagrams to draw on exam answers:

  • For stars-and-bars: draw r stars in a row and (n−1) bars between boxes, show an example for small n and r and label bars and stars.
  • For circular permutations: draw a circle, place labeled points for people 1..n, and show that rotating the whole circle gives the same arrangement.

Formulas

n! = 1·2·3·...·n — n factorial; n is a non-negative integer; unitless; applies for counting permutations of n distinct objects.

P(n, r) = n·(n−1)·...·(n−r+1) = n!/(n−r)! — number of ordered selections of r distinct items from n distinct items (n ≥ r ≥ 0); unitless.

C(n, r) = n!/(r!(n−r)!) — number of unordered selections of r distinct items from n distinct items (n ≥ r ≥ 0); unitless. Also useful identities and properties:

  • Symmetry: C(n, r) = C(n, n−r).
  • Pascal’s identity (for integers n > 0 and 0 ≤ r ≤ n): C(n, r) = C(n−1, r) + C(n−1, r−1).
  • Binomial sum: ∑_{r=0}^n C(n, r) = 2^n (and boundary values C(n, 0) = C(n, n) = 1).

n^r — number of ordered sequences of length r where each position can be any of n types (repetition allowed); unitless.

C(n+r−1, r) — number of unordered selections of r items from n types with repetition allowed (stars-and-bars) (n ≥ 1, r ≥ 0); unitless.

n!/(n1! n2! ... nk!) — permutations of a multiset with k types and counts n1,...,nk summing to n; unitless.

(n−1)! — number of distinct circular permutations of n distinct objects where rotations are considered identical (n ≥ 1); unitless.

Multinomial coefficient: (n; n1,n2,...,nk) = n!/(n1! n2! ... nk!) — number of ways to partition n labeled objects into k labeled groups of sizes n1,...,nk; unitless.

Worked examples

Example 1 — arranging distinct items (shelf problem) Problem: How many ways to arrange 7 distinct books on a shelf? Solution steps:

  1. Formula: n! with n = 7.
  2. Compute: 7! = 7·6·5·4·3·2·1 = 5040. Final answer: 5040.

Example 2 — choosing a committee (combination) Problem: From 10 students, select 4 to form a committee (order not important). How many ways? Solution steps:

  1. Formula: C(10,4) = 10!/(4!6!).
  2. Compute: 10! = 3628800, 4! = 24, 6! = 720 so denominator 24·720 = 17280.
  3. Division: 3628800/17280 = 210. Final answer: 210.

Example 3 — combinations with repetition (candies) Problem: There are 5 types of candies. How many ways to choose 3 candies if types may repeat and order does not matter? Solution steps:

  1. Use stars-and-bars formula: C(n+r−1, r) with n = 5, r = 3.
  2. Compute: C(5+3−1, 3) = C(7,3) = 7!/(3!4!) = 35. Final answer: 35.

Example 4 — permutations of a multiset (word arrangements) Problem: How many distinct arrangements of letters are there in the word MISSISSIPPI? Solution steps:

  1. Count letters: total n = 11. Counts: M:1, I:4, S:4, P:2.
  2. Use multiset formula: 11!/(1!4!4!2!).
  3. Compute: 11! = 39916800. Denominator: 1·24·24·2 = 1152.
  4. Division: 39916800/1152 = 34650. Final answer: 34650.

Example 5 — circular seating Problem: Six friends sit around a round table. How many distinct seating orders, ignoring rotations, are possible? Solution steps:

  1. Formula for circular permutations: (n−1)! with n = 6.
  2. Compute: 5! = 120. Final answer: 120.

Common mistakes

  • Not dividing by factorials for identical items (e.g., treating identical letters as distinct when arranging words).
  • Using n^r (repetition allowed) when the problem says drawing without replacement; or using P(n,r) when repetition is allowed.
  • For circular arrangements, forgetting to divide by n for rotational symmetry (i.e., using n! instead of (n−1)!). Also be careful about reflections: if reflections are also considered identical (a necklace), divide further by 2 for n > 2.
  • Misapplying stars-and-bars: mixing up whether boxes (types) are distinct or identical; stars-and-bars assumes box labels are distinct.

For your exam

Types of questions you will see:

  • Definitions and short notes (define permutation, combination, factorial, multiset, stars-and-bars).
  • Derivations (derive nPr = n!/(n−r)!; derive nCr by dividing permutations by r!). Show step-by-step reasoning.
  • Numerical problems (arrangements, selections, circular permutations, multisets). Show formulas used, substitute numbers, compute values clearly and give final answer.
  • Proofs or reasoning using combinatorial arguments (e.g., argue why combinations with repetition equals C(n+r−1,r); explain dividing by r! for unordered selections).
  • Word problems mapped to formulas (translate English carefully — order matter? repetition allowed?).

What a full-marks answer includes:

  • Precise definitions of terms used (bold or named), clear statement of formula with conditions (n ≥ r etc.).
  • A mapping from the word problem to a counting model (e.g., 'choose r without order, without replacement' → use nCr).
  • Correct formula, clear arithmetic steps, units not required, final numerical answer boxed or stated clearly.
  • For derivations, show multiplication rule steps and explain division for over-counting; include a small example to illustrate if helpful.

Quick check

  1. Compute 5P3.
  2. Compute 5C3.
  3. How many ways to choose 3 items from 5 types if repetition is allowed and order does not matter?

Answers: 1: 5P3 = 5·4·3 = 60. 2: 5C3 = 5!/(3!2!) = 10. 3: C(5+3−1,3) = C(7,3) = 35.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?