Permutations, Combinations and Probability

Counting and probability questions reward a clear method more than a memorised formula: decide whether order matters, whether repetition is allowed, and whether the events are independent or exclusive. Once those are settled, the formulas are short. Every worked answer here is verified by brute-force enumeration.

1. The counting principles

• Multiplication rule: if one task can be done in $m$ ways and, for each, another in $n$ ways, the two together can be done in $m\times n$ ways.
• Addition rule: if tasks are mutually exclusive alternatives, add the ways.

Example 1. A menu has 4 starters, 5 mains and 3 desserts. How many different full meals (one of each)? $4\times 5\times 3=60$.

Example 2. There are 3 roads from A to B and 4 roads from B to C. In how many ways can one travel from A to C? And in how many ways can one go from A to C and back, using a different road on each leg of the return trip (not the same road between B and C, nor the same road between A and B)? One way: $3\times 4=12$. For the round trip, choose the outward roads in $3\times 4$ ways, then the return road from C to B in 3 ways (any except the one used) and from B to A in 2 ways (any except the one used): $3\times 4\times 3\times 2=72$.

from itertools import product, permutations, combinations
from math import comb, perm, factorial

assert 4 * 5 * 3 == len(list(product(range(4), range(5), range(3))))
ab, bc = range(3), range(4)
trips = [(a1, b1, b2, a2) for a1 in ab for b1 in bc for b2 in bc for a2 in ab if b2 != b1 and a2 != a1]
assert len(trips) == 3 * 4 * 3 * 2 == 72

2. Factorials, permutations and combinations

• $n!=n(n-1)\cdots 1$, with $0!=1$.
• Permutations (order matters): $P(n,r)=\frac{n!}{(n-r)!}$.
• Combinations (order does not matter): $C(n,r)=\frac{n!}{r!(n-r)!}$.
• $C(n,r)=C(n,n-r)$, and $C(n,r)=C(n-1,r)+C(n-1,r-1)$.
• Arrangements of $n$ objects in a row: $n!$. In a circle: $(n-1)!$ (rotations are equal). For a necklace or bracelet, where flips also count as equal: $\frac{(n-1)!}{2}$.

assert perm(5, 3) == 60 == 5 * 4 * 3 and comb(5, 3) == 10 == comb(5, 2)
assert comb(8, 3) == comb(7, 3) + comb(7, 2)
assert len(list(permutations(range(5), 3))) == 60 and len(list(combinations(range(5), 3))) == 10
# round-table seating: fix one person, arrange the rest
assert factorial(5 - 1) == 24

Example 3. In how many ways can a committee of 3 men and 2 women be chosen from 7 men and 5 women? $C(7,3)\times C(5,2)=35\times 10=350$.

Example 4. How many ways can 5 people be seated in a row if two particular people must sit together? Glue them into one block: $4!\times 2!=48$.

Example 5. How many ways if those two must not sit together? Total $5!=120$, minus 48 gives $72$.

Example 6. How many arrangements of 5 people around a table if two particular people must sit together? Block them: 4 units around a circle $=3!$, times 2 for the pair's order: $12$.

assert comb(7, 3) * comb(5, 2) == 350
people = range(5)
together = [p for p in permutations(people) if abs(p.index(0) - p.index(1)) == 1]
assert len(together) == 48 and len(list(permutations(people))) - len(together) == 72
def circular(items):
    seen = set()
    for p in permutations(items):
        k = min(p[i:] + p[:i] for i in range(len(p)))     # rotations of one seating are the same circle
        seen.add(k)
    return seen
circles = circular(range(5))
assert len(circles) == 24
adjacent = [c for c in circles if any({c[i], c[(i + 1) % 5]} == {0, 1} for i in range(5))]
assert len(adjacent) == 12

3. Arrangements with repeated letters

Arrangements of $n$ objects in which $p$ are alike of one kind, $q$ alike of another, ...: $\frac{n!}{p!q!\cdots }$.

Example 7. Arrangements of the letters of MISSISSIPPI? $\frac{11!}{4!4!2!}=34650$.

Example 8. How many different arrangements are there of all the letters of LEVEL? The letters are L, E, V, E, L, with L twice and E twice: $\frac{5!}{2!2!}=30$.

Example 9. How many different words (arrangements) can be formed from the letters of ALLAHABAD? The letters are A four times, L twice, and H, B, D once each: $\frac{9!}{4!2!}=7560$.

assert factorial(11) // (factorial(4) * factorial(4) * factorial(2)) == 34650
assert factorial(5) // (factorial(2) * factorial(2)) == 30 == len(set(permutations("LEVEL")))
assert factorial(9) // (factorial(4) * factorial(2)) == 7560 == len(set(permutations("ALLAHABAD")))

4. Restricted arrangements and digit problems

