Unit 5: Permutation, Combination and Probability

I. Orientation

Permutation, combination, and probability are mathematical tools for counting possible outcomes and measuring the likelihood of events. The central distinction is whether order matters: arrangements use permutations, while selections use combinations. Probability then compares favourable outcomes with the complete set of possible outcomes under stated assumptions.

• Fundamental convention: Outcomes are counted systematically, without omission or repetition.
• Order: “AB” and “BA” are different in an arrangement but identical in a selection.
• Sample space: The set (S) contains every possible outcome of an experiment.
• Event: An event (E) is a subset of (S); it may contain one or several outcomes.
• Finite equally likely model: When all outcomes are equally likely,
  [
  P(E)=\frac{n(E)}{n(S)}
  ]
  where (n(E)) is the number of favourable outcomes.
• Factorial convention: (n!=n(n-1)(n-2)\cdots1), with (0!=1).
• Independence assumption: Separate trials are independent when the result of one does not alter the probabilities of another.

II. Principles of Counting and Combinatorial Methods

This section develops the counting rules used to determine the number of selections and arrangements before probability is calculated.

A. Principles of counting

The addition and multiplication principles provide the basic framework for counting disjoint alternatives and successive choices.

• Addition principle: If one task can be completed in (m) ways or another disjoint task in (n) ways, the total is (m+n).
  • Example: choosing one dessert from 4 cakes or 3 ice creams gives (4+3=7) choices.
• Multiplication principle: If successive stages have (m) and (n) choices respectively, the total is (mn).
  • Example: 5 shirts and 3 trousers produce (5\times3=15) outfits.
• Complementary counting: Count “not required” outcomes and subtract from the total:
  [
  n(\text{required})=n(\text{total})-n(\text{unwanted}).
  ]
• Inclusion–exclusion: For overlapping sets (A) and (B),
  [
  n(A\cup B)=n(A)+n(B)-n(A\cap B).
  ]

B. Problems based on selection

Selection problems use combinations because the order of selected objects is irrelevant.

• Combination formula: Selecting (r) objects from (n) distinct objects gives
  [
  ^nC_r=\frac{n!}{r!(n-r)!}.
  ]
  Here, (n) is the total number of objects and (r) is the number selected.
• Useful identities:
  [
  ^nCr=^nC{n-r},\qquad ^nC_0=^nC_n=1.
  ]
• Restrictions: If at least one object from a group is required, count the unrestricted selections minus selections containing none from that group.
• Worked example: Selecting 3 students from 8 gives
  [
  ^8C_3=\frac{8!}{3!5!}=56.
  ]
  The result does not distinguish the order in which the three students are chosen.

C. Problems based on arrangement

Arrangement problems use permutations because position and order matter.

• Distinct objects: Arranging (r) objects selected from (n) gives
  [
  ^nP_r=\frac{n!}{(n-r)!}.
  ]
• All objects: The number of arrangements of (n) distinct objects is (n!).
• Repeated objects: If (n) objects include repetitions (p,q,\ldots), then
  [
  \frac{n!}{p!q!\cdots}.
  ]
• Restriction method: Fix a required object or form a block for objects that must remain together, then arrange the resulting units.
• Worked example: The letters of “LEVEL” have (5) letters, with L and E repeated twice:
  [
  \frac{5!}{2!2!}=30.
  ]

D. Problems based on numbers

Number problems require attention to place value, leading zeroes, and divisibility conditions.

• Leading digit: A zero cannot occupy the first position of a multi-digit number; subtract arrangements beginning with zero or choose the first digit separately.
• Distinct-digit numbers: For a (k)-digit number formed from (n) available digits, use a first-place count followed by permutation of remaining places.
• Divisibility: Apply digit rules before arranging; for example, a number divisible by 5 must end in 0 or 5.
• Worked example: Four-digit numbers from (1,2,3,4,5), without repetition, number
  [
  ^5P_4=5\times4\times3\times2=120.
  ]
  Since zero is absent, no leading-digit correction is needed.

E. Problems based on words

Word problems count letter arrangements, accounting for repeated letters and positional restrictions.

• All letters distinct: A word with (n) different letters has (n!) arrangements.
• Repeated letters: Divide by factorials of repeated frequencies, as in
  [
  \frac{n!}{p!q!}.
  ]
• Vowels together: Treat all vowels as one block, arrange the block with consonants, then arrange the vowels internally.
• Vowels separated: Arrange consonants first and place vowels in the gaps between or around them.
• Worked example: “APPLE” has 5 letters with P repeated twice, so its arrangements are
  [
  \frac{5!}{2!}=60.
  ]

F. Geometric applications

Geometry-based counting uses positions, lines, diagonals, and polygons as combinatorial objects.

• Line segments: (n) points on a line determine
  [
  ^nC_2
  ]
  segments, since each segment needs two endpoints.
• Triangles: (n) points in general position determine
  [
  ^nC_3
  ]
  triangles, provided no three are collinear.
• Diagonals of a polygon: An (n)-gon has
  [
  ^nC_2-n=\frac{n(n-3)}2
  ]
  diagonals; subtracting (n) removes the sides.
• Worked example: A hexagon has (\frac{6(6-3)}2=9) diagonals.

G. Circular arrangement

Circular arrangements differ because rotations of the same arrangement are considered identical.

• Distinct objects around a circle: The number is
  [
  (n-1)!.
  ]
  Fixing one object removes the (n) equivalent rotations.
