第 01 章 组合分析

本章对应 Ross《A First Course in Probability》第 9 版第 1 章。它是全书的计数工具箱：后面凡是"等可能模型下的概率 = 有利结果数 ÷ 全部结果数"，都要靠这里的方法去数。与量化交易的直接联系不多，但二项分布、二叉树定价、多重检验规模估计都从这里出发。

学习目标

1. 熟练使用（广义）基本计数原理，把复杂计数拆成若干步相乘。
2. 区分排列、含相同元素的排列、组合、多项式系数，并理解它们共同的思路："先当作可区分、有顺序来数，再除以重复计数的倍数"。
3. 掌握 Pascal 恒等式、二项式定理、多项式定理，并会用"对某个特殊元素分情况"或"双重计数"的组合论证来证明恒等式。
4. 会用隔板法（stars and bars）求 \(x_1+\cdots+x_r=n\) 的正整数解与非负整数解个数，会用变量平移处理下界约束。
5. 能把这些工具用在量化研究的规模估计上：因子组合数、参数网格、离散化资产配置方案数、二叉树路径数。

读前导读

这一章在解决什么问题。 古典概率的公式是"有利结果数 ÷ 全部结果数"，难点全在"数"。这一章就是一套数数的方法。你在 CFA 一级定量方法里已经见过 \(n!\)、\({}_nP_r\)、\({}_nC_r\) 这三个公式，也会用计算器按出来。本章比 CFA 多走两步：第一，讲清楚这些公式为什么成立，核心只有一个思路——"先当作全都可区分、有顺序来数，再除以重复计数的倍数"；第二，教你用"组合论证"证明恒等式，也就是把等式两边解释成"用两种方法数同一堆东西"。后者是读后面各章推导的基本功。

和金融的联系很直接。CFA 的单步二叉树你已经会；多步二叉树里，\(n\) 步中恰好涨 \(k\) 次的路径有 \(\binom nk\) 条，这就是二项分布和 CRR 定价的骨架。另一个用途是估计"试了多少次"：回测组合数一旦上百万，好看的结果有多少是运气，就成了多重检验问题（第 02 章、第 03 册）。

需要先想起来的数学。

• 求和记号 \(\sum\)。 \(\sum_{k=0}^n a_k\) 就是 \(a_0+a_1+\cdots+a_n\)，\(k\) 是"计数器"，换成别的字母意思不变。例：\(\sum_{k=0}^{2}\binom2k=1+2+1=4\)。本章常做"换下标"：令 \(i=k+1\)，求和范围也要跟着平移（\(k\) 从 0 到 \(n-1\)，\(i\) 就从 1 到 \(n\)）。详见 第 00 册第 07 章 概率中的分析工具。
• 数学归纳法。 要证一个对所有 \(n\) 成立的命题：先验证 \(n=1\)，再证明"若对 \(n-1\) 成立，则对 \(n\) 也成立"。像多米诺骨牌，推倒第一块、且每块都能推倒下一块，所有骨牌都会倒。二项式定理的第一个证明就是这个结构。
• 一一对应（双射）。 如果两堆东西能一对一配对、不重不漏，那它们个数相同。"子集 ↔ 0/1 串"、"淘汰赛结果 ↔ 排名"都是这种论证。它让我们把难数的东西换成好数的东西。以上两项见 第 00 册第 08 章 读懂数学证明与符号。
• 几何级数与 \(2^n\)。 \(\sum_k\binom nk=2^n\) 以及后面的年金式求和，见 第 00 册第 04 章 级数与收敛。

怎么读这一章。 1.2–1.4 是核心，务必读懂"先区分再除以重复"的思路和 Pascal 恒等式的组合证明。二项式定理的归纳证明第一次可以只看结构，组合证明更重要。1.5 的多项式系数要会用，例 5d 淘汰赛可以先跳过。1.6 隔板法原书标为选读，但"量化实战"里的资金分配问题要用到它，建议至少读懂命题 6.1、6.2 和例 6b。最后把"量化实战"的三点读一遍，它们说明这些计数在研究中的实际位置。