• Number of $r$-digit numbers from given digits with repetition allowed: $n^r$ (with a nonzero first digit if zero is among the digits).
• Without repetition: a permutation count; handle the first digit separately if zero is allowed.

Example 10. How many 3-digit numbers can be formed using 0, 1, 2, 3, 4 with no repetition? First digit: 4 choices (not 0); second: 4; third: 3. Total $4\times 4\times 3=48$.

Example 11. How many of those are even? Count by the last digit. Last digit 0: the first two digits from {1,2,3,4}: $4\times 3=12$. Last digit 2 or 4 (2 choices): first digit from the remaining nonzero digits (3 choices), middle from the remaining 3: $2\times 3\times 3=18$. Total $12+18=30$.

Example 12. In how many ways can the letters of "ORANGE" be arranged so that the vowels occupy only odd positions? Vowels O, A, E; consonants R, N, G. Odd positions are 1, 3, 5: place the vowels in these 3 positions in $3!=6$ ways, and consonants in the remaining 3 positions in $3!=6$ ways: $36$.

digits = [0, 1, 2, 3, 4]
nums = [a * 100 + b * 10 + c for a, b, c in permutations(digits, 3) if a != 0]
assert len(nums) == 48 and len([n for n in nums if n % 2 == 0]) == 30
vowels = set("OAE")
ok = [w for w in permutations("ORANGE") if all((i % 2 == 0) for i, ch in enumerate(w) if ch in vowels)]
assert len(ok) == 36

5. Selections and distributions

• Choosing $r$ from $n$ with repetition allowed (order irrelevant): $C(n+r-1,r)$.
• Distributing $r$ identical items to $n$ people: $C(n+r-1,n-1)$.
• Number of subsets of an $n$-set: $2^n$.
• Number of diagonals of an $n$-gon: $\frac{n(n-3)}{2}$.
• Number of triangles from $n$ points with no three collinear: $C(n,3)$; if $k$ of them are collinear, subtract $C(k,3)$.
• Number of handshakes among $n$ people: $C(n,2)$.

Example 13. How many ways to distribute 10 identical sweets among 3 children, each getting at least one? Give one each first, then distribute 7 freely: $C(7+2,2)=36$.

Example 14. From 8 points, 4 of which are collinear, how many triangles can be formed? $C(8,3)-C(4,3)=56-4=52$.

sols = [(a, b, c) for a in range(1, 10) for b in range(1, 10) for c in range(1, 10) if a + b + c == 10]
assert len(sols) == comb(9, 2) == 36
assert comb(8, 3) - comb(4, 3) == 52
assert 8 * (8 - 3) // 2 == 20 and comb(10, 2) == 45
assert sum(comb(6, k) for k in range(7)) == 2 ** 6

6. Probability basics

$P(E)=\frac{\text{number of favourable outcomes}}{\text{total outcomes}}\text{(equally likely outcomes)}$

• $0\le P(E)\le 1$, and $P(\text{not }E)=1-P(E)$.
• Addition rule: $P(A\cup B)=P(A)+P(B)-P(A\cap B)$. For mutually exclusive events the last term is 0.
• Multiplication rule (independent events): $P(A\cap B)=P(A)P(B)$.
• Conditional probability: $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$.
• At least one: $P=1-P(\text{none})$, usually the quickest route.

Example 15. Two fair dice are rolled. Probability that the sum is 8? Favourable pairs: (2,6), (3,5), (4,4), (5,3), (6,2): $\frac{5}{36}$.

Example 16. A card is drawn from a standard deck. Probability it is a king or a heart? $\frac{4+13-1}{52}=\frac{16}{52}=\frac{4}{13}$.

Example 17. A coin is tossed 3 times. Probability of at least one head? $1-\frac{1}{8}=\frac{7}{8}$.

Example 18. A bag has 5 red and 4 blue balls. Two are drawn without replacement. Probability both are red? $\frac{5}{9}\times \frac{4}{8}=\frac{5}{18}$ (equivalently $\frac{C(5,2)}{C(9,2)}=\frac{10}{36}$).

from fractions import Fraction

dice = list(product(range(1, 7), repeat=2))
assert Fraction(len([d for d in dice if sum(d) == 8]), 36) == Fraction(5, 36)
deck = [(r, s) for r in range(13) for s in range(4)]                  # rank 12 = king, suit 0 = hearts
assert Fraction(len([c for c in deck if c[0] == 12 or c[1] == 0]), 52) == Fraction(4, 13)
tosses = list(product("HT", repeat=3))
assert Fraction(len([t for t in tosses if "H" in t]), 8) == Fraction(7, 8)
assert Fraction(5, 9) * Fraction(4, 8) == Fraction(5, 18) == Fraction(comb(5, 2), comb(9, 2))

Independent versus dependent events, with and without replacement

