Toán rời rạc, xác suất và phương pháp số
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| recurrence/rɪˈkʌrəns/ | Quan hệ truy hồi |
| complement/ˈkɒmplɪmənt/ | The event that the given event does not happen. |
| bisection/baɪˈsekʃn/ | A root-finding method that halves a sign-change interval at each step. |
Pick the model before counting
- "How many ways can 3 of 10 students be chosen?" depends on whether the 3 roles differ. Committee: $\binom{10}{3} = 120$. President, secretary, treasurer: $10 \cdot 9 \cdot 8 = 720$.
- GRE discrete mathematics tests counting models, probability, recurrences 递推关系, graphs and numerical methods.
Counting models
- Ordered, distinct: $n(n-1)\cdots(n-r+1)$. Unordered: $\binom{n}{r}$. Complete graph $K_n$: $\binom{n}{2}$ edges. A tree on $n$ vertices has $n - 1$ edges.
- $n$ lines in general position divide the plane into $1 + \dfrac{n(n+1)}{2}$ regions; the $k$th line adds $k$ regions. Parallel lines break the formula.
Ordered or unordered?
Choose the counting model from the situation.
How many edges does the complete graph $K_7$ have?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Each edge joins a pair of distinct vertices, and K₇ joins every pair: C(7, 2) = 7 · 6 / 2 = 21.
Into how many regions do 5 lines in general position divide the plane?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
The n-th line in general position crosses the earlier n − 1 lines and so adds n regions. Starting from 1 region: 1 + (1 + 2 + 3 + 4 + 5) = 1 + 15 = 16.
Probability
- "At least one" → use the complement 补事件. $r$ independent uniform picks from $n$ values are all distinct with probability $\dfrac{n(n-1)\cdots(n-r+1)}{n^r}$.
- Binomial($N$, $p$): mean $Np$, variance $Np(1-p)$. Events with positive probability cannot be both independent and mutually exclusive.
A binomial variable has $N = 10$, $p = 0.3$. Its variance is
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
$10 \times 0.3 \times 0.7$.
Two mutually exclusive events with positive probabilities cannot be independent.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
True. Exclusive means $P(A \cap B) = 0$, but independence needs $P(A \cap B) = P(A)P(B) > 0$.
Recurrences
- A recurrence needs enough initial values. $a_n = 2a_{n-1}$, $a_0 = 3$ gives $a_n = 3 \cdot 2^n$.
- Prove a guessed closed form by checking the recurrence and the initial condition, not by matching a few terms.
Numerical methods
- Newton: $x_{\text{new}} = x - f(x)/f'(x)$, needing $f'(x) \neq 0$. Bisection 二分法 halves a sign-change bracket of a continuous function each step.
$f(x) = x^2 - 2$, $x_0 = 1$: $x_1 = 1 - \tfrac{-1}{2} = 1.5$, $x_2 = 1.5 - \tfrac{0.25}{3} \approx 1.4167$, close to $\sqrt 2 \approx 1.4142$. Starting at $x_0 = 0$ fails: $f'(0) = 0$.
Apply one Newton step to $f(x) = x^2 - 3$ from $x_0 = 2$.
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
x₁ = x₀ − f(x₀)/f′(x₀) = 2 − (4 − 3)/(2 · 2) = 2 − 1/4 = 1.75, already close to √3 ≈ 1.732.
Recap
- Decide ordered or unordered first; check graph and geometry assumptions.
- Complement for "at least one"; binomial variance $Np(1-p)$.
- Recurrence proofs need initial conditions; Newton needs a nonzero derivative.
- complement: The event that the given event does not happen.
- bisection: A root-finding method that halves a sign-change interval at each step.