Permutation, Combination & Probability

✨ Login to track

medium importance~1 Q in Tier 130 formulas⚡ 13 shortcuts6 subtopics

Overview Learn (6)Formulas (30)Examples (5)Practice (74)

Every formula in this topic, grouped by subtopic. Print it and pin it above your desk.

Counting Principles: Product & Sum Rules

Product rule

m \times n

$m$ options for step 1 and $n$ for step 2, joined by 'and'.

Sum rule

m + n

Two cases that cannot happen together, joined by 'or'.

Strings with repetition

n^r

$r$ slots from $n$ items, repeats allowed.

Arrangements without repetition

n(n-1)(n-2)\ldots(n-r+1)

$r$ ordered slots, no item reused.

Permutations: Arrangements

Arrange r of n

^{n}P_r = \frac{n!}{(n-r)!}

Order matters; $0! = 1$.

All letters of a word

All $n$ letters distinct.

Word with repeated letters

\frac{n!}{p!\,q!\,r!}

$p$, $q$, $r$ are the repeat counts of the repeated letters.

Round table

(n-1)!

Fix one person; rotations are the same seating.

Necklace or garland

\frac{(n-1)!}{2}

Flips look identical, so divide by 2.

Combinations: Selections

Select r of n

^{n}C_r = \frac{n!}{r!\,(n-r)!}

Link with nPr

^{n}C_r = \frac{^{n}P_r}{r!}

Divide arrangements by $r!$ for selections.

Symmetry

^{n}C_r = ^{n}C_{n-r}

Flip a large lower index before computing.

Sum of all nCr

\sum_{r=0}^{n} {}^{n}C_r = 2^n

The number of subsets of an $n$-element set.

Pairs

^{n}C_2 = \frac{n(n-1)}{2}

Handshakes, league matches, diagonals.

Distribution & Grouping

Groups of sizes a, b, c

\frac{n!}{a!\,b!\,c!}

$n$ different people; divide again by $k!$ for $k$ equal groups.

Identical items, each at least one

^{n-1}C_{r-1}

$n$ items, $r$ people, no one empty.

Identical items, zeros allowed

^{n+r-1}C_{r-1}

Different items to n people

n^r

$r$ different items, each choosing a person.

2n people into n pairs

\frac{(2n)!}{2^n\,n!}

One or more selections

2^n - 1

$n$ different items, at least one taken.

Probability: Core Rules

Classical definition

P(E) = \frac{m}{n}

$m$ favourable of $n$ equally likely outcomes.

Complement

P(\bar{E}) = 1 - P(E)

'Not the event'.

Addition rule

P(A \cup B) = P(A) + P(B) - P(A \cap B)

Subtract the overlap once.

Multiplication (independent)

P(A \cap B) = P(A) \times P(B)

For independent events.

At least one

P(\text{at least one}) = 1 - P(\text{none})

The complement of 'none'.

Dice, Cards & Coins

Coin outcomes

2^n

$n$ fair coins tossed together.

Two dice outcomes

6 \times 6 = 36

Ordered pairs, not unordered.

Three dice outcomes

6^3 = 216

At least one six (three dice)

1 - \left(\frac{5}{6}\right)^3 = \frac{91}{216}

Two-card pairs

^{52}C_2 = 1326

Total for any two-card question.