Probability, Permutation & Combination

The fundamental counting principle is the AND rule used one step at a time. Whenever you have to build something position by position (a number, a code, a password, a set of posts), draw one empty box for each position and write in each box how many choices are left for that position. Then multiply.

For example, how many 2-digit numbers can be made from 3, 5, 7, 9 without repeating a digit? The tens box has 4 choices. One digit is now used, so the units box has 3. Total = 4 × 3 = 12. If repetition is allowed, both boxes get 4 choices and the answer becomes 4 × 4 = 16.

[[fig:0]]

Repetition allowed or not. Without repetition the choices drop by one in every next box (5, 4, 3, …). With repetition every box keeps the full number of choices (5, 5, 5, …). Read this one word in the question very carefully.

Fill the restricted box first. If a condition sits on some position (the number must be even, must not start with 0, the code must end in a vowel), fill that box first and only then the free boxes. Take 3-digit odd numbers from 2, 3, 4, 5, 6 without repetition. The units box can hold only 3 or 5, so it has 2 choices. Now the hundreds box has 4 digits left and the tens box 3. Total = 2 × 4 × 3 = 24.

[[fig:1]]

The zero problem. A number cannot start with 0. If 0 is among the digits, the first box loses one choice. Using 0, 1, 2, 3 without repetition, 3-digit numbers = 3 (not 0) × 3 × 2 = 18.

[[fig:2]]

Different posts for different people is box filling too. Suppose 3 different prizes go to 3 of 7 students, one prize each. The first prize has 7 choices, the second 6 and the third 5, so there are 7 × 6 × 5 = 210 ways.

A permutation is an arrangement: the same things in a different order give a different result. You already know the box method. The formulas below are that same box method written in short.

1. Arranging r things out of n different things. The first place has n choices, the second n − 1, and so on for r places. So
ⁿP_r = n × (n − 1) × … (r factors) = n!(n − r)!
For example, ⁷P₂ = 7 × 6 = 42 and ⁵P₃ = 5 × 4 × 3 = 60. Arranging all n things gives ⁿP_n = n!.

2. When some things are identical. Swapping two identical things does not make a new arrangement, so those swaps have to be divided out. If among n things p are alike of one kind, q alike of a second kind and r alike of a third kind, then
Arrangements = n!p! × q! × r!
The word LETTER has 6 letters with E twice and T twice, so it has 6!2! × 2! = 7204 = 180 arrangements.