Example 19. From the same bag (5 red, 4 blue), two balls are drawn with replacement. Probability that they are of different colours? $2\times \frac{5}{9}\times \frac{4}{9}=\frac{40}{81}$.

Without replacement: $\frac{5\cdot 4+4\cdot 5}{9\cdot 8}=\frac{40}{72}=\frac{5}{9}$.

assert 2 * Fraction(5, 9) * Fraction(4, 9) == Fraction(40, 81)
assert Fraction(5 * 4 + 4 * 5, 9 * 8) == Fraction(5, 9)

Conditional probability

Example 20. A family has two children. Given that at least one is a boy, what is the probability both are boys? Outcomes: BB, BG, GB (GG excluded): $\frac{1}{3}$. If instead we are told the older is a boy: outcomes BB, BG, probability $\frac{1}{2}$. The wording matters.

kids = list(product("BG", repeat=2))
at_least_one = [k for k in kids if "B" in k]
assert Fraction(len([k for k in at_least_one if k == ("B", "B")]), len(at_least_one)) == Fraction(1, 3)
older_boy = [k for k in kids if k[0] == "B"]
assert Fraction(len([k for k in older_boy if k == ("B", "B")]), len(older_boy)) == Fraction(1, 2)

The birthday and "at least one" patterns

Example 21. Probability that at least two people in a group of 3 share a birthday (365 days, ignoring leap years)? $1-\frac{365\cdot 364\cdot 363}{365^3}=0.0082$.

p_no_match = Fraction(365 * 364 * 363, 365 ** 3)
assert round(float(1 - p_no_match), 4) == 0.0082

7. Expected value

$E[X]=\sum x_{i}P(x_i)$. It is the long-run average, and it is linear: $E[X+Y]=E[X]+E[Y]$ even for dependent variables.

Example 22. A game pays Rs 30 on a six, Rs 10 on a five, and nothing otherwise, from a roll of a die. A ticket costs Rs 8. Is it fair? $E=\frac{30+10}{6}=6.67<8$, so the game favours the house by Rs 1.33 per play on average.

Example 23. Expected number of heads in 10 tosses of a fair coin: $10\times \frac{1}{2}=5$.

ev = Fraction(30 + 10, 6)
assert round(float(ev), 2) == 6.67 and round(float(8 - ev), 2) == 1.33
assert sum(Fraction(len([t for t in product("HT", repeat=4) if t.count("H") == k]), 16) * k for k in range(5)) == 2

8. Common traps

• Order matters or not? Choosing a committee (combination) versus electing a president, secretary and treasurer (permutation).
• Circular arrangements: $(n-1)!$, not $n!$.
• "At least" problems: use the complement.
• Counting identical letters twice without dividing by the factorials.
• With versus without replacement: probabilities change as the pool shrinks.
• Treating dependent events as independent, and adding probabilities of events that can both happen.
• Leading zeros in digit problems.

9. Practice set with answers

1. In how many ways can 6 people be arranged in a row if two particular people must not be together?
2. How many 4-digit numbers can be formed from 1, 2, 3, 4, 5 with no repetition, and how many of them are divisible by 5?
3. In how many ways can a team of 4 be chosen from 6 boys and 4 girls with at least one girl?
4. Two dice are rolled. Probability that the product is even?
5. Probability of getting exactly 2 heads in 4 tosses of a fair coin?
6. A bag has 4 white, 5 black and 3 green balls. Three are drawn at random. Probability that one of each colour is drawn?
7. How many different arrangements of the letters of "BANANA"?
8. A number is chosen at random from 1 to 50. Probability that it is a multiple of 4 or of 6?

assert factorial(6) - 2 * factorial(5) == 480
fours = [p for p in permutations(range(1, 6), 4)]
assert (len(fours), len([p for p in fours if p[-1] == 5])) == (120, 24)
assert comb(10, 4) - comb(6, 4) == 195
assert Fraction(len([d for d in dice if (d[0] * d[1]) % 2 == 0]), 36) == Fraction(3, 4)
assert Fraction(comb(4, 2), 16) == Fraction(3, 8)
assert Fraction(4 * 5 * 3, comb(12, 3)) == Fraction(3, 11)
assert len(set(permutations("BANANA"))) == 60 == factorial(6) // (factorial(3) * factorial(2))
assert len([n for n in range(1, 51) if n % 4 == 0 or n % 6 == 0]) == 50 // 4 + 50 // 6 - 50 // 12 == 16     # 12 + 8 - 4
assert Fraction(16, 50) == Fraction(8, 25)

Answers: 1) 480; 2) 120 numbers, 24 divisible by 5; 3) 195; 4) $\frac{3}{4}$; 5) $\frac{3}{8}$; 6) $\frac{3}{11}$; 7) 60; 8) $\frac{8}{25}$.