Combinations and permutations are the two core ways to count selections from a set. Permutations care about order; combinations do not. Each has a variant that allows repetition. Growth functions describe how fast an algorithm's resource usage scales with input size, from constant up to factorial.
Difficulty: Introductory to Intermediate | Prerequisites: factorials, basic set notation
Counting is foundational to probability, algorithm analysis, and combinatorics. In a CS foundations course, you need to count arrangements to analyse how many possible inputs an algorithm might face, or to work out probabilities. Growth functions (Big-O) then give you the language to describe how algorithms scale. These two topics often appear on the same exam because counting tells you "how many" and growth functions tell you "how fast."
r-permutation (without repetition)
An ordered arrangement of r elements chosen from a set of n, where each element may be used at most once. Formula: n! / (n - r)!. Think of it as picking r items from n and lining them up.
r-combination (without repetition)
An unordered selection of r elements from a set of n, no repeats. Formula: n! / (r! (n - r)!). Same as a permutation, but you divide out the orderings because sequence does not matter.
r-permutation with repetition
An ordered arrangement of r elements from n, where the same element can appear more than once. Formula: nʳ. Think of it as filling r slots where each slot has n choices independently.
r-combination with repetition
An unordered selection of r elements from n, allowing repeats. Formula: (n + r - 1)! / (r! (n - 1)!). This one is less intuitive; it counts the number of ways to distribute r identical items into n distinct bins.
nCr (binomial coefficient)
The number of ways to choose r items from n without repetition and without regard to order. Written C(n, r) or "n choose r." Equal to n! / (r! (n - r)!).
Big-O notation
A way of describing the upper bound on an algorithm's growth rate as input size increases. O(f(n)) means the function grows no faster than f(n) for large n, up to a constant factor.
Growth function
The mathematical function that describes how an algorithm's time or space requirements scale with input size n. Common examples range from O(1) (constant) to O(n!) (factorial).
The central question is: does order matter?
Permutations: order matters. Choosing A then B is different from B then A.
Combinations: order does not matter. {A, B} is the same selection as {B, A}.
The relationship between them: P(n, r) = C(n, r) × r!. In other words, a permutation count is just the combination count multiplied by the number of ways to arrange the chosen items.
r-permutations: P(n, r) = n! / (n - r)!
You have n choices for the first slot, n - 1 for the second, and so on down to n - r + 1.
r-combinations: C(n, r) = n! / (r! (n - r)!)
Same pool of choices, but you divide by r! to remove duplicate orderings.
Symmetry property: C(n, r) = C(n, n - r). Choosing which r to include is the same as choosing which n - r to exclude.
r-permutations with repetition: nʳ
Each of the r positions can be any of the n elements independently.
r-combinations with repetition: (n + r - 1)! / (r! (n - 1)!)
Often called the "stars and bars" formula. Think of distributing r identical objects among n distinct categories.
C(n + 1, k) = C(n, k - 1) + C(n, k). This is the rule that builds Pascal's triangle and is useful for computing binomial coefficients without large factorials.
Listed from slowest to fastest growing:
Constant: O(1)
Logarithmic: O(log n)
Linear: O(n)
Linearithmic: O(n log n)
Quadratic: O(n²)
Cubic: O(n³)
Polynomial: O(nᵏ), k is a constant
Exponential: O(2ⁿ), O(cⁿ), c is a constant
Factorial: O(n!)
For algorithm analysis, polynomial or better is generally considered tractable. Exponential and factorial growth makes a brute-force approach infeasible for large inputs.
Type | Repetition? | Formula |
|---|---|---|
r-permutations | No | n! / (n - r)! |
r-combinations | No | n! / (r! (n - r)!) |
r-permutations | Yes | nʳ |
r-combinations | Yes | (n + r - 1)! / (r! (n - 1)!) |
Key identities:
P(n, r) = C(n, r) × r!
C(n, r) = C(n, n - r)
C(n + 1, k) = C(n, k - 1) + C(n, k) (Pascal's identity)
Students frequently mix up permutations and combinations. If the problem says "arrange," "order," or "sequence," you want permutations. If it says "choose," "select," or "committee," you want combinations.
Forgetting the repetition dimension is common. Always ask: can the same element be picked more than once? This doubles your formula options.
Students sometimes think O(n²) and O(2n) are the same thing. They are not. O(n²) is polynomial (quadratic); O(2ⁿ) is exponential, which grows vastly faster.
Pascal's identity is not a separate formula to memorise in isolation. It is the relationship that builds Pascal's triangle, and it follows directly from the combination formula.
⚠️ You will almost certainly be asked to compute a permutation or combination, with or without repetition. Know which formula applies to which scenario.
⚠️ Exam questions may test whether you can identify the correct formula from a word problem. Look for the cues: does order matter? Is repetition allowed?
⚠️ Growth functions are tested both as standalone ordering questions ("rank these from slowest to fastest") and in the context of algorithm analysis.
True or false: C(10, 3) = C(10, 7). (True, by the symmetry property.)
Fill in the blank: r-permutations with repetition from n elements = ______. (nʳ)
True or false: O(n log n) grows faster than O(n²). (False: O(n²) grows faster.)
Fill in the blank: The formula for r-combinations without repetition is n! / (______ × ______). (r! × (n - r)!)
True or false: Choosing 3 items from 5 where order matters gives 60 arrangements. (True: P(5,3) = 5!/2! = 60.)
Q: A committee of 4 is chosen from 10 people. How many possible committees are there?
A: C(10, 4) = 10! / (4! × 6!) = 210. Order does not matter and there is no repetition.
Q: A 3-digit PIN is formed from digits 0 to 9, with repetition allowed. How many possible PINs exist?
A: 10³ = 1000. This is an r-permutation with repetition (order matters, repetition allowed).
Q: Rank the following from slowest to fastest growth: O(n²), O(log n), O(n!), O(n log n), O(1).
A: O(1) < O(log n) < O(n log n) < O(n²) < O(n!).
Q: What is C(n + 1, k) expressed using Pascal's identity?
A: C(n + 1, k) = C(n, k - 1) + C(n, k).
Q: How many ways can you choose 3 scoops of ice cream from 5 flavours if you can repeat flavours?
A: C(5 + 3 - 1, 3) = C(7, 3) = 35. This is a combination with repetition.
Counting feeds directly into probability (the number of favourable outcomes over total outcomes). Growth functions connect to algorithm analysis, which you will use when comparing sorting and searching algorithms. Pascal's identity links to the binomial theorem, which appears in both algebra and probability.
permutations, combinations, r-permutation, r-combination, with repetition, without repetition, nCr, n choose r, binomial coefficient, Pascal's identity, Pascal's triangle, stars and bars, Big-O, growth functions, time complexity, constant, logarithmic, linear, linearithmic, quadratic, cubic, polynomial, exponential, factorial, algorithm analysis, CS 101, discrete mathematics