1.1 为什么要学计数

先看原书的引例。\(n\) 根外观相同的天线排成一列，只要没有两根相邻的天线同时失效，系统就"可用"。如果恰好有 \(m\) 根失效，系统可用的概率是多少？

以 \(n=4,m=2\) 为例，把正常记为 1、失效记为 0，所有可能配置共 6 种：

0110、0101、1010、0011、1001、1100

其中前 3 种没有相邻的 0，所以概率为 \(3/6=1/2\)。\(n\)、\(m\) 一大，逐个列举就不现实了。我们需要一套有效的计数方法，这套数学理论叫组合分析（combinatorial analysis）。本章最后会回到这个问题，给出一般答案 \(\binom{n-m+1}{m}\big/\binom{n}{m}\)。

1.2 基本计数原理

基本计数原理（basic principle of counting）：做两个试验，试验 1 有 \(m\) 种可能结果；对试验 1 的每一种结果，试验 2 都有 \(n\) 种可能结果。那么两个试验合起来共有 \(mn\) 种结果。

证明很直接：把所有结果写成数对 \((i,j)\)，\(i\) 是试验 1 的第 \(i\) 种结果、\(j\) 是试验 2 的第 \(j\) 种结果，它们排成一个 \(m\) 行 \(n\) 列的矩阵，共 \(mn\) 个元素。

广义基本计数原理：\(r\) 个试验依次进行，第一个有 \(n_1\) 种结果；对前面每一种结果组合，第 \(k\) 个试验都有 \(n_k\) 种结果，那么共有 \(n_1n_2\cdots n_r\) 种结果。

需要强调的是：相乘的前提是"对每一种前序结果，后续的结果数相同"，并不要求后续的结果集合相同。例如不允许重复的车牌，第二位能选哪些字母取决于第一位，但能选的个数总是 25。

白话解释：乘法原理失效的典型情形是"后一步的选项个数取决于前一步选了什么"。例如先选一个行业、再从该行业里选一只股票，银行有 40 只、半导体有 120 只，就不能用"行业数 × 某个固定数"，而要分行业相加：\(40+120+\cdots\)。判断能否相乘，只问一句：无论前面怎么选，这一步的选项个数是否总是一样。

原书例题（保留数字）：

• 例 2a：10 位母亲各带 3 个孩子，评选"年度母子"一对，共 \(10\times3=30\) 种选法。
• 例 2b：委员会有 3 名大一、4 名大二、5 名大三、2 名大四学生，每个年级选 1 人组成 4 人小组：\(3\cdot4\cdot5\cdot2=120\)。
• 例 2c：7 位车牌，前 3 位字母、后 4 位数字：\(26^3\cdot10^4=175{,}760{,}000\)。
• 例 2d：定义在 \(n\) 个点上、取值为 0 或 1 的函数个数为 \(2^n\)。
• 例 2e：例 2c 中不允许字母或数字重复：\(26\cdot25\cdot24\cdot10\cdot9\cdot8\cdot7=78{,}624{,}000\)。

1.3 排列

把 \(a,b,c\) 三个字母排成一列，有 \(abc,acb,bac,bca,cab,cba\) 共 6 种，每一种叫一个排列（permutation）。由基本计数原理，第一个位置有 \(n\) 种选择，第二个有 \(n-1\) 种……所以 \(n\) 个不同对象的排列数为

读作"\(n\) 的阶乘（factorial）"，并约定 \(0!=1\)。

• 例 3a：9 人棒球队的击球顺序有 \(9!=362{,}880\) 种。
• 例 3b：6 男 4 女按考试成绩排名（无并列）。(a) 全部排名有 \(10!=3{,}628{,}800\) 种；(b) 若男生、女生各自内部排名，则有 \(6!\,4!=720\cdot24=17{,}280\) 种。
• 例 3c：书架上放 10 本书：4 本数学、3 本化学、2 本历史、1 本语言，同一科目的书必须放在一起。先决定科目的顺序（\(4!\) 种），再在各科目内部排列（\(4!\,3!\,2!\,1!\) 种），答案为 \(4!\,4!\,3!\,2!\,1!=6912\)。这就是常说的"捆绑法"。

