Permutation and Combination; Probability

Permutation and Combination

19.1 Fundamental Counting Principle

If task 1 can be done in m ways and task 2 in n ways:

If BOTH needed (AND): m × n ways (Multiplication)
If EITHER needed (OR): m + n ways (Addition)

19.2 Factorial

n! = n × (n-1) × (n-2) × ... × 2 × 1

Special cases: 0! = 1, 1! = 1

19.3 Permutation (Order Matters)

ⁿPᵣ = n! / (n-r)!

Reads: "n choose r with order"

Example: ⁵P₃ = 5!/(5-3)! = 5!/2! = 60

When items are repeated:

Permutations of n items where a items are same, b items are same:

= n! / (a! × b!)

Example: MATHEMATICS (11 letters, M×2, A×2, T×2):

= 11! / (2! × 2! × 2!) = 4,989,600

19.4 Combination (Order Doesn't Matter)

ⁿCᵣ = n! / [r! × (n-r)!]

Key Properties:

ⁿCᵣ = ⁿC(n-r)
ⁿC₀ = ⁿCₙ = 1
ⁿC₁ = n
ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ (Pascal's Identity)

19.5 Permutation vs Combination

Situation	Use
Arrangement (order matters)	Permutation
Selection (order doesn't matter)	Combination
Passwords, rankings, words	Permutation
Committees, teams, groups	Combination
Sitting arrangements (line)	Permutation
Sitting arrangements (circle)	(n-1)!

19.6 Special Cases

Circular Arrangement

n objects in a circle = (n-1)! ways
n objects on a necklace (both sides identical) = (n-1)! / 2

Choosing with Restrictions

At least / at most problems: Use complementary counting

At least 1 = Total - (choosing

At most 2 = Choose 0 + Choose 1 + Choose 2

Example: From 6 men 4 women, committee of 5 with at least 2 women:

= (4C2)(6C3) + (4C3)(6C2) + (4C4)(6C1) + (4C5)(6C0) Wait: at least 2 women:
2W + 3M = 4C2 × 6C3 = 6 × 20 = 120
3W + 2M = 4C3 × 6C2 = 4 × 15 = 60
4W + 1M = 4C4 × 6C1 = 1 × 6 = 6
Total = 186

Words from a Word (vowels together)

Treat vowels as a single unit
Arrange (consonants + 1 unit) + arrange vowels within unit

Example: OPTICAL (7 letters, vowels O, I, A):

Vowels together: treat OIA as 1 block → 5! arrangements
Vowels within block: 3! = 6
Total = 5! × 3! = 120 × 6 = 720

19.7 nPr and nCr Quick Lookups

n	r	nPr	nCr
5	2	20	10
5	3	60	10
6	2	30	15
6	3	120	20
10	2	90	45
10	3	720	120
50	2	2450	1225

Probability

20.1 Basic Definition

Probability = Favorable Outcomes / Total Outcomes

P(E) ranges from 0 to 1
P(sure event) = 1
P(impossible event) = 0
P(E) + P(E') = 1 → P(E') = 1 - P(E) (Complementary events)

20.2 Sample Spaces

Coin Toss

1 coin: S = {H, T}, n(S) = 2
2 coins: S = {HH, HT, TH, TT}, n(S) = 4
3 coins: n(S) = 8
n coins: n(S) = 2ⁿ

Dice Roll

1 die: S = {1,2,3,4,5,6}, n(S) = 6
2 dice: n(S) = 36

Card Deck (52 cards)

4 suits: Spades ♠, Hearts ♥, Diamonds ♦, Clubs ♣
Each suit: 13 cards (A, 2-10, J, Q, K)
Red cards: Hearts + Diamonds = 26
Black cards: Spades + Clubs = 26
Face cards: J, Q, K in each suit = 12 total
Aces: 4 total

20.3 Key Probability Formulas

Event	Formula
P(A or B) — Union	P(A) + P(B) - P(A∩B)
P(A and B) — Intersection	P(A) × P(B) [if independent]
P(A	B) — Conditional
Mutually exclusive events	P(A∩B) = 0, P(A∪B) = P(A) + P(B)
Independent events	P(A∩B) = P(A) × P(B)

20.4 Common Probability Examples

Drawing from a bag of balls:

P(red) = (number of red balls) / (total balls)

Drawing cards:

P(face card) = 12/52 = 3/13
P(king of red) = 2/52 = 1/26
P(queen or king) = 8/52 = 2/13

Rolling dice:

P(sum = 7 with 2 dice) = 6/36 = 1/6 (pairs: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1)
P(at least one six) = 1 - P(no six) = 1 - (5/6)² = 11/36