T.2 · 离散数学、概率与数值方法
GRE Subject Test · GRE 数学 知识点 6 2:58 英语旁白 · 英中内嵌字幕
章节
文本转录
This unit counts, uses recurrences, graphs and logic; calculates probabilities and distribution properties; and applies numerical approximation with an error argument.
本单元涉及计数、递推关系、图和逻辑；计算概率和分布的性质；并应用数值近似及其误差分析。
Choose the counting model first.
先选计数模型。
Ordered selections of r distinct objects use n times n minus 1 and so on; unordered subsets use n choose r.
从 n 个中取 r 个不同对象的有序选择用 n(n − 1)…；无序子集用组合数 C(n, r)。
A complete graph has one edge per pair.
完全图每对顶点一条边。
And n lines in general position cut the plane into 1 plus n times n plus 1 over 2 regions; parallels break that count.
n 条处于一般位置的直线把平面分成 1 + n(n + 1)/2 个区域；有平行线时这个计数就不成立。
Use complements for at least one, and condition on what is actually left after a draw.
“至少一个”用补事件，并按抽取后实际剩下的情况来条件化。
For r independent uniform outcomes from n values, all distinct has probability n falling r over n to the r.
从 n 个值中独立均匀取 r 次，全不相同的概率是 n 的 r 次下降阶乘除以 nʳ。
A binomial count has mean N p and variance N p times 1 minus p.
二项分布的均值是 Np，方差是 Np(1 − p)。
A recurrence links later values to earlier ones and needs enough initial data.
递推关系把后面的项与前面的项联系起来，并需要足够的初始条件。
a n equals 2 a n minus 1, with a 0 equal to 3, gives 3 times 2 to the n.
aₙ = 2aₙ₋₁，a₀ = 3，得到 3·2ⁿ。
A closed formula must satisfy both the rule and the start; fitting a few terms proves nothing.
通项公式必须同时满足递推和初值；只拟合几项什么也证明不了。
For f of x equals x squared minus 2 from x nought equals 1: the tangent at 1 meets the axis and gives 1.5.
对 f(x) = x² − 2，从 x₀ = 1 出发：1 处的切线与 x 轴相交，得 1.5。
The next step gives 1.4167, close to the approximate root 2.
下一步得 1.4167，接近 √2。
But starting at zero fails, because the derivative there is zero.
但从零出发会失败，因为那里导数为零。
Events with positive probabilities cannot be both independent and mutually exclusive.
概率都为正的事件不可能既独立又互斥。
There are 5 to the 4 equally likely ordered strings, and 120 with no repeat.
等可能的有序串共有 5⁴ 个，其中无重复的有 120 个。
So the probability of a repeat is 1 minus 120 over 625, which is 101 over 125.
所以出现重复的概率是 1 − 120/625 = 101/125。
Unordered subsets number 5, each in 24 orders; dividing by 4 factorial belongs to that count only.
无序子集有 5 个，每个有 24 种顺序；除以 4! 只适用于这个计数。
x cubed minus 2 is continuous with a sign change on 1, 2.
x³ − 2 在 上连续且变号。
Each step halves its width: the midpoint 1.5 is positive, retaining 1, 1.5; then 1.25 is negative, retaining 1.25, 1.5.
每一步区间宽度减半：中点 1.5 处为正，保留 ；然后 1.25 处为负，保留 。
After ten halvings the midpoint error is at most 1 over 2048.
十次减半后，中点误差至多 1/2048。
For 1 over x there is no root, only a singularity.
对 1/x，没有根，只有奇点。
Check yourself.
自我检测。
A complete graph has n times n minus 1 over 2 edges.
完全图有 n(n − 1)/2 条边。
Binomial variance is N p times 1 minus p.
二项分布方差是 Np(1 − p)。
Newton needs a nonzero derivative.
牛顿法需要导数非零。
Bisection needs continuity and a sign change.
二分法需要连续和变号。
And events with positive probabilities cannot be both independent and exclusive.
概率为正的事件不可能既独立又互斥。