Anshid

Module IV — Combinatorics and Discrete Probability

← Back to Mathematical Logic, Set Theory and Combinatorics

Course: MAT1MN104 — Mathematical Logic, Set Theory and Combinatorics Hours: 11 | Textbook Sections: 6.1, 6.2, 6.4, 6.8 (Thomas Koshy, Discrete Mathematics with Applications, 1/e)

Notation: permutations $P(n,r)$, combinations $C(n,r)$, probability $p(E) = |E|/|S|$.

1. The Fundamental Counting Principles

Addition principle: if mutually exclusive tasks $T_1,\ldots,T_k$ can be done in $m_1,\ldots,m_k$ ways, “$T_1$ or $T_2$ or … or $T_k$” can be done in $m_1+m_2+\cdots+m_k$ ways.

Example. One more course needed: 15 English or 10 French or 6 German (no overlap) → $15+10+6 = 31$ ways.

Theorem 6.2 — Inclusion-Exclusion (for tasks): if task A can be done $m$ ways, B in $n$ ways, and both simultaneously in $k$ ways, “A or B” can be done in $m+n-k$ ways.

Example. Deal a king or a black card: king in 4 ways, black card in 26 ways, both (black king) in 2 ways → $4+26-2 = 28$ ways.

Theorem 6.3 — Multiplication principle: task $T$ = subtask $T_1$ followed by $T_2$; $T_1$ in $m_1$ ways, and for each, $T_2$ in $m_2$ ways → T done in $m_1m_2$ ways (extends to any number of sequential subtasks).

(This is exactly why $|A\times B| = |A|\cdot|B|$ — choosing $(a,b)$ is “choose a, then choose b”.)

Worked example. Password = 2 letters + 3 digits (repetition allowed): $26\times 26\times 10\times 10\times 10 = 676{,}000$.

Key skill: “and” → multiply; “or, mutually exclusive” → add; “or, overlapping” → inclusion-exclusion (subtract overlap).

(Exam scope: Section 6.1 examinable except Example 6.7.)

2. Permutations

A permutation is an ordered arrangement — abc ≠ acb.

Definition. $P(n,r)$ = number of ordered arrangements (r-permutations) of r elements chosen from n distinct elements.

Theorem 6.4: $P(n,r) = \dfrac{n!}{(n-r)!}$

Why: first position: n ways; second: n−1 ways (one used up); …; rth position: n−r+1 ways. Multiply: $n(n-1)\cdots(n-r+1) = \dfrac{n!}{(n-r)!}$.

⚠️ Compute as $n(n-1)\cdots(n-r+1)$ directly for large n — don’t compute both factorials separately. E.g. $P(25,5) = 25\cdot24\cdot23\cdot22\cdot21 = 6{,}375{,}600$.

Worked example (Oct 2024). Words from scrambling SCRAMBLE (8 distinct letters): $P(8,8) = 8! = 40{,}320$.

2.1 Cyclic Permutations

Arranging around a circle differs from a line — rotations are the “same” arrangement.

Theorem 6.6: cyclic permutations of $n$ distinct items = $(n-1)!$.

Why: fix the first item’s position (removes rotation ambiguity); remaining $n-1$ items fill $n-1$ positions: $(n-1)!$ ways.

Example. 5 zinnias in a circle: $(5-1)! = 4! = 24$ arrangements (vs $5!=120$ in a line).

(Exam scope: Section 6.2 examinable through Example 6.13, plus cyclic permutations; proof of Theorem 6.4 and “Fibonacci numbers revisited” optional/non-examined.)

3. Combinations

An unordered selection: {Costa, Shea, Weiss} is the same committee regardless of listing order.

Definition. $C(n,r)$ = number of unordered r-element selections from n distinct elements.

Deriving the formula: each r-combination gives $r!$ different r-permutations (arrange its elements every way). So total r-permutations = $r!\cdot C(n,r) = P(n,r) = \dfrac{n!}{(n-r)!}$. Solving:

\[C(n,r) = \frac{n!}{r!(n-r)!} = \frac{n(n-1)\cdots(n-r+1)}{r!}\]

Special values: $C(n,0) = C(n,n) = 1$.

Worked example. Subcommittees of 3 from 25 members: $C(25,3) = 25\cdot24\cdot23/3! = 13800/6 = 2300$.

Worked example (Oct 2024). Groups from 7 marbles, each group ≥ 3 marbles: sizes 3,4,5,6,7 are mutually exclusive cases (addition principle):

\[C(7,3)+C(7,4)+C(7,5)+C(7,6)+C(7,7) = 35+35+21+7+1 = 99\]

⚠️ The most common exam mistake: using $P(n,r)$ where $C(n,r)$ was needed, or vice versa. Always ask: does order matter here?

(Exam scope: Section 6.4 examinable for the formula and direct applications; proof of Theorem 6.10, Example 6.22, Theorem 6.12, Example 6.26 are optional/non-examined.)

4. Discrete Probability

Sample space $S$ = set of all possible outcomes of an experiment (finite, nonempty). Event $E$ $\subseteq S$. Outcome in E: favorable; not in E: unfavorable. $E=\emptyset$: impossible event. $|E|=1$: simple event. Complement: $E’ = S - E$.

Example. Toss 3 coins: $|S| = 2\cdot2\cdot2 = 8$, $S = \{HHH,HHT,HTH,HTT,THH,THT,TTH,TTT\}$. A = “exactly 2 heads” = $\{HHT,HTH,THH\}$. B = “at least 2 heads” = $\{HHT,HTH,THH,HHH\}$. C = “4 heads” = $\emptyset$.