含相同元素的排列。 例 3d：单词 PEPPER 的字母能排出多少种不同的字母串？先给 3 个 P、2 个 E 加上下标，把它们当成可区分的：\(P_1E_1P_2P_3E_2R\)，共有 \(6!\) 种排列。去掉下标后，每一个字母串恰好对应 \(3!\,2!\) 个带下标的排列（3 个 P 之间互换、2 个 E 之间互换），所以答案是 \(6!/(3!\,2!)=60\)。

一般地，\(n\) 个对象中有 \(n_1\) 个彼此相同、\(n_2\) 个彼此相同、……、\(n_r\) 个彼此相同，则不同排列数为

• 例 3e：10 名棋手（4 俄、3 美、2 英、1 巴西），比赛结果只记国籍，可能的名次表有 \(10!/(4!\,3!\,2!\,1!)=12{,}600\) 种。
• 例 3f：4 面白旗、3 面红旗、2 面蓝旗挂成一列，同色旗相同，可组成 \(9!/(4!\,3!\,2!)=1260\) 种不同信号。

方法要点："先标号区分，再除以重复计数的倍数"是组合计数中最常用的技巧，下面的组合数、多项式系数都是它的直接推论。

1.4 组合与二项式定理

组合数

从 A、B、C、D、E 五个对象中选 3 个组成一组，不计顺序，有多少组？如果计顺序，有 \(5\cdot4\cdot3=60\) 种；每个三人组（例如 \(\{A,B,C\}\)）在其中被计了 \(3!=6\) 次，所以组数为 \(60/6=10\)。

一般地，从 \(n\) 个不同对象中取 \(r\) 个、不计顺序，组数为

读作"\(n\) 选 \(r\)（n choose r）"，它也就是 \(n\) 元集合中 \(r\) 元子集的个数。约定 \(\binom n0=\binom nn=1\)，并且当 \(r<0\) 或 \(r>n\) 时 \(\binom nr=0\)。这个约定让后面很多公式（例如超几何分布）不用分情况书写。

白话解释：\(\binom nr\) 就是 CFA 计算器上的 \({}_nC_r\)，\({}_nP_r=n!/(n-r)!\) 是"计顺序"的版本，两者差一个 \(r!\)。记两条就够：其一，"选 \(r\) 个"等于"留下 \(n-r\) 个"，所以 \(\binom nr=\binom n{n-r}\)；其二，左边的分式写法 \(n(n-1)\cdots(n-r+1)/r!\) 分子恰好 \(r\) 项，手算时比阶乘写法省事，例如 \(\binom{50}{3}=\frac{50\cdot49\cdot48}{6}=19600\)。

• 例 4a：20 人中选 3 人委员会：\(\binom{20}{3}=1140\)。
• 例 4b：5 女 7 男中选 2 女 3 男：\(\binom52\binom73=10\cdot35=350\)。若有两名男子不肯同时入选：同时含这两人的 3 男组有 \(\binom22\binom51=5\) 个，可行男组 \(35-5=30\) 个，答案 \(30\cdot10=300\)。
• 例 4c（回到天线问题）：\(n\) 根天线中 \(m\) 根失效，求没有两根失效天线相邻的排列数。先把 \(n-m\) 根正常天线排好，它们之间以及两端共形成 \(n-m+1\) 个空位；每个空位至多放一根失效天线，于是只需从这些空位中选 \(m\) 个：\(\binom{n-m+1}{m}\)。这就是"插空法"。所以引例的答案是 \(\binom{n-m+1}{m}/\binom nm\)；\(n=4,m=2\) 时为 \(\binom32/\binom42=3/6\)，与列举一致。

Pascal 恒等式

组合证明：固定某个特定对象"1"。含它的 \(r\) 元子集相当于从其余 \(n-1\) 个中再选 \(r-1\) 个，有 \(\binom{n-1}{r-1}\) 个；不含它的从其余 \(n-1\) 个中选 \(r\) 个，有 \(\binom{n-1}{r}\) 个。两类互不重叠且覆盖全部，相加即得。

