这是高中数学知识点汇总系列的第九篇.

两个计数原理

加法和乘法经过推广成为分类加法计数原理和分步乘法计数原理.

  • 分类加法计数原理 : 完成一件事有 nn 类不同方案, 在第 kk 类方案中有 NkN_k 种不同的方法 (每类不同方案中的方法互不相同), 那么完成这件事共有 N=∑k=1nNk\displaystyle N=\sum\limits_{k=1}^n N_k 种不同的方法.
  • 分步乘法计数原理 : 完成一件事需要 nn 个步骤, 做第 kk 个步骤有 NkN_k 种不同的方法 (无论每一步采用哪种方法, 其下一步方法数均相同), 那么完成这件事共有 N=∏k=1nNk\displaystyle N=\prod\limits_{k=1}^n N_k 种不同的方法.

排列组合

  • nn 的阶乘 n!n!: 正整数 11 到 nn 的连乘积. 规定 0!=10!=1.

    性质: 裂项 n⋅n!=(n+1)!−n!n\cdot n!=(n+1)!-n!.

  • (一个)排列: 从 nn 个不同元素中取出 mm 个元素, 并按照一定的顺序排成一列. (强调顺序)

    排列数: 从 nn 个不同元素中取出 mm 个元素的所有不同排列的个数, 用 Anm\text{A}^m_n 或 Pnm\text{P}_n^m 表示.

    排列数公式: Anm=n(n−1)⋯(n−m+1)=n!(n−m)!\text{A}^m_n=n(n-1)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}.

    全排列: 把 nn 个不同的元素全部取出的一个排列. Ann=n(n−1)⋯(3)(2)(1)=n!\text{A}^n_n=n(n-1)\cdots(3)(2)(1)=n!.

    性质: Anm=AnkAn−km−k\text{A}_n^m=\text{A}_n^k\text{A}_{n-k}^{m-k}, (#) nn 元情形: 若 m0=0,∑k=0t+1mk=mm_0=0,\sum\limits_{k=0}^{t+1}m_k=m, 则 Anm=∏j=0tAn−∑k=0jmkmj+1\displaystyle \text{A}_n^m=\prod\limits_{j=0}^t\text{A}_{n-\sum\limits_{k=0}^jm_k}^{m_{j+1}}.

    注: m<nm<n 时称为选排列.

  • (一个)组合: 从 nn 个不同元素中取出 mm 个元素作为一组. (不强调顺序)

    组合数: 从 nn 个不同元素中取出 mm 个元素的所有不同组合的个数, 用 Cnm\text{C}_n^m 或 (nm)\dbinom{n}{m} 表示.

    组合数公式: Cnm=AnmAmm=n(n−1)⋯(n−m+1)m!=n!m!(n−m)!\text{C}^m_n=\dfrac{\text{A}_n^m}{\text{A}^m_m}=\dfrac{n(n-1)\cdots(n-m+1)}{m!}=\dfrac{n!}{m!(n-m)!}.

    性质:

    • 对称恒等 Cnk=Cnn−k\text{C}_n^k=\text{C}_n^{n-k}. 组合解释: nn 个球中取 kk 个球   ⟺  \iff nn 个球中取 (n−k)(n-k) 个球扔掉.

    • 最大值: 当 nn 为偶数时, Cnn2\text{C}_{n}^{\frac n2} 取最大值; 当 nn 为奇数时, Cnn−12\text{C}_{n}^{\frac{n-1}2} 和 Cnn+12\text{C}_{n}^{\frac {n+1}2} 相等且取最大值.

    • 求和恒等 Cn+1k=Cnk+Cnk−1\text{C}_{n+1}^k=\text{C}_n^k+\text{C}_n^{k-1}. 推论: 裂项 ∑k=mnCkt=Cn+1t+1−Cmt+1\sum\limits_{k=m}^n \text{C}_k^t=\text{C}_{n+1}^{t+1}-\text{C}_m^{t+1}.

      组合解释: (n+1)(n+1) 个球中取 kk 个球   ⟺  \iff 先考虑第一个球, 若取则相当于在剩下 nn 个球中取 kk 个; 若不取则相当于在剩下 nn 个球中取 (k−1)(k-1) 个, 两种情况求和.

    • CnkCkj=CnjCn−jk−j\text{C}_n^k\text{C}_k^j=\text{C}_n^j\text{C}_{n-j}^{k-j}, 推论:

      jj 恒等式 ∑k=1nkjCnk\sum\limits_{k=1}^nk^j\text{C}_n^k 的值
      11 kCnk=nCn−1k−1k\text{C}_n^k=n\text{C}_{n-1}^{k-1} n2n−1n2^{n-1}
      22 k(k−1)Cnk=n(n−1)Cn−2k−2k(k-1)\text{C}_n^k=n(n-1)\text{C}_{n-2}^{k-2} (#) n(n+1)2n−2n(n+1)2^{n-2}
      33 k(k−1)(k−2)Cnk=n(n−1)(n−2)Cn−3k−3k(k-1)(k-2)\text{C}_n^k=n(n-1)(n-2)\text{C}_{n-3}^{k-3} (#) n2(n+3)2n−3n^2(n+3)2^{n-3}

      组合解释: nn 个球中选 mm 个球, mm 个球中再选 kk 个球   ⟺  \iff nn 个球中选 kk 个球, 剩下 (n−k)(n-k) 个球中选 (m−k)(m-k) 个球.

    • Cn0+Cn1+Cn2+⋯+Cnn=2n\text{C}_n^0+\text{C}_n^1+\text{C}_n^2+\cdots+\text{C}_n^n=2^n; Cn0−Cn1+Cn2−⋯+(−1)nCnn=0\text{C}_n^0-\text{C}_n^1+\text{C}_n^2-\cdots+(-1)^n\text{C}_n^n=0.

      推论: Cn0+Cn2+Cn4+⋯=Cn1+Cn3+Cn5+⋯=2n−1\text{C}_n^0+\text{C}_n^2+\text{C}_n^4+\cdots=\text{C}_n^1+\text{C}_n^3+\text{C}_n^5+\cdots=2^{n-1}.

    • 范德蒙恒等式(设下标 kk 均使组合数有意义):

      • ∑k=0nCakCbn−k=Ca+bn\sum\limits_{k=0}^n\text{C}_a^k\text{C}_b^{n-k}=\text{C}_{a+b}^{n}. (可用于证明超几何分布概率和为 11)

        组合解释: aa 个正品, bb 个次品, 取 nn 个   ⟺  \iff 取 kk 个正品和 (n−k)(n-k) 个次品, 对 kk 求和.

      • (#) ∑k=0nCkaCn−kb=Cn+1a+b+1\sum\limits_{k=0}^n\text{C}_k^a\text{C}_{n-k}^b=\text{C}_{n+1}^{a+b+1}.

注: 规定当 m>nm>n 或 m<0m<0 时 Anm=Cnm=0\text{A}^m_n=\text{C}^m_n=0, 但高中规定其无意义. 因此可列出 n≥mn\ge m 且 n,m∈Nn,m\in\N 的条件，该条件可能有助于解题.

二项式定理

  • 二项式定理: ∀n∈N∗(x+y)n=T\displaystyle \forall n\in\N^*\quad{(x+y)}^{n}=T, 二项展开式 TT=∑k=0nTk+1=\sum\limits_{k=0}^{n}{T_{k+1}};

    通项Tk+1T_{k+1}=Cnkxn−kyk=\text{C}_n^kx^{n-k}y^k(注意上标); 二项式系数: Cnk(k=0,⋯ ,n)\text{C}_n^k(k=0,\cdots,n).

    特别地, 若 y=1y=1 则有 (1+x)n=Cn0+Cn1x+⋯+Cnnxn(1+x)^n=\text{C}_n^0+\text{C}_n^1x+\cdots+\text{C}_n^nx^n.

    推论: {(a+b)n+(a−b)n=2(an+Cn2an−2b2+Cn4an−4b4+⋯ )(a+b)n−(a−b)n=2(Cn1an−1b+Cn3an−3b3+Cn5an−5b5+⋯ )\left\{\begin{aligned} (a+b)^n+(a-b)^n&=2(a^n+\text{C}_n^2a^{n-2}b^2+\text{C}_n^4a^{n-4}b^4+\cdots)\\ (a+b)^n-(a-b)^n&=2(\text{C}_n^1a^{n-1}b+\text{C}_n^3a^{n-3}b^3+\text{C}_n^5a^{n-5}b^5+\cdots)\\ \end{aligned}\right..

  • (#) 牛顿二项式定理: ∀α∈R(x+y)α=∑k=0∞(αk)xα−kyk\displaystyle\forall \alpha\in\R\quad{(x+y)}^{\alpha}=\sum\limits_{k=0}^{\infty}{\dbinom{\alpha}{k}x^{\alpha-k}y^k},

    其中 (αk)=α(α−1)⋯(α−k+1)k!\dbinom{\alpha}{k}=\dfrac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}, 规定 (α0)=1\dbinom{\alpha}{0}=1.

    (#) 多项式定理: 定义 (nn1 n2 ⋯ nk)=n!n1!n2!⋯nk!\displaystyle\binom{n}{n_1\ n_2\ \cdots\ n_k}=\frac{n!}{n_1!n_2!\cdots n_k!} , 则

    ∀n∈N∗(∑t=1kxt)n=∑n1+⋯+nk=n((nn1 ⋯ nk)∏t=1kxtnt)=n!∑n1+⋯+nk=n∏t=1kxtntnt!\displaystyle\forall n\in\N^*\quad\left(\sum\limits_{t=1}^kx_t\right)^n=\sum\limits_{n_1+\cdots+n_k=n}\left(\binom{n}{n_1\ \cdots\ n_k}\prod\limits_{t=1}^kx_t^{n_t}\right)=n!\sum\limits_{n_1+\cdots+n_k=n}\prod\limits_{t=1}^k\dfrac{x_t^{n_t}}{n_t!}.

注: x,y\textit{x,y} 中还可以取复数或多项式.

杨辉三角

  • 第 nn 行第 mm 个数字为 Cn−1m−1\text{C}_{n-1}^{m-1}; 第 nn 行数字之和为 2n−12^{n-1}.
  • 一些组合数性质可以应用到杨辉三角中.

课本知识挖掘

  • 单循环赛: 每两个队伍之间进行一场比赛.

    双循环赛: 每两个队伍之间进行两场比赛, 主客场各一次.

    若有 nn 个队伍, 则一共进行 n(n−1)2\dfrac{n(n-1)}{2} 场单循环赛, n(n−1)n(n-1) 场双循环赛.

  • nn 元集合的不同子集有 2n2^n 个.

  • (2n)!=(1)(3)(5)⋯(2n−1)⋅2n⋅n!(2n)!=(1)(3)(5)\cdots(2n-1)\cdot 2^n\cdot n!.

  • 若第 k1k_1 项和第 k2k_2 项的二项式系数相等, 那么有Cnk1−1=Cnk2−1\text{C}_n^{k_1-1}=\text{C}_n^{k_2-1}, 即 n=k1+k2−2n=k_1+k_2-2.

  • 若 (a+b)n(a+b)^n 的第 (k−1),k,(k+1)(k-1),k,(k+1) 项的二项式系数成等差数列,

    只需找到两个连续整数 p,qp,q 满足 pq=2kpq=2k, 则 n=p2−2n=p^2-2 或 q2−2q^2-2.

  • (#) ∑k=0nAnk=[n!e]\sum\limits_{k=0}^n\text{A}^k_n=[n!e].

应试技巧

  • 等比二项式求和可考虑先用等比数列求和公式求和后再考虑系数.

  • 解含组合数的方程时勿忘 Cnm=Cnn−m\text C^m_n=\text C^{n-m}_n 会导致多解.

  • 排列组合计数:

    • 数字排列注意不能有前导 00.

    • 特殊位置优先确定.

    • 善用分类讨论, 如果不太好算可以分多几类.

    • 分组是组合问题, 分配是排列问题.

    • 要求相邻考虑捆绑法; 要求隔离考虑插入法(插入需要被隔离的物体).

    • 缩倍法: 地位均等时根据对称性将结果乘上倍数; 规定顺序时根据对称性将结果除以系数.

    • 正难则反: 多个条件互相约束时考虑利用容斥原理转换问题.

      A∩B=S−A‾−B‾+A‾∪B‾A\cap B=S-\overline A-\overline B+\overline A\cup\overline B

    • 要求固定顺序可以使用缩倍法或插入法.

    • 同元素分配考虑插板法.

    • 遇到单圈先剪成链状后建立递推式, 即利用马尔科夫链处理, 再求解通项.

  • 一些模型:

    • 可重复排列: nn 个元素中取 mm 个元素(允许重复取出)按顺序排成一列, 方案数 nmn^m.

    • 不全相异元素全排列 (Mississippi\text{Mississippi} 公式): n=∑k=1nnkn=\sum\limits_{k=1}^nn_k 个元素中分别有 n1,n2,⋯ ,nkn_1,n_2,\cdots,n_k 个元素相同, 则这 nn 个元素的全排列数为 Cn1+⋯+nkn1Cn2+⋯+nkn2⋯Cnknk=(nn1 n2 ⋯ nk)\text{C}_{n_1+\cdots+n_k}^{n_1}\text{C}_{n_2+\cdots+n_k}^{n_2}\cdots \text{C}_{n_k}^{n_k}=\displaystyle\binom{n}{n_1\ n_2\ \cdots\ n_k}.

    • 插板法: nn 个相同的球装入 mm 个盒中, 每个盒中至少有 kk 个球, 方案数 Cn−mk+m−1m−1\text{C}_{n-mk+m-1}^{m-1}.

    • 圆排列: nn 个不同的元素不分首尾排成一圈, 方案数 (n−1)!(n-1)!.

    • 项链数: n(n≥3)n(n\ge3) 粒不同的珠子串成项链, 方案数 12(n−1)!\dfrac12(n-1)!.

    • 环染色: n(n≥2)n(n\ge2) 元环染 kk 种色, 相邻格子不同色, 方案数 (k−1)n+(−1)n(k−1){(k-1)}^n+{(-1)}^n(k-1).

    • 错排问题: nn 个球打乱后每个球不在原位, 方案数 (#) Dn=n!∑k=0n(−1)kk!=[n!e]D_n=n!\sum\limits_{k=0}^n\dfrac{{(-1)}^k}{k!}=\left[\dfrac{n!}{e}\right].

      nn 0 1 2 3 4 5 6
      DnD_n 1 0 1 2 9 44 265

  • 若 (x+a)n=∑k=0nakxk{(x+a)}^{n}=\sum\limits_{k=0}^{n}{a_kx^k}. 常见考法：

    • 注意问某一项的系数还是二项式系数.

    • 代入 x=px=p 可得 a0+a1p+⋯+anpna_0+a_1p+\cdots+a_np^n.

      • 代入 x=1x=1 可得各项系数和 a0+a1+⋯+ana_0+a_1+\cdots+a_n.
      • 代入 x=−1x=-1 可得 a0−a1+⋯+(−1)nana_0-a_1+\cdots+{(-1)}^na_n.
      • 将结果同除 pnp^n 可得 a0pn+a1pn−1+⋯+an\dfrac{a_0}{p^n}+\dfrac{a_1}{p^{n-1}}+\cdots+a_n.

    • 在 (x+∣a∣)n{(x+|a|)}^n 中代入 x=1x=1 可得 ∣a0∣+∣a1∣+⋯+∣an∣|a_0|+|a_1|+\cdots+|a_n|.

    • 奇偶项之和: 若 A=a0+a1+⋯+an,B=a0−a1+⋯+(−1)nanA=a_0+a_1+\cdots+a_n,B=a_0-a_1+\cdots+{(-1)}^na_n,

      则 a1+a3+a5+⋯=12(A−B),a0+a2+a4+⋯=12(A+B)a_1+a_3+a_5+\cdots=\dfrac{1}{2}(A-B),a_0+a_2+a_4+\cdots=\dfrac{1}{2}(A+B).

    • a1+2a2+⋯+nana_1+2a_2+\cdots+na_n: 式子两边分别求导后代入 x=1x=1 即得.

    • 所求式可能缺项, 如需要求 a1+a2+⋯+ana_1+a_2+\cdots+a_n 时要将 a0a_0 减去.

    • (#) 代入 nn 次单位根再求和可得隔 nn 项之和.