Probability of an event (equally likely outcomes):

\[p(E) = \frac{|E|}{|S|} = \frac{\text{number of favorable outcomes}}{\text{total possible outcomes}}\]

Worked example (Oct 2024). Card drawn at random, P(spade): $|S|=52$, spades=13 → $p = 13/52 = 1/4$.

Worked example (Oct 2024). P(at least one head, 3 coins): only TTT has none, $|E|=8-1=7$ → $p = 7/8$.

Unequal outcomes: if outcomes $a_1,\ldots,a_n$ aren’t equally likely, with probabilities summing to 1, then for $E=\{a_{i_1},\ldots,a_{i_k}\}$: $p(E) = \sum p(a_i)$.

Worked example. A loaded die: $p(\text{prime}) = 2\cdot p(\text{nonprime})$. 3 outcomes each. $3p(\text{prime})+3p(\text{nonprime})=1$ → $6p(\text{nonprime})+3p(\text{nonprime})=1$ → $p(\text{nonprime})=1/9$, $p(\text{prime})=2/9$. $P(\text{odd}) = p(1)+p(3)+p(5) = 1/9+2/9+2/9 = 5/9$ (1 nonprime, 3&5 prime).

4.1 Mutually Exclusive Events

A, B mutually exclusive if $A\cap B=\emptyset$ (can’t occur together). Example: drawing a red queen and a black king.

Theorem 6.20 — Inclusion-exclusion (probability, proof not examined):

\[p(A\cup B) = p(A) + p(B) - p(A\cap B)\]

If mutually exclusive ($A\cap B=\emptyset$): $p(A\cup B) = p(A) + p(B)$.

Worked example. $P(\text{red queen or black king}) = 2/52 + 2/52 = 4/52 = 1/13$.

*(Exam scope: Section 6.8 examinable through Example 6.49, plus mutually exclusive events and Theorem 6.20’s statement, not its proof. p(E)= E / S — where E is often itself a permutation/combination count — is the most-tested idea in this chapter.)*

5. Optional / Not Examined — Module V Extensions

  • Conditional probability: $p(A\mid B) = p(A\cap B) / p(B)$, $p(B)\neq 0$ — B becomes the new sample space.
  • Multiplication theorem: $p(A\cap B) = p(B)\cdot p(A\mid B) = p(A)\cdot p(B\mid A)$.
  • Independent vs dependent events: independent if $p(A\mid B) = p(A)$, i.e. $p(A\cap B) = p(A)p(B)$; otherwise dependent. E.g. two cards with replacement: independent, $p(\text{both aces}) = (4/52)(4/52)$. Without replacement: dependent, $p(\text{both aces}) = (4/52)(3/51)$.
  • Probability distributions: a random variable $X$ assigns a number to each outcome (e.g. $X$ = heads in 3 tosses). Distribution lists each value with its probability — for 3 fair coins, $p(X=0)=1/8$, $p(X=1)=3/8$, $p(X=2)=3/8$, $p(X=3)=1/8$ (from $C(3,k)/2^3$). Expected value: $E[X] = \sum x\cdot p(X=x)$.
  • Correlation and regression: for paired data $(x_i,y_i)$, correlation coefficient $r$ ($-1$ to $1$) measures linear association strength. Linear regression fits $\hat{y} = a+bx$ minimizing total squared vertical distance.

Chapter Summary

  • Addition principle (mutually exclusive: add), inclusion-exclusion for tasks ($m+n-k$), multiplication principle (sequential: multiply).
  • Permutations: $P(n,r) = n!/(n-r)!$ (order matters); cyclic permutations: $(n-1)!$.
  • Combinations: $C(n,r) = n!/(r!(n-r)!)$ (order doesn’t matter).
  • Probability: $p(E)=|E|/|S|$ (equally likely) or $\sum p(a_i)$ (otherwise); mutually exclusive events: $p(A\cup B)=p(A)+p(B)$; general: $p(A\cup B)=p(A)+p(B)-p(A\cap B)$.
  • Module V: conditional probability, independence, distributions, correlation/regression.

Practice Problems

  1. A restaurant offers 4 starters, 6 mains, 3 desserts. How many 3-course meals (multiplication principle)?
  2. Choose one elective from 8 Maths or 5 CS electives (no overlap). How many ways?
  3. Compute $P(7,3)$ and $C(7,3)$. Explain in words what each counts.
  4. Seat 6 people (i) in a row, (ii) around a circular table.
  5. Distinct arrangements of the letters of “LOGIC”.
  6. Committee of 4 from 6 men and 5 women, exactly 2 men and 2 women — how many ways?
  7. Roll a fair die. Find $P(\text{number} > 4)$.
  8. Roll two dice. Find $P(\text{sum} = 7)$. (Hint: $|S|=36$, list favorable outcomes.)
  9. Are “sum is 7” and “first die shows 6” mutually exclusive (two dice)? Compute $p(\text{sum is 7 or first die shows 6})$.
  10. Design your own mutually-exclusive-events probability problem modeled on the red-queen-or-black-king example, and solve it.
  11. (Module V) Two cards drawn without replacement. Find $P(\text{both hearts})$ using the multiplication theorem.
  12. Number of 5-card poker hands with exactly 3 aces. (Hint: choose 3 aces, then 2 cards from non-aces — two combinations, multiplied.)
← Previous Module Course Home Next Module →