"固定一个特殊元素、按它在不在分两类"的论证，在概率论里会以"对第一步取条件"的形式反复出现（第 03 章）。

金融直觉：Pascal 恒等式就是二叉树的"回溯"。到达第 \(n\) 步、累计上涨 \(r\) 次的节点，只能从两个节点走来：第 \(n-1\) 步上涨 \(r-1\) 次的节点（这一步涨），或上涨 \(r\) 次的节点（这一步跌）。所以到达它的路径数等于两者之和。Pascal 三角逐行相加，与二叉树从左往右逐步展开是同一张图。

二项式定理

\(\binom nr\) 又叫二项式系数（binomial coefficient），来源于二项式定理（binomial theorem）：

原书给了两个证明。

归纳证明。 \(n=1\) 时显然。设对 \(n-1\) 成立，则

推导拆解：

1. 第一个等号：把 \((x+y)^n\) 拆成 \((x+y)\cdot(x+y)^{n-1}\)，对后一个因子用归纳假设。
2. 第二个等号：把 \((x+y)\) 分配进去，乘 \(x\) 的部分让 \(x\) 的指数加 1，乘 \(y\) 的部分让 \(y\) 的指数加 1，得到两个和式。
3. 换下标：第一个和式令 \(i=k+1\)，\(k\) 从 \(0\) 到 \(n-1\) 变成 \(i\) 从 \(1\) 到 \(n\)，通项变成 \(\binom{n-1}{i-1}x^iy^{n-i}\)；第二个和式 \(i=k\) 从 \(0\) 到 \(n-1\)，通项 \(\binom{n-1}{i}x^iy^{n-i}\)。两式通项里 \(x,y\) 的指数现在一样了，这正是换下标的目的。
4. 合并：\(i=n\) 只出现在第一个和式（系数 \(\binom{n-1}{n-1}=1\)，即 \(x^n\)），\(i=0\) 只出现在第二个（即 \(y^n\)），\(1\le i\le n-1\) 两边都有，系数相加。
5. 方括号里用 Pascal 恒等式化为 \(\binom ni\)；又 \(\binom nn=\binom n0=1\)，于是首尾两项也并入 \(\sum_{i=0}^n\binom nix^iy^{n-i}\)。

组合证明。 考虑 \((x_1+y_1)(x_2+y_2)\cdots(x_n+y_n)\)。展开后共 \(2^n\) 项，每一项是从每个括号里各取 \(x_i\) 或 \(y_i\) 相乘。含 \(k\) 个 \(x\) 因子的项，对应于从 \(n\) 个下标中选出取 \(x\) 的那 \(k\) 个，共 \(\binom nk\) 项。令所有 \(x_i=x,\ y_i=y\) 就得到 (4.2)。

• 例 4d：\((x+y)^3=y^3+3xy^2+3x^2y+x^3\)。
• 例 4e：\(n\) 元集合的子集个数为 \(\sum_{k=0}^n\binom nk=(1+1)^n=2^n\)。另一种看法：给每个元素赋值 0 或 1，赋 1 的元素构成一个子集，二者一一对应。非空子集有 \(2^n-1\) 个。

1.5 多项式系数

问题：把 \(n\) 个不同物品分成 \(r\) 个有区别的组，各组大小分别是 \(n_1,\dots,n_r\)（\(\sum n_i=n\)），有多少种分法？逐组选取：

中间的阶乘逐项相消。另一种看法：取 \(n_1\) 个 1、\(n_2\) 个 2、……、\(n_r\) 个 \(r\) 组成的序列，它的任一排列 \(i_1,\dots,i_n\) 表示"把物品 \(j\) 分到第 \(i_j\) 组"。例如 \(n=8\)、\((n_1,n_2,n_3)=(4,3,1)\)，排列 1,1,2,3,2,1,2,1 表示物品 1、2、6、8 入第 1 组，3、5、7 入第 2 组，4 入第 3 组。分法与"含相同元素的排列"一一对应，所以个数相同。

