Discrete mathematics, probability and numerical methods
| English | 中文 | Pinyin |
|---|---|---|
| recurrence/rɪˈkʌrəns/ | 递推关系 | dì tuī guān xì |
| mutually exclusive/ˈmjuːtʃuːəli eksˈkluːsɪv/ | 互斥的 | hù chì de |
A decision before an answer
- A calculator returns a root, but the starting value and derivative determine whether Newton’s method can approach it.
- Your goal: Use counting, recurrences, graph reasoning and logic.
Read the relationship
- Choose the counting model first: ordered selections of r distinct objects use n(n−1)⋯(n−r+1), while unordered subsets use C(n,r). A complete simple graph on n vertices has one edge per unordered vertex pair, giving n(n−1)/2 edges; loops and multiple edges would change the model. For n lines in general position in a plane, the kth line crosses the prior k−1 lines in distinct points and adds k regions. The total is 1+n(n+1)/2; parallels or triple concurrence invalidate that count.
- Calculate probabilities and distribution properties.
How many unordered pairs can be chosen from 5 objects?
5 choose 2 =5×4/2=10.
Use the defining rule
- Use complements to count at least one occurrence, and condition on the actual remaining population after a draw without replacement. For r iid outcomes chosen from n equally likely values, the probability that all are distinct is n(n−1)⋯(n−r+1)/n^r when r≤n. Its complement counts repeated outcomes. For a binomial count with N independent trials and fixed success probability p, mean is Np and variance Np(1−p). Identical probabilities alone do not establish independence.
- Apply numerical approximation and assess error.
A tree has 8 vertices. Its edge count is:
A finite tree has n−1 edges.
Check the conditions
- A recurrence describes later values from earlier ones and needs enough initial data to determine a sequence. Separate the index from the value: a_n=2a_(n−1) with a_0=3 gives a_n=3·2^n. Graph and algorithm arguments often establish a recurrence by identifying what a new vertex or step adds. A closed formula should satisfy both the recurrence and its initial conditions; fitting a few observed terms does not prove it for every index.
- Apply numerical approximation and assess error.
For f(x)=x²−2 and x₀=1, Newton’s step gives 1−(1−2)/2=1.5. The next value is 1.5−0.25/3=1.4167. These approximate sqrt(2), but f′(0)=0 makes zero an invalid starting point.
For a fair die, P(even) = ____ (decimal).
Three of six equally likely outcomes are even.
Apply the task format
- Numerical approximation needs an error argument. Bisection preserves a sign-changing bracket for a continuous function and halves its width at each step; a zero may be absent if continuity fails. Newton’s update is x_new=x−f(x)/f′(x), requiring a nonzero derivative at the current point; convergence is not automatic from every starting value. An approximation’s residual and its error in x are different. State the method’s assumptions and a stopping criterion, rather than treating extra displayed decimals as accuracy.
- Apply numerical approximation and assess error.
Events with positive probabilities cannot be both independent and mutually exclusive.
Which answer fits this case?
Use counting, recurrences, graph reasoning and logic
Newton’s method is guaranteed to converge from every starting value.
A zero derivative or unsuitable starting value can prevent convergence.
Keep the distinctions
- recurrence 递推关系 — A rule linking a sequence term to earlier terms.
- mutually exclusive 互斥的 — Events that cannot happen together.
- Use counting, recurrences, graph reasoning and logic.
- Calculate probabilities and distribution properties.
- Apply numerical approximation and assess error.
Match each term with its precise meaning in this lesson.
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
The order follows the stated process; check each stage before the next.