• Clockwise and anticlockwise distinction: If reflections are also considered identical, the number becomes
  [
  \frac{(n-1)!}{2}
  ]
  for (n>2).
• Adjacent objects: Treat specified adjacent objects as a block, remembering that the block may have internal orders.
• Worked example: Six people around a round table can sit in
  [
  (6-1)!=120
  ]
  distinct ways when rotations alone are identical.

III. Probability and Standard Random Experiments

Probability assigns numerical values to events and applies the counting methods above to coins, dice, and cards.

A. Concept of probability

Probability measures the chance that an event occurs, ranging from impossible to certain.

• Classical probability: For equally likely outcomes,
  [
  P(E)=\frac{n(E)}{n(S)}.
  ]
• Bounds:
  [
  0\le P(E)\le1,\qquad P(S)=1,\qquad P(\varnothing)=0.
  ]
• Complement rule:
  [
  P(E^c)=1-P(E),
  ]
  where (E^c) means that (E) does not occur.
• Addition rule:
  [
  P(A\cup B)=P(A)+P(B)-P(A\cap B).
  ]
• Interpretation: (P(E)=0.7) means the event has a 70% chance under the stated probability model.

B. Classification of events

Events are classified according to their possibility, relationship, and influence on one another.

• Simple event: Contains one outcome, such as rolling a 6 on one die.
• Compound event: Contains several outcomes, such as rolling an even number: ({2,4,6}).
• Certain and impossible events: The sample space (S) is certain; the empty set (\varnothing) is impossible.
• Mutually exclusive events: (A\cap B=\varnothing); for one die, rolling 2 and rolling 5 together is impossible.
• Exhaustive events: Their union covers (S); odd and even outcomes exhaust a standard die.
• Independent events: (P(A\cap B)=P(A)P(B)).
• Dependent events: The occurrence of one changes the probability of the other, as in drawing cards without replacement.

C. Problems based on coins

Coin problems model repeated binary trials with outcomes Head (H) and Tail (T).

• Equally likely outcomes: For (n) fair tosses, the sample space has (2^n) ordered outcomes.
• Exactly (r) heads: The number of outcomes is
  [
  ^nC_r,
  ]
  because the positions of the (r) heads are selected.
• Probability of exactly (r) heads:
  [
  P(r\text{ heads})=\frac{^nC_r}{2^n}.
  ]
• Worked example: In 4 fair tosses, exactly 2 heads occur with probability
  [
  \frac{^4C_2}{2^4}=\frac6{16}=\frac38.
  ]
• At least one head: Use the complement:
  [
  P(\text{at least one H})=1-P(\text{all T})=1-\frac1{2^n}.
  ]

D. Problems based on dice

Dice problems use ordered pairs or tuples when multiple dice are rolled.

• One die: The sample space is ({1,2,3,4,5,6}), with each outcome having probability (1/6).
• Two dice: There are (6\times6=36) ordered outcomes; ((2,5)) and ((5,2)) are distinct outcomes.
• Sum events: A sum of 7 has 6 favourable pairs:
  [
  (1,6),(2,5),(3,4),(4,3),(5,2),(6,1),
  ]
  so its probability is (6/36=1/6).
• Parity: The probability of an even number on one fair die is (3/6=1/2), since outcomes are (2,4,6).
• Important distinction: “At least one 6” in two throws is best found by complement:
  [
  1-\left(\frac56\right)^2=\frac{11}{36}.
  ]

E. Problems based on cards

Card probabilities depend on the standard deck composition and whether cards are replaced.

• Standard deck: There are 52 cards, 4 suits, 13 ranks, 26 red cards, 26 black cards, and 4 aces.
• One-card probability: The probability of drawing an ace is
  [
  \frac4{52}=\frac1{13}.
  ]
• Combination counting: A 5-card hand is selected in
  [
  ^{52}C_5
  ]
  ways because order within a hand is irrelevant.
• Worked example: The probability of a 5-card hand containing exactly two aces is
  [
  \frac{^4C_2\,^{48}C_3}{^{52}C_5}.
  ]
• Replacement: With replacement, the deck returns to 52 cards and trials are usually independent; without replacement, the denominator and probabilities change after each draw.

IV. Conditional Probability

Conditional probability measures an event when information about another event is already known.

A. Conditional probability

For events (A) and (B), with (P(B)>0), the probability of (A) given (B) is

[
P(A\mid B)=\frac{P(A\cap B)}{P(B)}.
]

Here, (P(A\mid B)) means the probability of (A) under the condition that (B) has occurred.

• Reduced sample space: Knowing (B) occurs restricts attention to outcomes in (B).
• Multiplication rule:
  [
  P(A\cap B)=P(B)P(A\mid B)=P(A)P(B\mid A).
  ]
• Independence test: (A) and (B) are independent when
  [
  P(A\mid B)=P(A),
  ]
  equivalently (P(A\cap B)=P(A)P(B)).
• Worked example: From a deck, the probability that the second card is an ace given that the first was an ace is
  [
  P(\text{second ace}\mid\text{first ace})=\frac3{51}=\frac1{17},
  ]
  because one ace and one card have already been removed.
• Bayes’ theorem: If (A_1,A_2,\ldots,A_n) partition the sample space,
  [
  P(A_i\mid B)=\frac{P(A_i)P(B\mid A_i)}
  {\sum_j P(A_j)P(B\mid A_j)}.
  ]
  This reverses the direction of conditional information and is useful in classification and diagnostic problems.