定义 若 \(n_1+\cdots+n_r=n\)，记多项式系数（multinomial coefficient）

• 例 5a：10 名警察分为巡逻 5 人、站内值班 2 人、后备 3 人：\(\frac{10!}{5!\,2!\,3!}=2520\)。
• 例 5b：10 个孩子分成 A 队、B 队各 5 人（两队有名称，有区别）：\(\frac{10!}{5!\,5!}=252\)。
• 例 5c：10 个孩子自行分成两队各 5 人打篮球（两队无名称，无区别）：\(\frac{10!/(5!\,5!)}{2!}=126\)。

常见误区：组没有标签时，要再除以"大小相同的组之间的排列数"。例 5b 和例 5c 的差别就在这里。

白话解释：多项式系数是二项式系数的推广：二项式是"分两组"（入选/落选，或涨/跌），多项式是"分 \(r\) 组"。\(\binom{n}{k}=\binom{n}{k,\,n-k}\)。在金融里的对应物是"三叉树"：每步涨、平、跌三种可能，\(n\) 步中分别出现 \(n_1,n_2,n_3\) 次的路径数就是 \(\binom{n}{n_1,n_2,n_3}\)。判断要不要再除以组间排列，只问：把两组的名字互换，算不算同一种分法？例 5b 中"A 队是甲组、B 队是乙组"和反过来是两种，例 5c 中是同一种。

多项式定理（multinomial theorem）（证明留作原书理论练习 19）：

求和遍历所有和为 \(n\) 的非负整数向量。例 5e：\((x_1+x_2+x_3)^2=x_1^2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3\)，系数分别是 \(\binom{2}{2,0,0}=1\)、\(\binom{2}{1,1,0}=2\) 等。

例 5d（淘汰赛） \(n=2^m\) 名选手进行单败淘汰赛，以 8 人为例。

(a) 第一轮可能的结果数。把 8 人分成有序的 4 对有 \(\binom{8}{2,2,2,2}=8!/2^4\) 种，对与对之间无顺序，再除以 \(4!\)；每对有 2 种胜者，所以第一轮结果数为 \(\frac{8!\,2^4}{2^4\,4!}=\frac{8!}{4!}\)。另一种算法：先选 4 名胜者 \(\binom84\)，再把 4 名胜者与 4 名负者配对 \(4!\)，同样得 \(4!\binom84=8!/4!\)。

(b) 整个比赛的结果数。第二轮 \(4!/2!\)，第三轮 \(2!/1!\)，总数 \(\frac{8!}{4!}\cdot\frac{4!}{2!}\cdot\frac{2!}{1!}=8!\)。一般地，\(n=2^m\) 人淘汰赛有 \(n!\) 种完整结果。直接论证是把比赛结果对应成 \(1,\dots,n\) 的一个排名：冠军排 1、决赛负者排 2；半决赛输给 1 号的排 3、输给 2 号的排 4；再前一轮输给 1、2、3、4 号的分别排 5、6、7、8……即在有 \(2^k\) 场比赛的那一轮中被淘汰的选手，排名等于 \(2^k\) 加上击败他的选手的排名。这样比赛结果与排列一一对应。

1.6 方程的整数解个数（原书选读）

引例：湖中有 4 种鱼，共钓上 10 条，只记录各种鱼的条数，可能的结果数等于满足 \(x_1+x_2+x_3+x_4=10\) 的非负整数向量个数。一般问题是

正整数解（隔板法，stars and bars）。 把 \(n\) 个 0 排成一行，相邻 0 之间有 \(n-1\) 个空隙；从中选 \(r-1\) 个放隔板，把 0 分成 \(r\) 段，第 \(i\) 段的 0 的个数就是 \(x_i\)，且每段至少一个。例如 \(n=8,r=3\)，选法 0 | 0 0 0 0 | 0 0 0 对应 \((1,4,3)\)。

命题 6.1 满足 (6.1) 且所有 \(x_i>0\) 的整数向量共 \(\binom{n-1}{r-1}\) 个。