3. "Always together": the glue method. Glue the things that must stay together into one block. Arrange the block with the other things, then arrange the things inside the block. In TRIANGLE the vowels are I, A, E. Glue them: T, R, N, G, L, [IAE] = 6 units, which go in 6! ways. Inside the block the 3 vowels go in 3! ways. Total = 6! × 3! = 4320. If the glued letters are identical (like two O's), the inside arrangement is 2!2! = 1, not 2.

[[fig:0]]

4. "Never together" or "separated": the gap method. Arrange the free things first. Gaps form between them and at both ends. Put the restricted things in different gaps, so no two of them can touch. Say 4 boys and 2 girls sit in a row with no two girls together. The boys go in 4! = 24 ways and create 5 gaps: _ B _ B _ B _ B _. The 2 girls take 2 of these 5 gaps in ⁵P₂ = 20 ways. Total = 24 × 20 = 480. With k free things you always get k + 1 gaps.

[[fig:1]]

5. Fixed or restricted positions. Put the fixed letter in its place first, then arrange the rest. Arrangements of TRACE that begin with T = 4! = 24, since T stays put and the other 4 letters move. Arrangements in which T is not first = 5! − 4! = 120 − 24 = 96. A "not at this place" question can be done directly (count the allowed places) or as total − unwanted.

6. Circular arrangements. A row has a first and a last seat. A round table has no starting point, so moving everyone one seat round gives the same arrangement. Fix one person as the reference and arrange the other n − 1 as if in a line:
n people around a round table = (n − 1)!
Radhika and 5 friends (6 people) at a round table can sit in 5! = 120 ways. If clockwise and anticlockwise count as the same, as in a necklace or garland that can be turned over, divide by 2: 7 different beads on a necklace give 6!2 = 360.

[[fig:2]]

Round table with a condition. The glue method and the subtraction method work at a round table too; only the final count uses (n − 1)! in place of n!. If two particular people must sit together, glue them into one unit: with n people there are now n − 1 units, which sit in (n − 2)! ways, and the pair can swap in 2! ways. If those two must not sit together, subtract: (n − 1)! − 2 × (n − 2)!. For men and women sitting alternately, seat the men first in (m − 1)! ways; this fixes m gaps between them, and the women fill these gaps in m! ways. Take Radhika and 5 friends at a round table with Radhika and Kavya always side by side: 5 units give 4! = 24 seatings, and the two of them swap places, so 48 ways. At a round table, fix one unit first and arrange the rest in a line. A necklace or garland can also be turned over, so after all this, divide by 2.

Shortest paths on a grid. On a grid of streets, a shortest route from the bottom-left corner A to the top-right corner B uses only two kinds of steps: R (one block to the right) and U (one block up). If B is m blocks to the right and n blocks up, every shortest route is just a word made of m R's and n U's, and every such word is a route. So the routes are the arrangements of identical letters:
Shortest paths = (m + n)!m! × n! = ^{m + n}C_m

[[fig:3]]

On a 4 × 3 grid there are 7!4! × 3! = 35 shortest routes. If the route must pass through a point C, multiply the routes A → C by the routes C → B, because the two halves are independent (AND means multiply).

A combination is a selection: only which things are chosen matters, not the order in which they are picked. Radhika, Aman and Ravi make the same team whether Radhika is picked first or last.

The formula and where it comes from. Arranging r things out of n gives ⁿP_r. But every group of r things has been counted r! times there, once for each order. So divide by r!:
ⁿC_r = ⁿP_rr! = n!r! × (n − r)!
For instance, ⁸C₂ = 8 × 72 × 1 = 28 and ⁹C₃ = 9 × 8 × 73 × 2 × 1 = 84. The quick way: write r factors on top starting from n and going down, and r! below.

Results that save time.

• ⁿC₀ = ⁿC_n = 1, ⁿC₁ = n.
• ⁿC_r = ⁿC_{n − r}. Choosing the 3 people out of 12 who go is the same as choosing the 9 who stay back, so ¹²C₉ = ¹²C₃ = 220. Always work with the smaller one.
• If ⁿC_a = ⁿC_b and a ≠ b, then a + b = n.
• ⁿC₀ + ⁿC₁ + … + ⁿC_n = 2ⁿ, because each thing is either taken or left. Selecting at least one thing from n = 2ⁿ − 1.

[[fig:0]]

Committees with conditions. Split the question into cases, multiply inside each case, add the cases.

• "At least 2 women" = 2 women OR 3 women OR …
• "At most 1 singer" = 0 singers OR 1 singer.
• A particular person always included: put that person in and choose the rest, ^{n − 1}C_{r − 1}. Always excluded: ^{n − 1}C_r.

Take 4 men and 3 women, and a team of 3 with at least 2 women: (2W, 1M) + (3W) = ³C₂ × ⁴C₁ + ³C₃ = 12 + 1 = 13.
When the wanted side has many cases, count the unwanted side and subtract it from the total.

[[fig:1]]

Selection followed by arrangement. Some questions first choose and then order, for example choosing 4 songs out of 10 and deciding the order in which they are sung. The answer is ⁿC_r × r! = ⁿP_r. If the condition is about which things are chosen (two items must not both be picked), apply it at the selection stage and then multiply by r!.

Geometry counts are pure combinations.

• Straight lines through n points, no three collinear = ⁿC₂.
• Triangles from n points, no three collinear = ⁿC₃. Any 3 vertices of a polygon also form a triangle, so a polygon with n vertices gives ⁿC₃ triangles.
• If m of the n points are collinear: lines = ⁿC₂ − ^mC₂ + 1, triangles = ⁿC₃ − ^mC₃. Eight points with 3 on one line give ⁸C₃ − ³C₃ = 56 − 1 = 55 triangles.
• Diagonals of an n-sided polygon = ⁿC₂ − n = n(n − 3)2. A 12-sided polygon has 12 × 92 = 54 diagonals.
• Handshakes among n people, each pair once = ⁿC₂, so 9 people make 36 handshakes. If every pair exchanges gifts (each gives one to the other), it becomes ⁿP₂ = n(n − 1).

[[fig:2]]

Matches in a tournament. A match is a pair of teams, so a league in which every team plays every other team once has ⁿC₂ matches, exactly like handshakes. If every pair plays twice, home and away, the order matters (A at home against B is not B at home against A), and the count becomes ⁿP₂ = n(n − 1). In a knockout, every match removes exactly one team and only the champion is never removed, so n teams need n − 1 matches; no formula for pairs is needed. Say Radhika's school runs a league of 6 houses with one match per pair: ⁶C₂ = 15 matches.

Pascal's rule and two more identities. Mark one particular person among n + 1 people. A group of r either leaves this person out (ⁿC_r ways) or includes the person and picks r − 1 others (ⁿC_{r − 1} ways). So
ⁿC_r + ⁿC_{r − 1} = ^{n + 1}C_r
This is the rule that builds Pascal's triangle, where each number is the sum of the two above it. Two more results help with ratio questions:

• ⁿC_rⁿC_{r − 1} = n − r + 1r
• r × ⁿC_r = n × ^{n − 1}C_{r − 1}

For example, ⁷C₂ + ⁷C₃ = ⁸C₃ = 56, which you can check: 21 + 35 = 56. Two neighbouring terms of the same n add up to one term of n + 1.

Probability measures how likely something is, on a scale from 0 to 1. An event that can never happen has probability 0, an event that is certain has probability 1, and everything else lies in between.

A few words first. An experiment is the act we perform: tossing a coin, rolling a die, drawing a card. The sample space S is the list of all possible outcomes. An event E is the group of outcomes we are interested in. When all outcomes are equally likely,
P(E) = n(E)n(S) = favourable outcomestotal outcomes
So probability is two counts and one division, which is exactly why P&C came first.

Coins. One coin gives {H, T}, 2 outcomes. With n coins (or one coin tossed n times) there are 2ⁿ outcomes. Exactly r heads can come in ⁿC_r ways, since we choose which r tosses show heads. With 4 coins, P(exactly 2 heads) = ⁴C₂2⁴ = 616 = 38.

[[fig:0]]

Dice. One die gives {1, 2, 3, 4, 5, 6}. Two dice give 6 × 6 = 36 ordered outcomes, and (2, 5) is different from (5, 2). The number of ways to get each sum:
| Sum | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Ways | 1 | 2 | 3 | 4 | 5 | 6 | 5 | 4 | 3 | 2 | 1 |
For sums up to 7, ways = sum − 1; after 7, ways = 13 − sum. Doublets (the same number on both dice) = 6. If Radhika rolls two dice, P(sum 8) = 536.

[[fig:1]]

Playing cards. A pack has 52 cards in 4 suits of 13 each. Spades ♠ and clubs ♣ are black (26); hearts ♥ and diamonds ♦ are red (26). Each suit has A, 2–10, J, Q, K. The face cards are J, Q and K: 3 per suit, so 12 in the pack (6 red, 6 black). There are 4 aces, 4 kings and so on. P(a red face card) = 652 = 326.

[[fig:2]]

Balls from a bag. When several balls are drawn together, use combinations for both counts. A bag has 4 red and 6 green balls and 2 are drawn. P(both green) = ⁶C₂¹⁰C₂ = 1545 = 13. Committees and teams chosen at random work the same way.

Odds. Odds in favour of E = favourable : unfavourable = a : b, so P(E) = aa + b. Odds against E = b : a.

Days of the week. A non-leap year has 52 weeks + 1 extra day; a leap year has 52 weeks + 2 extra days. The 2 extra days of a leap year are one of 7 pairs (Sun–Mon, Mon–Tue, …, Sat–Sun), and 2 of these pairs contain a Sunday. So P(53 Sundays in a leap year) = 27, and in a non-leap year it is 17.

The addition rule (OR). For any two events A and B,
P(A or B) = P(A) + P(B) − P(A and B)
Why subtract? The outcomes that belong to both A and B were counted once in P(A) and again in P(B), so the double count is removed once. Draw one card from a pack: P(king or heart) = 452 + 1352 − 152 = 1652 = 413. The king of hearts sat in both groups, so it is taken out once.

[[fig:0]]

If A and B cannot happen together (mutually exclusive), P(A and B) = 0 and P(A or B) = P(A) + P(B). A sum of 2 or a sum of 12 with two dice: 136 + 136 = 118.

The same idea with counts. "Divisible by a or b" uses the same rule on counts: n(a or b) = n(a) + n(b) − n(both). "Divisible by both a and b" means divisible by LCM(a, b). From 1 to 50, 16 numbers are divisible by 3, 10 by 5 and 3 by both (that is, by 15). Divisible by 3 or 5 = 16 + 10 − 3 = 23, so the probability is 2350. "Divisible by exactly one of them" = 23 − 3 = 20, because the common ones have to be removed from the union as well.

[[fig:1]]

The complement rule (NOT). An event either happens or it does not, so
P(not A) = 1 − P(A)
This is the most useful shortcut in probability. Whenever the wanted event has many cases and its opposite has very few, find the opposite and subtract from 1.

"At least one" = 1 − "none". Toss 3 coins. P(at least one head) = 1 − P(no head) = 1 − 18 = 78. Listing seven cases is slow; one subtraction is quick.

[[fig:2]]

Sometimes the complement is hidden inside a story. Ask yourself which simpler event has to fail for your event to happen. Once you see that, the question takes one line.

Independent events (AND). Two events are independent when one happening does not change the chance of the other: two different coins, two different dice, two people solving a problem separately, two sensors working on their own. For independent events
P(A and B) = P(A) × P(B)
Radhika solves a puzzle with probability 12 and Aman with probability 13, independently. P(both solve) = 12 × 13 = 16. P(neither solves) = 12 × 23 = 13. So P(the puzzle gets solved) = P(at least one solves) = 1 − 13 = 23. The complement rule of the last type and the multiplication rule work together here.

[[fig:0]]

Without replacement: dependent events. If a ball is drawn and not put back, the second draw depends on the first. Still multiply, but update the numbers each time. A bag has 4 red and 3 white balls, and two are drawn one after the other without replacement. P(both red) = 47 × 36 = 27.

[[fig:1]]

Repeated independent trials: exactly r successes out of n. If each trial succeeds with probability p (and fails with q = 1 − p), then for exactly r successes we choose which r trials succeed (ⁿC_r ways), and each such pattern has probability p^r q^{n − r}:
P(exactly r) = ⁿC_r × p^r × q^{n − r}
A coin tossed 3 times: P(exactly 2 heads) = ³C₂ × (12)² × 12 = 38. For "at least r", add the cases r, r + 1, …, n, or use 1 − (the few cases below r).

Total probability: one event, several routes. Suppose an item can come from machine A, B or C. A defective item is "from A and defective" OR "from B and defective" OR "from C and defective". AND multiplies, OR adds:
P(defective) = P(A) × P(D | A) + P(B) × P(D | B) + P(C) × P(D | C)
P(D | A) is read "probability of defective, given that it came from A". It is simply the defect rate of A.

The reverse question (Bayes' idea). If an item turns out defective, which machine did it probably come from? Take that machine's route and divide by the total:
P(A | D) = P(A) × P(D | A)P(defective)
Two boxes are equally likely to be chosen; box I has 10% defective items and box II has 30%. P(defective) = 0.5 × 0.1 + 0.5 × 0.3 = 0.2. If an item is defective, P(it came from box I) = 0.050.2 = 0.25.

[[fig:2]]

Expected value: the long-run average. If an outcome x happens with probability P(x), then E = Σ x × P(x). For one fair die, E = 1 + 2 + 3 + 4 + 5 + 66 = 3.5. If a trial succeeds with probability p, the expected number of trials until the first success is 1p; for a six on a die that is 6 throws. For longer patterns, such as two heads in a row, write one equation for each stage you can be in and solve them together. One of the practice questions below is worked out this way.

Conditional probability: when you already know something. Sometimes the question tells you a fact about the outcome first: the card drawn is red, the sum is 8, at least one child is a boy. That fact shrinks the sample space. Count only inside the new, smaller space:
P(A | B) = P(A and B)P(B) = n(A and B)n(B)
A card drawn from a pack turns out to be a face card. What is the chance that it is a king? Now there are only 12 possible cards and 4 of them are kings, so P = 412 = 13, not 452. Read the word given (or it is known that) as: throw away every outcome that does not fit, then count again.

In a dictionary, words are listed by their first letter, then by the second letter, and so on. So the rank of a word among all the arrangements of its letters is just: (number of words that come before it) + 1. We count those earlier words place by place, using the box method you already know.

Method. Write the letters of the word in alphabetical order. Look at the first letter of the given word. Every unused letter that is smaller than it could have started an earlier word, and each such start can be followed by the remaining letters in (letters left)! ways. Add these counts, then fix the first letter and repeat the same thing for the second place, the third place and so on. At the end, add 1 for the word itself.

[[fig:0]]

Take PALM. In alphabetical order the letters are A, L, M, P. Words starting with A, L or M all come before PALM: 3 × 3! = 18. Now fix P. The second letter of PALM is A, and no unused letter is smaller than A, so 0. Fix PA: of L and M, nothing is smaller than L, so 0. Only PALM is left. Rank = 18 + 1 = 19.

Repeated letters. If a letter repeats, the words after a fixed start are counted with the repeated-letter formula k!p!, and a repeated letter is counted only once as a starting choice. In BOOK the letters are B, K, O, O. Starting with B, nothing is smaller, so 0. After B, the letter K is smaller than O: BK followed by O, O gives 2!2! = 1 word. After BO, K is again smaller than O: BOK followed by O gives 1 word. Rank = 0 + 1 + 1 + 1 = 3, and the list BKOO, BOKO, BOOK agrees.

Numbers in ascending order are the same question with digits in place of letters: the position of a number among all the numbers formed by some digits is its rank. Rank = (words before it) + 1; never forget the final 1.

First ask two questions: are the objects identical or different, and do we care who gets them (named people or boxes) or only how they are grouped? The answer decides the formula.

1. Identical objects to different people (stars and bars). Line up the n identical objects as dots and put r − 1 bars among them; the dots before the first bar go to the first person, the dots between the first and second bar to the second person, and so on. Every arrangement of n dots and r − 1 bars is one distribution, so
Ways (anyone may get none) = ^{n + r − 1}C_{r − 1}

[[fig:0]]

If each person must get at least one, first hand one object to each person. The remaining n − r objects can then be shared freely: ^{n − 1}C_{r − 1} ways. This is the same as counting positive whole-number solutions of x₁ + x₂ + … + x_r = n, while the first formula counts the solutions with x ≥ 0. If each person must get at least k, hand out k to everyone first and share what is left.

2. Different objects to different people, no limit. Each object chooses its person independently, so the count is rⁿ, the box method of the first type.

3. Different objects into groups of fixed sizes. Choose the members of each group one after another: n different objects into groups of sizes p, q, s (all sizes different, p + q + s = n) can be made in n!p! × q! × s! ways. If some groups have the same size and are not named, swapping those groups gives nothing new, so divide also by m! for m equal groups: 6 different books into 3 groups of 2 = 6!(2!)³ × 3! = 15. If the groups then go to named people, multiply back by the number of ways to hand them out: 15 × 3! = 90.

[[fig:1]]

Take Radhika sharing 5 identical toffees among her 3 friends. With no condition there are ⁷C₂ = 21 ways; if each friend must get at least one, there are ⁴C₂ = 6 ways. Identical objects use stars and bars; different objects use factorials.