In Counting Principles we learned to count by multiplying choices (the product rule) and adding disjoint cases (the sum rule). Two kinds of selection appear so often that they get their own names and formulas: permutations, where we pick objects and the order matters, and combinations, where we pick objects and order does not matter.
Almost every counting question in a university exam, GATE or a placement aptitude test comes down to two questions: does order matter? and is repetition allowed? Once you answer both, the formula follows. This chapter builds each formula from the product rule, so you understand why it is true and do not just memorise it.
An r-permutation of a set is an ordered arrangement of r distinct elements from it. An r-combination is an unordered selection (a subset) of r elements from it.
All numerical answers in this chapter were checked with a brute-force Python program that lists and counts every possibility.
Factorials
How many ways can n distinct objects be arranged in a row? The first position has n choices, the second n − 1 (one object is used up), and so on down to 1. By the product rule:
n! = n × (n − 1) × (n − 2) × … × 2 × 1, with 0! = 1.
So the 8 letters of COMPUTER (all different) can be arranged in 8! = 40320 ways. The convention 0! = 1 is not arbitrary: there is exactly one way to arrange nothing (the empty arrangement), and it makes every formula below work when r = 0 or r = n.
Factorials grow very fast: 10! = 3,628,800 and 20! is about 2.4 × 1018, close to the limit of a signed 64-bit integer (about 9.2 × 1018); 21! no longer fits in a long long. That is why brute-force "try every ordering" algorithms become hopeless beyond about n = 12.
Permutations: Order Matters
Example. 10 runners race. In how many ways can gold, silver and bronze be awarded?
Gold: 10 choices. Silver: 9 (anyone except the gold winner). Bronze: 8. Total 10 × 9 × 8 = 720. Order matters here because (Asha gold, Ravi silver) is a different result from (Ravi gold, Asha silver).
The number of r-permutations of n distinct objects is P(n, r) = n × (n − 1) × … × (n − r + 1) = n! / (n − r)!, for 0 ≤ r ≤ n.
Why the formula? The product n(n − 1)…(n − r + 1) has exactly r factors. Multiplying top and bottom by (n − r)! turns the top into n!. Special cases: P(n, n) = n! (arrange everything) and P(n, 0) = 1. You will also see the notation nPr.
Worked example: arrangements with a restriction
5 boys and 3 girls (all different people) stand in a row. In how many ways can they stand if no two girls are next to each other?
First arrange the boys: 5! = 120 ways.
The boys create 6 gaps (including both ends): _ B _ B _ B _ B _ B _.
Put each girl in a different gap, and order matters since the girls are different: P(6, 3) = 6 × 5 × 4 = 120 ways.
Total: 120 × 120 = 14400.
This gap method is the standard trick for "no two X together". For "these items must be together" use the opposite trick: glue them into one block. For example, in COMPUTER the vowels O, U, E stay together in 6! × 3! = 4320 arrangements (6 units: the block plus C, M, P, T, R; then arrange the 3 vowels inside the block).
Permutations with Repeated Objects
How many different words can be made from the letters of BANANA? If all 6 letters were different the answer would be 6!. But swapping the three A's among themselves gives the same word, and so does swapping the two N's. Each distinct word is therefore counted 3! × 2! times in the 6! arrangements:
Number of words = 6! / (3! × 2! × 1!) = 720 / 12 = 60.
If n objects contain n1 identical objects of type 1, n2 of type 2, …, nk of type k (n1 + … + nk = n), the number of distinct arrangements is n! / (n1! n2! … nk!).
This is called the multinomial coefficient. Examples:
MISSISSIPPI: 11 letters with M×1, I×4, S×4, P×2: 11! / (4! 4! 2!) = 34650.
ENGINEERING: E×3, N×3, G×2, I×2, R×1: 11! / (3! 3! 2! 2!) = 277200.
Binary strings of length 10 with exactly four 1s: 10! / (4! 6!) = 210.
Circular Permutations
In how many ways can 6 people sit around a round table? Seats are not numbered; only who sits next to whom matters. So two seatings that are rotations of each other are the same.
Each circular seating corresponds to exactly 6 linear arrangements (start reading from any of the 6 people). So the count is 6! / 6 = 5! = 120. Another way to see it: fix one person's seat to remove the rotation, then arrange the other 5 in 5! ways.
n distinct objects can be arranged in a circle in (n − 1)! ways. If clockwise and anticlockwise are also considered the same (beads on a necklace that can be flipped over), the count is (n − 1)!/2 for n ≥ 3.
So 6 different beads give 5!/2 = 60 distinct necklaces.
Combinations: Order Does Not Matter
Example. A club of 12 members chooses a committee of 5. How many committees are possible?
If order mattered we would have P(12, 5) ordered lists. But every committee (a set of 5 people) appears in 5! different orders in that list. So:
C(12, 5) = P(12, 5) / 5! = 95040 / 120 = 792.
The number of r-combinations of n distinct objects is C(n, r) = n! / (r! (n − r)!), for 0 ≤ r ≤ n. It is also written nCr or as the binomial coefficient "n choose r".
The key relation is P(n, r) = C(n, r) × r!: to make an ordered selection, first choose which r objects (C(n, r) ways), then order them (r! ways).
Worked examples
(a) The committee of 5 must have exactly 3 men and 2 women, chosen from 7 men and 5 women. Choose the men: C(7, 3) = 35. Choose the women: C(5, 2) = 10. Product rule: 35 × 10 = 350.
(b) At least one woman. Counting "1 woman + 2 women + … + 5 women" works but is slow. Use the complement: all committees minus those with no woman = C(12, 5) − C(7, 5) = 792 − 21 = 771.
(c) Triangles from 10 points, of which exactly 4 lie on one line (no other three collinear). Any 3 points make a triangle unless they are collinear: C(10, 3) − C(4, 3) = 120 − 4 = 116.
(d) Diagonals of a 10-sided polygon. Every pair of vertices gives a side or a diagonal: C(10, 2) − 10 = 45 − 10 = 35. In general an n-gon has n(n − 3)/2 diagonals.
(e) Lattice paths. Moving only right (R) or up (U) one unit at a time, how many shortest paths go from (0, 0) to (4, 3)? Every path is a word with 4 R's and 3 U's; choose the 3 positions of the U's: C(7, 3) = 35.
Identities for Binomial Coefficients
Many identities can be proved by a combinatorial proof: show that both sides count the same set in two different ways. This is often shorter and more convincing than algebra.
Symmetry: C(n, r) = C(n, n − r)
Proof. Choosing which r objects to take is the same as choosing which n − r objects to leave behind. Each choice of one determines the other, so both counts are equal. ∎
Pascal's identity: C(n, k) = C(n − 1, k − 1) + C(n − 1, k) for 1 ≤ k ≤ n − 1
Proof. Count the k-subsets of {1, 2, …, n}. Split them into two disjoint groups by asking: does the subset contain element n?
Yes: the other k − 1 elements come from {1, …, n − 1}: C(n − 1, k − 1) subsets.
No: all k elements come from {1, …, n − 1}: C(n − 1, k) subsets.
By the sum rule the total is C(n − 1, k − 1) + C(n − 1, k). ∎
Pascal's identity builds Pascal's triangle, where each entry is the sum of the two above it:
n = 0 1
n = 1 1 1
n = 2 1 2 1
n = 3 1 3 3 1
n = 4 1 4 6 4 1
n = 5 1 5 10 10 5 1
n = 6 1 6 15 20 15 6 1
It also gives a way to compute C(n, k) in code without huge factorials: fill a table row by row using only additions (dynamic programming).
Vandermonde's identity
C(m + n, r) = ∑k=0r C(m, k) C(n, r − k).
Proof. Choose r people from a group of m men and n women. Classify by k = number of men chosen: C(m, k) ways for the men and C(n, r − k) for the women. Add over all k. ∎ For example, with m = 5, n = 4, r = 3: 1·4 + 5·6 + 10·4 + 10·1 = 84 = C(9, 3).
The Binomial Theorem
For any x, y and integer n ≥ 0: (x + y)n = ∑k=0n C(n, k) xn−k yk.
Why? Expand (x + y)(x + y)…(x + y) with n factors. Each term of the expansion picks x or y from every factor. The term xn−kyk appears once for every way of choosing which k factors give y, which is C(n, k) ways. That is why C(n, k) is called a binomial coefficient.
Worked example: a single coefficient
Find the coefficient of x5 in (2x − 3)8.
The general term is C(8, k) (2x)k (−3)8−k.
We need k = 5: C(8, 5) × 25 × (−3)3.
= 56 × 32 × (−27) = −48384.
Useful consequences
Put x = y = 1: ∑k C(n, k) = 2n. An n-element set has 2n subsets in total.
Put x = 1, y = −1: ∑k (−1)k C(n, k) = 0 for n ≥ 1. A non-empty set has as many even-sized subsets as odd-sized ones. We use this fact to prove the Inclusion-Exclusion Principle.
The sum of all coefficients of a polynomial p(x) is p(1). For (2x − 3)8 it is (2 − 3)8 = 1.
Combinations with Repetition (Stars and Bars)
Example. A shop sells 4 kinds of donuts. In how many ways can you buy 6 donuts? Order does not matter, and you may take many of the same kind.
Write a purchase as 6 stars (donuts) separated by 3 bars into 4 compartments, one per kind. For instance:
★★ | ★ | | ★★★ means 2 of kind A, 1 of B, 0 of C, 3 of D
| ★★★★★★ | | means 0 of A, 6 of B, 0 of C, 0 of D
Every purchase is exactly one row of 6 stars and 3 bars, and every such row is a purchase. A row has 9 positions; choose which 3 are bars: C(9, 3) = 84.
The number of ways to choose r objects from n types, with repetition allowed and order ignored, is C(n + r − 1, r) = C(n + r − 1, n − 1).
Integer solutions of equations
The same count answers: how many solutions does x1 + x2 + x3 = 10 have in non-negative integers? Each xi is "how many of type i", so the answer is C(10 + 3 − 1, 2) = C(12, 2) = 66.
Positive integers (each xi ≥ 1)? Give each variable 1 first: put xi = yi + 1 with yi ≥ 0. Then y1 + y2 + y3 = 7, which has C(9, 2) = 36 solutions. In general, x1 + … + xn = r has C(r − 1, n − 1) positive solutions.
Lower bounds are handled by this substitution. Upper bounds (like xi ≤ 6) need the Inclusion-Exclusion Principle, covered in a later chapter.
Dividing into Groups
12 students are split into 3 project groups of 4.
If the groups are labelled (Group A works on networks, B on databases, C on compilers): choose A, then B from the rest, then C gets the remaining 4. C(12, 4) × C(8, 4) × C(4, 4) = 495 × 70 × 1 = 12! / (4! 4! 4!) = 34650.
If the groups are unlabelled (just "three groups of four"): each split was counted once for each of the 3! ways to attach labels, so divide: 34650 / 6 = 5775.
Dividing by the number of ways to relabel is only valid when the groups have the same size. With sizes 5, 4, 3 the groups are already distinguishable by size, so there is nothing to divide by.
The Four Basic Cases
Choosing r items from n distinct types:
Repetition not allowed | Repetition allowed | |
|---|---|---|
Order matters | P(n, r) = n!/(n − r)! | nr |
Order does not matter | C(n, r) = n!/(r!(n − r)!) | C(n + r − 1, r) |
Balls into boxes
Many problems are "put n balls into k boxes". The answer depends on whether balls and boxes are distinguishable. For n = 4 balls and k = 3 boxes (empty boxes allowed):
Balls | Boxes | Formula | n = 4, k = 3 |
|---|---|---|---|
Distinct | Distinct | kn (each ball picks a box) | 81 |
Identical | Distinct | C(n + k − 1, k − 1) (stars and bars) | 15 |
Distinct | Identical | S(n, 1) + … + S(n, k), Stirling numbers of the second kind | 1 + 7 + 6 = 14 |
Identical | Identical | Partitions of n into at most k parts | 4 (4, 3+1, 2+2, 2+1+1) |
S(n, j), the number of ways to split n distinct objects into j non-empty unlabelled groups, has no simple closed form; the Inclusion-Exclusion Principle chapter gives a formula for it through onto functions.
Checking with Code
Python's itertools generates permutations and combinations directly, and math.perm and math.comb (Python 3.8+) compute the formulas. Comparing the two is the fastest way to catch a counting mistake.
from itertools import permutations, combinations, combinations_with_replacement
from math import comb, perm, factorial
# 1. r-permutations: gold, silver, bronze among 10 runners
print("P(10,3) formula:", perm(10, 3),
" brute force:", len(list(permutations(range(10), 3))))
# 2. Distinct arrangements of BANANA (repeated letters)
print("BANANA formula:", factorial(6) // (factorial(3) * factorial(2)),
" brute force:", len(set(permutations("BANANA"))))
# 3. Committees of 5 from 7 men (0-6) and 5 women (7-11) with at least one woman
good = [c for c in combinations(range(12), 5) if any(p >= 7 for p in c)]
print("At least one woman:", len(good), " formula:", comb(12, 5) - comb(7, 5))
# 4. Combinations with repetition: 6 donuts from 4 types
print("6 donuts, 4 types:", len(list(combinations_with_replacement("ABCD", 6))),
" formula:", comb(6 + 4 - 1, 6))
# 5. Non-negative solutions of x1 + x2 + x3 = 10
sols = [(a, b, 10 - a - b) for a in range(11) for b in range(11 - a)]
print("Solutions of x1+x2+x3=10:", len(sols), " formula:", comb(12, 2))
Output:
P(10,3) formula: 720 brute force: 720
BANANA formula: 60 brute force: 60
At least one woman: 771 formula: 771
6 donuts, 4 types: 84 formula: 84
Solutions of x1+x2+x3=10: 66 formula: 66
Note the set(...) in check 2: permutations treats the three A's as different objects and produces all 720 orderings, and the set removes the duplicates. That is exactly the "divide by 3! × 2!" step of the formula.
Common Mistakes
Using P when order does not matter. A committee, a hand of cards or a subset is unordered: use C. A ranking, a password or a seating is ordered: use P.
Double counting "at least one". Choosing "one woman first, then any 4 others" gives 5 × C(11, 4) = 1650, far more than 771, because a committee with two women is counted once for each of them. Use the complement instead.
Forgetting identical objects. Arrangements of BANANA are not 6!.
Circular arrangements. n people around a table: (n − 1)!, not n!. Divide by 2 only when reflections are also the same (necklaces, garlands), not for people at a table, where left and right neighbours differ.
Dividing by k! for unequal groups. Only groups of equal size can be swapped without changing the split.
Stars and bars with the wrong numbers. r objects into n types: C(n + r − 1, r). Check with a tiny case: 2 objects from 2 types gives C(3, 2) = 3 (AA, AB, BB). Correct.
Practice and GATE-Style Questions
Q1. How many 4-digit numbers have all digits different?
The first digit cannot be 0: 9 choices. The second can be 0 but not the first digit: 9. Then 8, then 7. Total 9 × 9 × 8 × 7 = 4536. (P(10, 4) = 5040 would include strings like 0123 that are not 4-digit numbers.)
Q2. How many distinct arrangements does the word LETTER have?
6 letters with E×2, T×2: 6! / (2! 2!) = 720 / 4 = 180.
Q3. In how many ways can 5 identical chocolates be given to 3 children? What if each child must get at least one?
Stars and bars: C(5 + 3 − 1, 2) = C(7, 2) = 21. With at least one each: give one to every child first, then distribute the remaining 2 freely: C(2 + 2, 2) = 6, which matches C(r − 1, n − 1) = C(4, 2) = 6.
Q4. Prove that ∑k=0n C(n, k) = 2n combinatorially.
Both sides count the subsets of an n-element set. Right side: each element is in or out, 2 choices each, so 2n. Left side: group the subsets by size k; there are C(n, k) subsets of size k. Adding over all sizes counts every subset exactly once. ∎
Q5. How many shortest grid paths go from (0, 0) to (4, 3) and pass through (2, 1)?
From (0, 0) to (2, 1): C(3, 1) = 3. From (2, 1) to (4, 3): 2 R's and 2 U's, C(4, 2) = 6. Product: 18 (out of the 35 paths in total).
Q6. Interview: compute C(n, k) mod 109+7 for many queries with n ≤ 106. How?
Precompute factorials f[i] = i! mod p and inverse factorials using Fermat's little theorem (p is prime, so a−1 ≡ ap−2 mod p). Then C(n, k) = f[n] × inv_f[k] × inv_f[n − k] mod p, in O(1) per query after O(n) preprocessing. For small n without a modulus, Pascal's triangle with additions only also works.
Summary
n distinct objects in a row: n!. In a circle: (n − 1)!.
Ordered selections of r from n: P(n, r) = n!/(n − r)!. Unordered: C(n, r) = n!/(r!(n − r)!), and P(n, r) = r! × C(n, r).
Arrangements with identical objects: n!/(n1! … nk!).
Selections with repetition (stars and bars): C(n + r − 1, r); the same number counts non-negative solutions of x1 + … + xn = r.
Binomial theorem: (x + y)n = ∑ C(n, k) xn−kyk; Pascal's identity and combinatorial proofs explain the identities.
For "at least one" use the complement; for "never together" use gaps; for "always together" use a block.
Before reaching for a formula, ask two questions: does order matter, and can things repeat? The answers pick the formula for you.