命题 6.2 满足 (6.1) 且所有 \(x_i\ge0\) 的整数向量共 \(\binom{n+r-1}{r-1}\) 个。

证明：令 \(y_i=x_i+1\)，问题化为 \(y_1+\cdots+y_r=n+r\) 的正整数解，由命题 6.1 得 \(\binom{n+r-1}{r-1}\)。

推导拆解：命题 6.1 的计数在于"隔板放在哪"：\(n\) 个 0 之间有 \(n-1\) 个缝，每个缝至多放一块板（放两块就会出现空段，违反 \(x_i>0\)），要分成 \(r\) 段需要 \(r-1\) 块板，所以是 \(\binom{n-1}{r-1}\)。命题 6.2 允许 \(x_i=0\)，直接放板会出现两块板挨在一起，不好数，于是做平移：每个 \(x_i\) 先"借"1 个，\(y_i=x_i+1\ge1\)，总数变成 \(n+r\)。\(x\) 的非负解与 \(y\) 的正解一一对应（加 1、减 1 互逆），所以个数相同，代入命题 6.1，把 \(n\) 换成 \(n+r\) 即得 \(\binom{n+r-1}{r-1}\)。 另一种看法：把 \(n\) 个 0 和 \(r-1\) 块板一起排成一行，共 \(n+r-1\) 个位置，选出哪 \(r-1\) 个位置放板，结果相同。

于是钓鱼问题的答案为 \(\binom{13}{3}=286\)。

• 例 6a：\(x_1+x_2=3\) 的非负整数解有 \(\binom41=4\) 个：\((0,3),(1,2),(2,1),(3,0)\)。
• 例 6b（投资分配）：有 2 万美元，以 1000 美元为单位投资于 4 个项目。若必须全部投出，即 \(x_1+\cdots+x_4=20\) 的非负解，共 \(\binom{23}{3}=1771\) 种策略；若不必全部投出，引入保留额 \(x_5\)，化为 \(x_1+\cdots+x_5=20\)，共 \(\binom{24}{4}=10{,}626\) 种。
• 例 6c：\((x_1+\cdots+x_r)^n\) 展开后的项数等于 \(\binom{n+r-1}{r-1}\)。
• 例 6d：用隔板法重解天线问题。把 \(m\) 个失效品排好，记 \(x_1\) 为最左边失效品左侧的正常品数，\(x_i\) 为第 \(i-1\) 与第 \(i\) 个失效品之间的正常品数，\(x_{m+1}\) 为最右侧的正常品数。约束为 \(x_1+\cdots+x_{m+1}=n-m\)，\(x_1,x_{m+1}\ge0\)，中间 \(x_i>0\)。令 \(y_1=x_1+1\)、\(y_{m+1}=x_{m+1}+1\)，化为 \(\sum y_i=n-m+2\) 的正整数解，个数为 \(\binom{n-m+1}{m}\)，与例 4c 一致。若要求任意两个失效品之间至少隔 2 个正常品，则中间 \(x_i\ge2\)，令 \(y_i=x_i-1\)，化为 \(\sum y_i=n-2m+3\) 的正整数解，个数为 \(\binom{n-2m+2}{m}\)。

技巧：通过平移变量，把"下界约束"统一转化为正整数解问题。

量化实战

本章是纯计数工具，用在量化里主要是三件事。

1. 估计研究的"搜索规模"，为多重检验做准备。 从 50 个候选因子里挑 3 个做组合，有 \(\binom{50}{3}=19{,}600\) 种；如果每个组合还要扫"回看窗口 5 种 × 持有期 4 种 × 调仓频率 3 种"的参数网格，由乘法原理，总回测次数是 \(19{,}600\times60\approx1.18\times10^6\)。回测次数越多，纯靠运气得到漂亮结果的机会越大。这个数字本身就是第 02 章 Boole 不等式（Bonferroni 校正）里的 \(n\)，也决定了在第 03 册讲多重检验时你需要多严格的显著性门槛。

2. 离散化资产配置的枚举可行性。 例 6b 换个说法就是：把资金按最小单位分成 \(n\) 份分配给 \(r\) 个标的，可选方案有 \(\binom{n+r-1}{r-1}\) 种（不允许空仓则为 \(\binom{n-1}{r-1}\)）。\(n=20,r=4\) 时只有 1771 种，可以全部枚举再挑最优；\(n=100,r=20\) 时约为 \(4.9\times10^{21}\)，枚举不可能，只能借助第 04 册的优化方法。

3. 二叉树路径计数。 在每步上涨（乘 \(u\)）或下跌（乘 \(d\)）的二叉树中，\(n\) 步里恰好上涨 \(k\) 次的路径数是 \(\binom nk\)，所有路径数之和是 \(2^n\)（例 4e）。若每步上涨概率为 \(p\)，终点价格 \(S_0u^kd^{n-k}\) 的概率就是 \(\binom nkp^k(1-p)^{n-k}\)——这正是第 04b 章的二项分布，也是第 08 册 CRR 二叉树定价的基础。原书习题 21、22 的格点路径计数就是它的原型。

下面的代码用暴力枚举验证隔板法公式，并用模拟验证二叉树终点分布。

import itertools
from math import comb, factorial
import numpy as np

# 1) 研究规模：从 N 个候选因子中选 k 个组合，再乘参数网格
N, k = 50, 3
grid = 5 * 4 * 3          # 回看窗口 5 种 × 持有期 4 种 × 调仓频率 3 种（乘法原理）
print("因子组合数 C(50,3) =", comb(N, k))
print("加上参数网格后的回测次数 =", comb(N, k) * grid)

# 2) 隔板法：20 个最小单位资金分配到 4 个标的
def count_alloc(n, r, positive=False):
    """枚举 x1+...+xr=n 的解个数（暴力验证用）"""
    lo = 1 if positive else 0
    return sum(1 for x in itertools.product(range(lo, n + 1), repeat=r - 1)
               if sum(x) <= n - lo)
n, r = 20, 4
print("全部投出：公式", comb(n + r - 1, r - 1), " 枚举", count_alloc(n, r))
print("允许留现金：公式", comb(n + r, r), " 枚举", count_alloc(n, r + 1))
print("每个标的至少 1 单位：公式", comb(n - 1, r - 1), " 枚举", count_alloc(n, r, positive=True))

# 3) 二叉树路径计数：n 步中上涨 k 次的路径数 = C(n,k)
S0, u, d, p, steps = 100.0, 1.02, 1 / 1.02, 0.5, 10
ks = np.arange(steps + 1)
paths = np.array([comb(steps, j) for j in ks])
prob = paths * p**ks * (1 - p)**(steps - ks)
ST = S0 * u**ks * d**(steps - ks)
print("路径数:", paths.tolist(), " 总和 =", paths.sum(), "= 2^10 =", 2**steps)
rng = np.random.default_rng(0)
ups = rng.binomial(1, p, size=(200_000, steps)).sum(axis=1)
emp = np.bincount(ups, minlength=steps + 1) / len(ups)
for j in (3, 5, 7):
    print(f"上涨 {j} 次: S_T={ST[j]:.2f}  理论概率={prob[j]:.4f}  模拟={emp[j]:.4f}")

关键输出：

因子组合数 C(50,3) = 19600
加上参数网格后的回测次数 = 1176000
全部投出：公式 1771  枚举 1771
允许留现金：公式 10626  枚举 10626
每个标的至少 1 单位：公式 969  枚举 969
路径数: [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]  总和 = 1024 = 2^10 = 1024
上涨 3 次: S_T=92.38  理论概率=0.1172  模拟=0.1165
上涨 5 次: S_T=100.00  理论概率=0.2461  模拟=0.2467
上涨 7 次: S_T=108.24  理论概率=0.1172  模拟=0.1174

枚举结果与 \(\binom{23}{3}\)、\(\binom{24}{4}\)、\(\binom{19}{3}\) 完全一致；中间那行路径数就是 Pascal 三角的第 10 行。

本章小结

所有计数都建立在乘法原理上：分步计数时，只要每一步的选项个数不依赖前面的具体选择，就可以相乘。排列 \(n!\)、含相同元素的排列、组合 \(\binom nr\)、多项式系数是同一个思想的不同表现——先按"可区分、有顺序"来数，再除以重复计数的倍数。Pascal 恒等式、二项式定理、多项式定理都可以用组合论证得到，组合证明往往比代数证明更直观。分组时要分清组有没有标签。隔板法给出方程整数解的个数，有下界约束时先平移变量。

练习

基础

1. 7 人围成一排拍照，其中甲乙必须相邻，有多少种排法？若甲乙不能相邻呢？ 提示：相邻用捆绑法 \(6!\cdot2=1440\)；不相邻用总数减去相邻，\(7!-1440=3600\)（或插空法 \(5!\cdot\binom62\cdot2!\)）。
2. 单词 MISSISSIPPI 的字母有多少种不同排列？ 答案：\(\frac{11!}{1!\,4!\,4!\,2!}=34{,}650\)。
3. 在 \(4\times3\) 的格点上，从左下角走到右上角，每步只能向右或向上，共有多少条路径？（原书习题 21 的类型） 答案：需走 4 右 3 上，路径数 \(\binom73=35\)。这正是二叉树中到达某节点的路径数。
4. 一副 52 张牌中任取 5 张，共有多少手牌？其中"葫芦"（三条加一对）有多少手？ 答案：\(\binom{52}{5}=2{,}598{,}960\)；葫芦 \(13\cdot12\cdot\binom43\binom42=3744\)。
5. 证明 \(\binom nr=\binom n{n-r}\)，并给出组合解释。 提示：选出 \(r\) 个入选者等价于选出 \(n-r\) 个落选者。

进阶

6. （Vandermonde 恒等式，原书理论练习 8）证明 \(\binom{n+m}{r}=\sum_{i}\binom ni\binom m{r-i}\)，并由此推出 \(\binom{2n}{n}=\sum_k\binom nk^2\)。 提示：\(n\) 个男生和 \(m\) 个女生中选 \(r\) 人，按其中男生人数 \(i\) 分类。第 04b 章的超几何分布归一化要用到它。
7. 用"选一个委员会并指定主席"的两种计数方式证明 \(k\binom nk=n\binom{n-1}{k-1}\)，再由此证明 \(\sum_{k}k\binom nk=n2^{n-1}\)。 提示：先选委员会再选主席，或先选主席再选其余成员。后者对 \(k\) 求和后用二项式定理。
8. 你有 10 万元，以 1 万元为单位投资 4 个策略，要求策略 1 至少 2 万、策略 2 至少 2 万、策略 3 和 4 至少 1 万，且必须全部投出。有多少种方案？ 答案：平移 \(y_1=x_1-1,\ y_2=x_2-1\)，化为 \(y_1+y_2+x_3+x_4=8\) 的正整数解，\(\binom73=35\)。
9. 把 \(n\) 个不同物品放入 \(r\) 个不同盒子（允许空盒），共有多少种放法？由此证明 \(\sum\frac{n!}{x_1!\cdots x_r!}=r^n\)，求和遍历 \(x_1+\cdots+x_r=n\) 的非负整数解。（原书自测题 20） 提示：每个物品有 \(r\) 种去处，共 \(r^n\) 种；按各盒物品数分类，每类有多项式系数种。
10. 某研究员从 40 个因子中选 2 到 4 个做等权组合，每个组合测试 3 种调仓频率。一共进行了多少次回测？ 答案：\(3\big[\binom{40}2+\binom{40}3+\binom{40}4\big]=3(780+9880+91390)=306{,}150\)。

原书推荐习题：Problems 7、10（相邻/不相邻约束）、21、22（格点路径）、25（桥牌发牌，多项式系数）、31–34（隔板法及带下界约束）；Theoretical Exercises 8、9（Vandermonde 恒等式）、10、12（双重计数）、11（Fermat 恒等式）、13（交错和，容斥原理的前置）、16（允许并列的排名数递推）；Self-Test 1、9、17、20。

原书对照

（书内页码 = PDF 页码 − 13。）